Mamy liczby: 7,6,6. Elementem wg którego należy sortować to "7". Rozpoczynamy od lewej strony szukanie elementu >= 7 - brak takiego, od prawej szukamy <=7 i jest to "6", i co dalej ? Bo przecież zamienić miejscami mozna tylko element >= z <=.
0
0
elementem z lewej storny będzie 7 bo 7 >= 7 :)
0
Ale "7" przecież nie możemy brać pod uwagę szukając elementu większego >=7 bo przecież to wg tego elementu szukamy - gdyby tak można było zrobić to mając:
7,12,5 to 7>=7 a 5<=7 więc zamiana miejscami:
5,12,(7) i "7" byłoby już na swoim miejscu - co oczywiście jest błędem
0
to nic nie robisz bo warunek też jest że indeks elementu z lewej jest mniejszy od indeksu elementu z prawej
0
Ale jak to nic nie robię - to mi się nie posortuje :-)
Dwie najdziwniejsze sytuacje w quicksorcie, których nie rozumiem - jak mamy np. 7 6 6 to znaczy idąc od lewej strony NIE MA elementu >= a idąc od prawej jest element <= od pierwszego elementu czyli "7"
oraz
np. 6 8 7 czyli idąc od lewej strony jest element >= a idąc od prawej strony NIE MA elementu <= od pierwszego elementu czyli "6"
jak się wtedy quicksort zachowuje ?
0
a Ty chcesz rosnąco? To przecież z lewej bierzesz 7 a z prawej 6 i zamieniasz. Nie porównujesz element z pierwszym w tablicy tylko z jakąś zmienną pivot, której przypisujesz wartość jakiegoś elementu niekoniecznie pierwszego
0
z tego co pamiętam, to w quicksort jest tak, że bierze się pierwszą liczbę z tablicy (ale niekoniecznie, tak jest po prostu wygodnie), po czym dzieli się resztę tablicy na mniejsze i większe lub równe. dlatego:
dla liczb 7,6,6
tworzone są tablice:
- 6,6
- PUSTA
- liczba 7, która będzie wstawiona pomiędzy te dwie
jeżeli sortujemy rosnąco to wynik będzie:
tablica1,liczba o indeksie 1,tablica2 => 6,6,7
a jeśli malejąco to
tablica2,liczba o indeksie 1,tablica1 => 7,6,6
i tyle.
0
1 Partition(l,r)::
2 begin
3 v := a[l]; i := l; j := r+1;
4 repeat
5 //Niezmiennik: dla każdego k=l,l+1,\ldots,i, a[k] < v,
6 // dla każdego k=j,j+1,\ldots,r+1, a[k] > v,
7 // j-i \ge -1.
8 repeat i := i+1 until a[i] > v; //za ostatnim elem. musi stać straznik-elem wiekszy od wszystkich innych
9 repeat j := j-1 until a[j] < v;
10 if i < j then
11 Exchange(i,j);
12 until i \ge j;
13 a[l] := a[j]; a[j] := v;
14 return j
15 end;
Dla: 7,12,5
- Zamienione zostaną 12 i 5
Na pierwsze miejsce zostanie wpisana 5 (a[l] := a[j];)</li>
Na drugie miejsce zostanie wpisana 7 (a[j] := v;)</li>
</ol>
Dla:7,6,6
Poprzez Exchange(i,j) nie zostanie zamieniony zadny elem, bo i==j</li>
Na pierwsze miejsce zostanie wpisana 6 (a[l] := a[j];)</li>
Na trzecie miejsce zostanie wpisana 7 (a[j] := v;)</li>
</ol>
0
Nie znam Pascala ale czy dla 7,6,6 to to quicksort wg tego kodu co podałeś jak będzie szukać od lewej elementu > od "7" to czy nie nastąpi wyjście poza tablicę skoro nie ma elementu > od "7" i skoro wg tego kodu należy szukać elementów > i < od pierwszego elementu to byłby problem z posortowaniem: 6,7,6 - bo należy raczej szukać elementów >= i <=.
0
No ale jest napisane, że za ostatnim stoi strażnik, a na pierwszym się na pewno zatrzyma
0
Aaa nie zauważyłem, że tam coś jest napisane o strażniku :)
Ale w przypadku 6,7,6 to by się chyba nie posortowało - należałoby zmienić "> i <" na ">= i <=" - a może się mylę ?
Bo teraz element większy od "6" to 7, mniejszego nie ma więc wskaźnik zatrzymałby się na pierwszym elemencie = "6", pierwszy element zamieniłby się sam ze sobą i tak w kółko