I got a task to implement a QuickSort algorithm on an ArrayList which can use as a pivot:
- Last item of an ArrayList.
- Random item of an ArrayList.
- Median value of the first one, the last one and the middle value of the ArrayList.
The problem is that only the first way works 100% properly and the rest is making some weird mistakes and I can not find the mistake. Maybe one of you will be able to do it.
import java.io.*;
import java.util.Random;
import java.util.ArrayList;
import java.util.Scanner;
public class Sortowanie {
ArrayList<Integer> data;
public Sortowanie(String File) {
data=new ArrayList<Integer>();
BufferedReader reader=null;
try {
reader = new BufferedReader(new FileReader(File));
String wiersz = null;
while((wiersz = reader.readLine()) != null) {
String [] liczby = wiersz.split(",");
wiersz.trim();
for(int i=0; i<liczby.length; i++) {
int liczba= Integer.parseInt(liczby[i]);
data.add(liczba);
}
}
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public void quicksort( int x, int y, int v) {
int i,j,temp;
i=x;
j=y;
int pivot=0;
switch(v) {
case 0: {
pivot = y;
break;
}
case 1: {
Random r=new Random();
pivot = (r.nextInt(y-x+1))+x;
break;
}
case 2: {
int naj=x;
if(data.get((x+y)/2)>data.get(naj)) naj=((x+y)/2);
if(data.get(y)>data.get(naj)) naj=y;
pivot=naj;
break;
}
}
do {
while (data.get(i)<data.get(pivot))
i++;
while (data.get(pivot)<data.get(j))
j--;
if (i<=j) {
temp=data.get(i);
data.set( i, data.get(j));
data.set(j, temp);
i++;
j--;
}
}while (i<=j);
if (x<j) {
quicksort(x,j, v);
// System.out.println("while(x<j)");
}
if (i<y)
{
quicksort(i,y, v);
//System.out.println("while(i<y)");
}
}
Aucun commentaire:
Enregistrer un commentaire