Witam, mam następujący problem, mam program który ma mi realizować quicksort, liczyć liczbę porównań, zmian oraz współczynnik średniej złożoności. Program powyżej 10 liczb do posortowania się "wykrzacza", źle liczy liczbę zmian, a współczynnika w ogóle nie mogę jakoś ogarnąć.
import java.util.*; // importujemy pakiety
public class Sort {
static int qsComparew1=0, qsComparew2=0,qsSwitch=0, selCompare=0, selSwitch=0; //liczba zamian i porownan
public static void main(String [] args){
Scanner keyIn = new Scanner(System.in); //tworzymy obiekt Scanner przylaczony do klawiatury
Random rnd = new Random(); //tworzymy obiekt do losowania liczb
System.out.print("Podaj ilość liczb:");
int sizeArray = Integer.parseInt(keyIn.nextLine()); //rozmiar tablicy
int [] qsArr= new int[sizeArray]; //tablica do posortowania
for (int i=0 ; i<sizeArray; i++) // wypełniamy tablice losowymi liczbami do 99
{
qsArr[i]=rnd.nextInt(100);
}
int [] selArr = qsArr.clone(); //klonujemy tablice
for (int i=0; i<qsArr.length; i++)
System.out.print(" "+qsArr[i]);
//int [] qsArr ={17, 75, 51, 0, 85, 80, 44, 87, 7, 88, 85, 30, 81, 46, 66, 57, 54, 14};
System.out.println("\n\nSortowanie Quick Sort");
quickSort(qsArr); //sortujemy quick sort
System.out.println("\nLiczba prównan "+ (qsComparew1 +qsComparew2) + ", liczba zamian "+ qsSwitch );
for (int i=0; i<qsArr.length; i++) //wyswietlamy tablice
System.out.print(" "+qsArr[i]);
//int [] selArr = qsArr.clone();
System.out.println("\n\nSortowanie Selection Sort");
selectionSort(selArr); //sortujemy alg. selection sort
System.out.println("\nLiczba prównan "+ selCompare + ", liczba zamian "+ selSwitch );
for (int i=0; i<selArr.length; i++)
System.out.print(" "+selArr[i]);
}
public static void quickSort(int [] arrInt){ //metoda squick sort
recQSort(arrInt, 0, arrInt.length-1);
}
public static void recQSort(int [] arrInt, int first, int last){
int pivotLoc; //pozycja podzialu
if (last-first<=0) //jezeli tablica 1-elementowa
return;
else{
pivotLoc = pivotInt(arrInt, first, last);
recQSort(arrInt, first, pivotLoc); //rekursywne wywyłanie
recQSort(arrInt, pivotLoc+1, last); //rekursywne wywyłanie
}
}
public static int pivotInt(int [] arrInt, int first, int last ){ //metoda podziału na dwie grup
int pivot = arrInt[first]; //os podzialu
int scanup = first+1; // wskaznik dolny przesuwany do góry
int temp; //wartosc tymczasowa
int scandown = last; //wsakznik gorny przesuwany w dol
while(true){
qsComparew1++;
while ( scanup<=scandown && arrInt[scanup]<pivot ) //znajdujemy wiekszy element od wartosci osiowej
{
scanup++;
qsComparew1++;
}
qsComparew2++;
while ( arrInt[scandown]>pivot ){ //znajdujemy mniejszy element od wartosci osiowej
scandown--;
qsComparew2++;
}
if (scanup>=scandown) //jezeli nie ma podlist to podzial kompletny
break;
else { //zamieniemy elementy miejscami
temp=arrInt[scanup];
arrInt[scanup]=arrInt[scandown];
arrInt[scandown]=temp;
qsSwitch++;
scanup++;
scandown--;
}
}
//przesuwamy wartosc osiowa w odpowiednie miejsce
temp=arrInt[scandown];
arrInt[scandown]=arrInt[first];
arrInt[first]=temp;
return scandown;
}
public static void selectionSort(int [] arrInt){
int n=arrInt.length;
int pass, small, temp;
for (pass=0; pass<n-1;pass++){ // skanujemy tablice
small=pass; //ustalamy najmniejszy element
for(int j=pass+1;j<n;j++){ //przeszukujemy subliste
selCompare++;
if (arrInt[j]<arrInt[small]) //jezeli znajdujemy element mniejszy
small=j;
}
//zamieniamy miejscami elementy
temp = arrInt[pass];
arrInt[pass] = arrInt[small];
arrInt[small] = temp;
selSwitch++;
}
}
}
Jakieś pomysły?