Sortowanie quicksort - kilka pytań

Question

Witam serdecznie. Jestem nowym użytkownikiem forum MZ, dlatego, jeśli to możliwe, proszę o wyrozumiałość. ;) Witajcie.

Od kilku godzin analizuję algorytm quicksort. Większość już rozumiem (tak, wiem, szybki nie jestem...), ale mam kilka wątpliwości.

void quicksort(int *tablica, int lewy, int prawy) { 
	int v=tablica[(lewy+prawy)/2]; 
	int i,j,x; 
	i=lewy; 
	j=prawy; 
	do{ 
		while (tablica[i]<v) i++; 
		while (tablica[j]>v) j--; 
		if (i<=j){ 
			x=tablica[i]; 
			tablica[i]=tablica[j]; 
			tablica[j]=x; 
			i++; 
			j--; 
		} 
	} while (i<=j); 
	if (j>lewy) quicksort(tablica,lewy, j); 
	if (i<prawy) quicksort(tablica, i, prawy); 
}

Kod z prezentacji pana Zelenta.

Moje pytania:
- dlaczego w linii 9. i 16. używamy warunku mniejszy bądź równy zamiast mniejszy?
- dlaczego używamy pętli do..while, a nie while; czemu pętla powinna wykonać się raz przed sprawdzeniem warunku?
- dlaczego w 17. i 18. linijce kodu są warunki; co by było bez nich?

Pozdrawiam, z góry dziękuję za odpowiedź.

Answer 1

Moje pytania:
- dlaczego w linii 9. i 16. używamy warunku mniejszy bądź równy zamiast mniejszy?
- dlaczego używamy pętli do..while, a nie while; czemu pętla powinna wykonać się raz przed sprawdzeniem warunku?
- dlaczego w 17. i 18. linijce kodu są warunki; co by było bez nich?

Pozdrawiam, z góry dziękuję za odpowiedź.

 1. Ponieważ indexy i oraz j mają się "minąć", aby potem wywołania w linii 17 i 18 miały sens. Zauważ że i służy jako lewy index prawej tablicy, a j jako prawy index lewej tablicy. W przeciwnym wypadku możliwe jest że i będzie równe j, co jest bezsensowne, gdyż ten element na które wskazywały by te indeksy, to już dobrze wypozycjonowany element. Strata czasu.
2. Wywolując funkcję quicksort parametr lewy jest <= parametrowy prawy, więc można pominąć pierwsze sprawdzenie
3. Bez tych warunków dla tablic jednoelementowych funcja nadal wy się wywoływała (j == lewy ==prawy == i). Stack overflow! :)

Comments

Ok, dzięki za wyjaśnienie.

A nie da się tak przepisać tej funkcji, zeby i oraz j nie musiły się "mijać" tylko żeby, gdy "dobiją" do siebie, od razu zacząć rekurencyjne wywoływanie funkcji quicksort, zmieniając oczywiście też warunki w ostatnich linijkach?

Dzięki twojemu wyjaśnieniu już wszystko rozumiem, ale ciekawi mnie, czy bez "mijania się" p i q, tutaj i i j, da się to zrobić?

---

Hmm, zapewne się da, nie miałem styczności z tym algorytmem od ponad roku, ale może spróbuję coś naskrobać.

---

ok, chyba działa, kilkanaście razy testowałem w kazdym razie :P
 

void quicksort(int *tablica, int lewy, int prawy) {
	int v = tablica[(lewy + prawy) / 2];
	int i, j, x;
	i = lewy;
	j = prawy;
	do {
		while (tablica[i]<v) i++;
		while (tablica[j]>v) j--;
		if (i < j) {
			x = tablica[i];
			tablica[i] = tablica[j];
			tablica[j] = x;
			i++;
			j--;
		}
	} while (i < j);

	if (j>lewy) quicksort(tablica, lewy, j==i ? j-1 : j);
	if (i<prawy) quicksort(tablica, j==i ? i+1 : i, prawy);
}