Quicksort: Wybieranie osi

Wdrażając Quicksort, jedną z rzeczy, które musisz zrobić, jest wybranie pivota. Ale kiedy patrzę na pseudokod, taki jak ten poniżej, nie jest jasne, jak powinienem wybrać oś. Pierwszy element listy? Coś innego?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Czy ktoś może mi pomóc pojąć koncepcję wyboru punktu zwrotnego i tego, czy różne scenariusze wymagają różnych strategii.

Wybranie losowego obrotu minimalizuje prawdopodobieństwo, że napotkasz wydajność dla najgorszego przypadku O (n ² ) (zawsze wybranie pierwszego lub ostatniego spowodowałoby wydajność w najgorszym przypadku dla danych prawie posortowanych lub prawie odwrotnie posortowanych). Wybór środkowego elementu byłby również akceptowalny w większości przypadków.

Ponadto, jeśli implementujesz to samodzielnie, istnieją wersje algorytmu, które działają w miejscu (tj. Bez tworzenia dwóch nowych list, a następnie ich łączenia).

To zależy od twoich wymagań. Losowy wybór obrotu utrudnia utworzenie zestawu danych, który generuje wydajność O (N ^ 2). „Mediana-trzech” (pierwsza, ostatnia, środkowa) jest również sposobem na uniknięcie problemów. Uważaj jednak na względną wydajność porównań; jeśli twoje porównania są kosztowne, Mo3 wykonuje więcej porównań niż losowy wybór (pojedynczej wartości obrotu). Porównywanie rekordów bazy danych może być kosztowne.

Aktualizacja: dodawanie komentarzy do odpowiedzi.

mdkess zapewnił:

„Mediana z 3” NIE jest pierwszą i ostatnią środkową. Wybierz trzy losowe indeksy i weź środkową wartość tego. Chodzi o to, aby upewnić się, że wybór osi nie jest deterministyczny - jeśli tak jest, dane najgorszego przypadku można dość łatwo wygenerować.

Na co odpowiedziałem:

• Analiza algorytmu znalezienia Hoare'a z podziałem na medianę z trzech (1997) autorstwa P. Kirschenhofera, H. Prodingera, C. Martíneza potwierdza twoje twierdzenie (że „mediana-trzech” to trzy losowe pozycje).

• Na portal.acm.org opisano artykuł o „Najgorszym przypadku permutacji mediany trzech szybkich sortowań” autorstwa Hannu Erkiö, opublikowany w The Computer Journal, tom 27, nr 3, 1984. [Aktualizacja 2012-02- 26: Mam tekst do artykułu . Rozdział 2 „Algorytm” zaczyna się: „ Korzystając z mediany pierwszego, środkowego i ostatniego elementu A [L: R], w większości praktycznych sytuacji można uzyskać wydajne partycje na części o dość równych rozmiarach. „W związku z tym omawiane jest pierwsze, środkowe i ostatnie podejście Mo3.]

• Innym interesującym krótkim artykułem jest MD McIlroy „A Killer Adversary for Quicksort” , opublikowany w Software-Practice and Experience, Vol. 29 (0), 1-4 (0 1999). Wyjaśnia, jak sprawić, by prawie każdy Quicksort zachowywał się kwadratowo.

• AT&T Bell Labs Tech Journal, październik 1984 „Teoria i praktyka w konstruowaniu rutyny roboczej” stwierdza, że ​​Hoare zasugerował podział wokół mediany kilku losowo wybranych wierszy. Sedgewick [...] zalecał wybranie mediany pierwszego [. ..] ostatnia [...] i środkowa ”. Oznacza to, że obie techniki „mediany z trzech” są znane w literaturze. (Aktualizacja 2014-11-23: wydaje się, że artykuł jest dostępny na IEEE Xplore lub w Wiley - jeśli masz członkostwo lub jesteś gotów uiścić opłatę).

• „Engineering a Sort Function” JL Bentley i MD McIlroy, opublikowane w Software Practice and Experience, tom 23 (11), listopad 1993 r., Zawiera obszerną dyskusję na ten temat i wybrali adaptacyjny algorytm partycjonowania oparty częściowo na rozmiar zbioru danych. Jest wiele dyskusji na temat kompromisów dla różnych podejść.

• Wyszukiwanie w Google wyrażenia „mediana-trzech” działa całkiem nieźle przy dalszym śledzeniu.

Dzięki za informację; Wcześniej spotkałem się tylko z deterministyczną „medianą-trzech”.

Heh, właśnie uczyłem tej klasy.

Istnieje kilka opcji.
Prosty: wybierz pierwszy lub ostatni element zakresu. (źle na częściowo posortowanych danych wejściowych) Lepiej: Wybierz element ze środka zakresu. (lepiej na częściowo posortowanych wejściach)

Jednak wybranie dowolnego dowolnego elementu stwarza ryzyko niewłaściwego podzielenia tablicy o rozmiarze n na dwie tablice o rozmiarze 1 i n-1. Jeśli robisz to dostatecznie często, ryzykujesz, że twoje szybkie sortowanie stanie się O (n ^ 2).

Jednym z ulepszeń, które zauważyłem, jest wybór mediany (pierwsza, ostatnia, środkowa); W najgorszym przypadku nadal może dojść do O (n ^ 2), ale prawdopodobnie jest to rzadki przypadek.

W przypadku większości danych wystarczy wybrać pierwszy lub ostatni. Ale jeśli okaże się, że często napotykasz najgorsze scenariusze (częściowo posortowane dane wejściowe), pierwszą opcją byłoby wybranie wartości centralnej (która jest statystycznie dobrą osią obrotu dla częściowo posortowanych danych).

Jeśli nadal napotykasz problemy, przejdź do trasy środkowej.

Nigdy, przenigdy nie wybieraj stałej osi - może to zostać zaatakowane w celu wykorzystania czasu wykonania O (n ^ 2) najgorszego przypadku algorytmu, który po prostu prosi o kłopoty. Najgorszy przypadek środowiska uruchomieniowego Quicksort występuje, gdy partycjonowanie daje jedną tablicę zawierającą 1 element i jedną tablicę zawierającą n-1 elementów. Załóżmy, że wybierasz pierwszy element jako partycję. Jeśli ktoś prześle tablicę do twojego algorytmu, która jest w porządku malejącym, twój pierwszy przestaw będzie największy, więc wszystko inne w tablicy przesunie się na lewo od niej. Następnie, gdy powtórzysz, pierwszy element będzie ponownie największy, więc jeszcze raz umieszczasz wszystko na lewo od niego i tak dalej.

Lepszą techniką jest metoda mediany-3, w której losowo wybierasz trzy elementy i wybierasz środek. Wiesz, że wybrany element nie będzie pierwszym ani ostatnim, ale także, zgodnie z centralnym twierdzeniem granicznym, rozkład środkowego elementu będzie normalny, co oznacza, że ​​będziesz dążyć do środka (a zatem , n lg n czas).

Jeśli absolutnie chcesz zagwarantować czas wykonania algorytmu O (nlgn), metoda kolumna-5 do znajdowania mediany tablicy działa w czasie O (n), co oznacza, że ​​równanie powtarzania dla szybkiego sortowania w najgorszym przypadku będzie be T (n) = O (n) (znajdź medianę) + O (n) (podział) + 2T (n / 2) (powtórz lewy i prawy.) Zgodnie z Twierdzeniem Głównym, to jest O (n lg n) . Jednak stały współczynnik będzie ogromny i jeśli najważniejsza jest wydajność w najgorszym przypadku, zamiast tego użyj sortowania przez scalanie, które jest tylko trochę wolniejsze niż średnio szybkie sortowanie i gwarantuje czas O (nlgn) (i będzie znacznie szybsze niż ta kiepska mediana quicksort).

Wyjaśnienie algorytmu mediany median

Nie próbuj być zbyt sprytny i łącz strategie obrotu. Jeśli połączysz medianę 3 z losowym obrotem, wybierając medianę pierwszego, ostatniego i losowego indeksu pośrodku, nadal będziesz podatny na wiele rozkładów, które wysyłają medianę 3 kwadratowych (więc jest gorsza niż zwykły losowy pivot)

Np. Rozkład organów piszczałkowych (1,2,3 ... N / 2..3,2,1) pierwszy i ostatni będzie równy 1, a indeks losowy będzie o pewną liczbę większą niż 1, biorąc medianę daje 1 ( pierwszy lub ostatni) i otrzymujesz skrajnie niezrównoważone partycjonowanie.

W ten sposób łatwiej jest podzielić quicksort na trzy sekcje

1. Funkcja wymiany lub zamiany elementu danych
2. Funkcja partycji
3. Przetwarzanie partycji

Jest tylko trochę bardziej nieefektywna niż jedna długa funkcja, ale jest dużo łatwiejsza do zrozumienia.

Kod następujący:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Zależy to całkowicie od sposobu sortowania danych na początku. Jeśli uważasz, że będzie to pseudolosowe, najlepszym rozwiązaniem jest wybranie losowej selekcji lub środkowej.

Jeśli sortujesz kolekcję dostępną losowo (na przykład tablicę), najlepiej jest wybrać fizyczny element środkowy. Dzięki temu, jeśli cała tablica jest już posortowana (lub prawie posortowana), dwie partycje będą prawie równe, a uzyskasz najlepszą prędkość.

Jeśli sortujesz coś, co ma tylko dostęp liniowy (na przykład listę połączoną), najlepiej wybrać pierwszy element, ponieważ jest to element najszybciej dostępny. Tutaj jednak, jeśli lista jest już posortowana, masz spieprzone - jedna partycja zawsze będzie zerowa, a druga będzie miała wszystko, co daje najgorszy czas.

Jednak w przypadku listy z linkami wybranie czegokolwiek poza pierwszą tylko pogorszy sprawę. Wybiera środkowy element z listy, musisz przejść przez to na każdym kroku partycji - dodając operację O (N / 2), która jest wykonywana logN razy, co daje całkowity czas O (1,5 N * log N) i to jest jeśli wiemy, jak długa jest lista, zanim zaczniemy - zwykle nie, więc musielibyśmy przejść całą drogę, aby je policzyć, a następnie przejść w połowie, aby znaleźć środek, a następnie przejść przez trzeci raz zrobić właściwą partycję: O (2,5N * log N)

W idealnym przypadku punkt obrotu powinien być wartością środkową w całej tablicy. Zmniejszy to szanse uzyskania najgorszej wydajności.

Złożoność szybkiego sortowania różni się znacznie w zależności od wyboru wartości przestawnej. na przykład, jeśli zawsze wybierasz pierwszy element jako przestawienie, złożoność algorytmu staje się najgorsza jak O (n ^ 2). oto sprytna metoda wyboru elementu przestawnego - 1. wybierz pierwszy, środkowy i ostatni element tablicy. 2. porównaj te trzy liczby i znajdź liczbę większą od jednej i mniejszą od drugiej, tj. Medianę. 3. uczynić ten element elementem obrotowym.

wybranie pivota tą metodą dzieli tablicę na prawie dwie połowy, a zatem złożoność redukuje się do O (nlog (n)).

Średnio mediana 3 jest dobra dla małych n. Mediana 5 jest trochę lepsza dla większego n. Ninther, czyli „mediana z trzech median z trzech”, jest jeszcze lepsza dla bardzo dużych n.

Im wyższy poziom próbkowania, tym lepsze wyniki przy wzroście n, ale poprawa dramatycznie spada wraz ze zwiększaniem próbek. I ponosisz koszty ogólne związane z pobieraniem i sortowaniem próbek.

Zalecam użycie wskaźnika środkowego, ponieważ można go łatwo obliczyć.

Możesz to obliczyć, zaokrąglając (array.length / 2).

W naprawdę zoptymalizowanej implementacji metoda wyboru wartości przestawnej powinna zależeć od rozmiaru tablicy - w przypadku dużej tablicy opłaca się poświęcić więcej czasu na wybór dobrego przestawienia. Bez przeprowadzania pełnej analizy sądziłbym, że „środek O (log (n)) elementów” to dobry początek, a to ma dodatkową zaletę polegającą na tym, że nie wymaga dodatkowej pamięci: używanie wywołań końcowych na większej partycji i partycjonowanie miejsc, używamy tego samego O (log (n)) dodatkowej pamięci na prawie każdym etapie algorytmu.