Witam
Napisałem prostego quicksorta i mam przerobić go na quicksorta współbieżnego.
Jak normalny działa ok, tak ten przerobiony sortuje tablicę raz bardziej skutecznie, raz wcale.
import java.util.Random;
public class RandomArray{
private int size;
private int arr[];
RandomArray(){
arr = new int[1000];
size = 1000;
Random rand = new Random();
for (int i = 0; i < size; i++){
arr[i] = rand.nextInt(20);
}
}
RandomArray(int size){
this.size = size;
arr = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++){
arr[i] = rand.nextInt(20);
}
}
public int make_pivot(int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
public void quickSort(int left, int right) {
int index = make_pivot(left, right);
if (left < index - 1){
new Thread(){
public void run(){
quickSort(left, index - 1);
}
}.start();
}
if (index < right)
new Thread(){
public void run(){
quickSort(index, right);
}
}.start();
}
public void show(){
for(int i = 0; i < size; i++){
if ((i % 20 == 0) && (i != 0))
System.out.println();
System.out.print(arr[i] + "\t");
}
System.out.println();
System.out.println();
}
public int getSize() { return size; }
public int[] getTab(){
return arr;
}
}
public class Main {
public static void main(String[] args) {
RandomArray tablica = new RandomArray(20);
tablica.show();
tablica.quickSort(0, tablica.getSize()-1);
tablica.show();
}
}
W czym może tkwić problem?
Przykładowe wyjście:
0 11 19 4 2 19 17 18 0 19 8 7 19 14 1 17 15 1 5 15 - tablica przed segregacją
0 1 0 1 2 5 4 14 15 11 8 7 15 17 17 18 19 19 19 19 - tablica po "rzekomej segregacji"