algorytm.org

Algorytm Hoare'a



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Hoare'a
Ocena użytkowników:***** / 25
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 27 lipca 2005 19:06

Gdy potrzebujemy wiedzieć jaka jest wartość k-tego elementu nieposortowanego ciągu (np.: kto zdobył k-te miejsce, bądź jaka jest mediana czyli element n/2 w kolejności), można wówczas oczywiście posorotwać cały ciąg i sprawdzić k-ty element. Jest to jednak operacja zbyt kosztowna. Wystarczy bowiem zastosować algortym Hoare'a.
W algorytmie Hoare'a stosujemy podobną metodę jak w quicksorcie. Ciąg wejściowy dzielimy na 2 podciągi: elementów mniejszych i większych bądź równych pewnemu elementowi. Następnie w zależności od liczebności wynikowych podciągów wywołujemy rekurencyjnie funkcję dla odpowiedniego podciągu. Rekursję powtarzamy tak długo aż w wyniku otrzymamy ciąg o 1 elemencie.

Przykład:

Ciąg: {7,2,4,3,6,8,1,5,9}
Szukamy trzeciego elementu w ciągu
Niech elementem dzielącym będzie 7 - pierwsza liczba z brzegu, wówczas ciąg elementów mniejszych od 7 to {2,4,3,6,1,5} natomiast ciag elementów większych bądź równych: {7,8,9}.
Ponieważ ciag elemntów mniejszych od 7 jest liczniejszy niż 3, tam będziemy dalej szukać naszej liczby. A więc wywołujemy rekurencyjnie funkcję dla ciągu elementów mniejszych od 7 szukając tam elementu trzeciego.
Elementem dzielącym jest tutaj 2, wówczas ciąg elementów mniejszych od 2 to {1}, a większych bądź równych {2,4,3,6,5}.
Ponieważ ciąg elementów mniejszych od 2 ma mniej niż 3 elementy, elementu trzeciego będziemy szukać wśród elementów większych bądź równych 2. Dlatego wywołujemy rekurencyjnie funkcję poszukiwania elemntów dla tego właśnie ciągu. Lecz nie szukamy tam elementu trzeciego, lecz 3-liczność_zbioru_liczb_mniejszych, zatem szukamy teraz elementu 2 (bo 3-1=2).
Postępujemy tak tak długo aż będziemy szukać elementu pierwszego i w wyniku otrzymamy jednoelementowy ciąg liczb mniejszych od liczby dzielącej.
Program należy zabezpieczyć przed wypadkiem gdy element dzielący będzie najmniejszym elementem ciągu, gdyż wówczas ciąg elementów mniejszych od niego byłby pusty i rekurencja mogłaby być wywoływana w nieskończoność.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 15
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 09 czerwca 2011 21:32
Dodaj komentarz