Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Aktualna kategoria: Nauka » Informatyka » Liceum - lekcje

123456789101112131415161718...2122
Lekcja: "Algorytmy sortujące - algorytm Quicksort"

Tworzenie partycji cd.


Aby podzielić zbiór na dwie partycje umieszczamy na początku zbioru wskaźniki - i oraz j. Wskaźnik i przechodząc przez zbiór wyszukuje mniejsze wartości od piwotu. W monecie kiedy taka wartość jest odnaleziona, zostaje wymieniona z elementem na pozycji j.
Po wykonaniu tej operacji wskaźnik j zostanie przesunięty na kolejną pozycję w zbiorze. Wskaźnik j zapamiętuje pozycję, na podziału na partycje, będzie miejscem, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze, nie bierze udziału w przeszukiwaniu zbioru.

Wewnętrzna pętla sortowania szybkiego zwiększa wskaźnik i porównuje element tablicy z ustaloną wartością. To właśnie ta prostota sprawia, że Quicksort jest tak szybki - trudno o prostszą pętlę wewnętrzną algorytmu sortowania.

wartości mniejsze
lub równe od piwotu

wartości większe
lub równe od piwotu

PIWOT

partycja lewa

j

i

partycja prawa

element rozgraniczający

<< Poprzednia plansza   Następna plansza >>
Pobierz lekcję

Udostępnij link do tej lekcji innym uczniom:




Zgłoś uwagę do lekcji:




Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie