Sortowanie Proxmapy

Sortowanie Proxmapy
	Przykład sortowania przez wstawianie listy liczb losowych.
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku
Wydajność w najlepszym przypadku
Średnia wydajność
Najgorszy przypadek złożoności przestrzeni

Elementy są rozdzielane pomiędzy pojemniki

W przeciwieństwie do sortowania segmentowego, które sortuje po zapełnieniu wszystkich segmentów, elementy są sortowane przez wstawianie w miarę ich wstawiania

ProxmapSort lub Proxmap sort to algorytm sortowania , który działa poprzez dzielenie tablicy elementów danych, czyli kluczy, na pewną liczbę „tablic podrzędnych” (zwanych segmentami, w podobny sposób). Nazwa jest skrótem od obliczania „mapy bliskości”, która wskazuje dla każdego klucza K początek podtablicy, w której K będzie znajdować się w ostatecznej kolejności posortowania. Klucze są umieszczane w każdej podtablicy przy użyciu sortowania przez wstawianie . Jeśli klucze są „dobrze rozmieszczone” pomiędzy podtablicami, sortowanie odbywa się w czasie liniowym. Złożoność obliczeniowa szacunki obejmują liczbę podtablic i zastosowaną funkcję mapowania bliskości, czyli „klucz mapy”. Jest to forma kubełkowego i radixowego .

Po zakończeniu ProxmapSort można użyć ProxmapSearch do znalezienia $czasie,$ w posortowanej tablicy jeśli klucze były dobrze rozłożone podczas

Obydwa algorytmy zostały wynalezione pod koniec lat 80. XX wieku przez prof. Thomasa A. Standisha z Uniwersytetu Kalifornijskiego w Irvine .

Przegląd

Podstawowa strategia

Ogólnie: Biorąc pod uwagę tablicę A z n kluczami:

zamapuj klucz na podtablicę docelowej tablicy A2 , stosując funkcję map key do każdego elementu tablicy
określić, ile kluczy będzie mapowanych na tę samą podtablicę, używając tablicy „liczby trafień”, H
określić, gdzie zaczyna się każda podtablica w tablicy docelowej, tak aby każdy segment miał dokładnie taki rozmiar, aby pomieścić wszystkie klucze, które będą do niego mapowane, używając tablicy „proxmap”, P
dla każdego klucza oblicz podtablicę, na którą będzie on mapowany, używając tablicy „lokalizacji”, L
dla każdego klawisza sprawdź jego lokalizację i umieść go w tej komórce A2 ; jeśli koliduje z klawiszem znajdującym się już na tej pozycji, wstawienie go sortuje na miejsce, przesuwając klawisze większe od tego klawisza o jeden w prawo, aby zrobić miejsce dla tego klawisza. Ponieważ podtablica jest wystarczająco duża, aby pomieścić wszystkie przypisane do niej klucze, taki ruch nigdy nie spowoduje przepełnienia kluczy do następnej podtablicy.

Wersja uproszczona: biorąc pod uwagę tablicę A z n kluczami

Inicjuj : Utwórz i zainicjuj 2 tablice o rozmiarze n : hitCount , proxMap i 2 tablice o długości A .length: lokalizacja i A2 .
Partycja : Używając starannie wybranej funkcji mapKey , podziel A2 na podtablice za pomocą kluczy w A
Rozproszenie : Przeczytaj A , wrzucając każdy klucz do odpowiedniego pojemnika w A2 ; sortowanie przez wstawianie według potrzeb.
Collect : Odwiedź podtablice w odpowiedniej kolejności i umieść wszystkie elementy z powrotem w oryginalnej tablicy lub po prostu użyj A2 .

Uwaga: „klucze” mogą również zawierać inne dane, na przykład tablicę obiektów Studenta, które zawierają klucz oraz identyfikator i imię ucznia. To sprawia, że ProxMapSort nadaje się do organizowania grup obiektów, a nie tylko samych kluczy.

Przykład

0 Rozważmy pełną tablicę: A [ do n-1 ] z n kluczami. Niech i będzie indeksem A. Posortuj klucze A w tablicę A2 o jednakowym rozmiarze.

Funkcja klucza mapy jest zdefiniowana jako mapKey(key) = Floor(K).

Tablica tablicowa
A1	6.7	5.9	8.4	1.2	7.3	3.7	11,5	1.1	4.8	0,4	10,5	6.1	1.8
H	1	3	0	1	1	1	2	1	1	0	1	1
P	0	1	-9	4	5	6	7	9	10	-9	11	12
L	7	6	10	1	9	4	12	1	5	0	11	7	1
A2	0,4	1.1	1.2	1.8	3.7	4.8	5.9	6.1	6.7	7.3	8.4	10,5	11,5

Pseudo kod


   0   

      0

   0   

      
        


  0 // oblicz liczbę trafień  dla  i  =  do  11  // gdzie 11 to n  {  H  [  i  ]  =  ;  }  for  i  =  do  12  // gdzie 12 to A.length  {  pos  =  MapKey  (  A  [  i  ]  );  H.  [  poz.  ]  =  H.  [  poz.  ]  +  1  ;  }  bieganie Razem  =  ;  
   0  
       0
          
    
          
            

   0   // oblicz mapę przybliżoną – lokalizację początku każdej podtablicy  dla  i  =  do  11  if  H  [  i  ]  =  P  [  i  ]  =  -  9  ;  else  P  [  i  ]  =  łącznie  ;  runningTotal  =  runningTotal  +  H  [  i  ]  ;  dla  i  =  do  12  
      

   0   
      
   0    // oblicz lokalizację – podtablicę – w A2, w której ma zostać umieszczony każdy element z A  L  [  i  ]  =  P  [  MapKey  (  A  [  i  ]  )  ]  ;  dla  I  =  do  12  ;  // sortuj elementy  A2  [  I  ]  =  <  pusty  >  ;  for  i  =  to  12  // wstaw każdy element do podtablicy, zaczynając od początku, zachowując porządek 

       
       
                  
    
            {  początek  =  L  [  ja  ]  ;  // podtablica dla tego elementu zaczyna się w tym miejscu  wstawka  made  =  false  ;  for  j  =  start  to  (  <  znaleziono  koniec  A2  i  nie  dokonano  wstawienia  >  )  {  if  A2  [  j  ]  ==  <  pusty  >  _  _  _  _  
              
               
             
                  
              // jeśli podtablica jest pusta, po prostu umieść element na pierwszej pozycji podtablicy  A2  [  j  ]  =  A  [  i  ]  ;  dokonano  wstawienia  =  true  ;  w przeciwnym  razie  A  [  i  ]  <  A2  [  j  ]  // klucz należy do A2[j]  int  end  =  j  +  1  ;  // znajdź koniec używanej części podtablicy – gdzie pierwsza <pusta> to  while  (  A2   
                
                   
                  
                  
                [  koniec  ]  !  =  <pusty>  )  koniec  ++  ;  _  for  k  =  end  -  1  do  j  // przesuń większe klawisze w prawo 1 komórka  A2  [  k  +  1  ]  =  A2  [  k  ]  ;  A2  [  jot  ]  =  ZA  [  ja  ]  ;  dokonano  wstawienia  =  true  ;  
    
 // dodaj nowy klucz  }  }

Tutaj A jest tablicą do posortowania, a funkcje mapKey określają liczbę używanych podtablic. Na przykład podłoga(K) po prostu przypisze tyle podtablic, ile jest liczb całkowitych z danych w A . Dzielenie klucza przez stałą zmniejsza liczbę podtablic; Do tłumaczenia zakresu elementów w A na podtablice można używać różnych funkcji, na przykład konwertując litery A – Z na 0–25 lub zwracając pierwszy znak (0–255) w celu sortowania ciągów. Podtablice są sortowane w miarę napływania danych, a nie po umieszczeniu wszystkich danych w podtablicy, jak to jest typowe w przypadku sortowania segmentowego .

Wyszukiwanie Proxmapy

ProxmapSearch wykorzystuje tablicę proxMap wygenerowaną przez wcześniej wykonane ProxmapSort, aby znaleźć klucze w posortowanej tablicy A2 w stałym czasie.

Podstawowa strategia

Sortuj klucze za pomocą ProxmapSort, zachowując funkcję MapKey oraz tablice P i A2
Aby wyszukać klucz, przejdź do P[MapKey(k)], początku podtablicy zawierającej klucz, jeśli ten klucz znajduje się w zestawie danych
Przeszukuj sekwencyjnie podtablicę; jeśli klucz zostanie znaleziony, zwróć go (i powiązane informacje); jeśli znajdziesz wartość większą niż klucz, klucza nie ma w zestawie danych
$Obliczanie$ ( k)] Jeśli podczas sortowania użyto klucza mapy, który zapewnia dobry rozkład kluczy, każda podtablica jest ograniczona powyżej stałą c , więc potrzebne jest co najwyżej c porównań, aby znaleźć klucz lub wiedzieć, że go nie ma; dlatego ProxmapSearch to . ${\ displaystyle O (1)}$ . Jeśli użyto najgorszego klucza mapy, wszystkie klucze znajdują się w tej samej podtablicy, więc ProxmapSearch w tym najgorszym przypadku będzie wymagać ${\ displaystyle O (n)}$ .

Pseudo kod

     funkcja  mapKey(key)  zwraca  piętro(key) proxMap ← wcześniej wygenerowana tablica proxmap o rozmiarze n A2 ← wcześniej   posortowana

    
        
             tablica o rozmiarze n  funkcja  proxmap-search(key)  jest  dla  i = proxMap[mapKey(key)]  do  długości(tablica ) − 1  wykonaj  , jeśli  sortedArray[i].key == klucz,  a następnie  zwróć  sortedArray[i]

Analiza

Wydajność

$H ,$ P i zajmuje Każde z nich jest obliczane podczas jednego przejścia przez tablicę, przy stałym czasie spędzonym w każdej lokalizacji tablicy.

$czasem$ co skutkuje standardowym sortowaniem przez wstawianie
Najlepszy przypadek: MapKey dostarcza tę samą małą liczbę elementów do każdej podtablicy w kolejności, w której występuje najlepszy przypadek sortowania przez wstawianie. Każde sortowanie przez $wstawianie$ _ istnieje p podtablic, zatem p * c = n , więc faza wstawiania zajmuje O(n); zatem $_$ _
Przypadek przeciętny: każda podtablica ma co najwyżej rozmiar c , będący stałą; sortowanie przez wstawianie dla każdej podtablicy wynosi wówczas w najgorszym wypadku O(c^2) – stała. (Rzeczywisty czas może być znacznie lepszy, ponieważ c przedmiotów nie jest sortowanych, dopóki ostatni przedmiot nie zostanie umieszczony w wiadrze). Całkowity czas to liczba segmentów (n/c) , razy ${\ displaystyle O (c ^ {2})}$ = ${\ displaystyle O (n)}$ .

Aby uniknąć najgorszego przypadku, konieczne jest posiadanie dobrej funkcji MapKey. Aby znaleźć dobry klucz, musimy wiedzieć coś o rozkładzie danych.

Optymalizacje

Oszczędzaj czas: Zapisz wartości MapKey(i), aby nie trzeba było ich ponownie obliczać (tak jak w powyższym kodzie)
Oszczędź miejsce: proxMaps można przechowywać w tablicy hitCount, ponieważ po obliczeniu proxmapy nie są potrzebne liczniki trafień; dane można posortować z powrotem do A, zamiast używać A2, jeśli zwrócimy uwagę, które wartości A zostały dotychczas posortowane, a które nie.

Implementacja kodu JavaScript:

  

     0
     
      
      
       Tablica  .  prototyp  .  ProxmapSort  =  funkcja  ()  {  //-- Data edycji: 2019/11/13 Tajwan --//  var  start  =  ;  var  koniec  =  to  .  długość  ;  var  A2  =  nowa  tablica  (  koniec  );  var  MapKey  =  nowa  tablica  (  koniec  );  var  hitCount  =  nowa  tablica  ( 
  
              0 
     
     
         koniec  );  for  (  var  i  =  początek  ;  i  <  koniec  ;  i  ++  )  {  hitCount  [  i  ]  =  ;  }  var  min  =  to  [  początek  ];  var  max  =  to  [  start  ];  for  (  var  i  =  początek  +  1  ;  i  <    
            
             
  
  
     koniec  ;  ja  ++  )  {  if  (  to  [  ja  ]  <  min  )  {  min  =  to  [  ja  ];  }  else  {  if  (  to  [  ja  ]  >  max  )  {  max  =  to  [  ja  ];  }}  }  //Optymalizacja 1.Zapisz klucz MapKey[i].  dla  (  var  i        
                  
    
   =  początek  ;  ja  <  koniec  ;  i  ++  )  {  MapKey  [  i  ]  =  Matematyka  .  piętro  (((  to  [  i  ]  -  min  )  /  (  max  -  min  ))  *  (  koniec  -  1  ));  hitCount  [  Klucz mapy  [  i  ]]  ++  ;  } 
  
      
          
         //Optymalizacja sklepu 2.ProxMaps w hitCount.  hitCount  [  koniec  -  1  ]  =  koniec  -  hitCount  [  koniec  -  1  ];  for  (  var  i  =  koniec  -  1  ;  i  >  początek  ;  i  --  ){  hitCount  [  i  -  1  ]  =  hitCount  [  i  ]  -  hitCount 
  
  
     0
     0
           
      
      
     [  i  -  1  ];  }  //wstaw A[i]=this[i] do A2 poprawną pozycję  var  wstawIndex  =  ;  var  wstawStart  =  ;  for  (  var  i  =  początek  ;  i  <  koniec  ;  i  ++  )  {  wstawIndex  =  hitCount  [  MapKey  [  i  ]];  wstawStart  =  wstawIndeks  ;  chwila       
            
        
       (  A2  [  wstawindeks  ]  !=  null  )  {  wstawindeks  ++  ;  }  while  (  wstawIndeks  >  wstawStart  &&  this  [  i  ]  <  A2  [  wstawIndeks  -  1  ])  {  A2  [  wstawIndeks  ]  =  A2  [  wstawIndeks  -  1  ];  wstawindeks-  ;  _ 
    
      
  
               
 }  A2  [  insertIndex  ]  =  this  [  i  ];  }  for  (  var  i  =  początek  ;  i  <  koniec  ;  i  ++  )  {  this  [  ja  ]  =  A2  [  ja  ];  }  };

Porównanie z innymi algorytmami sortowania

Ponieważ ProxmapSort nie jest sortowaniem porównawczym , dolna granica Ω( n log n ) nie ma zastosowania. ^{[ potrzebne źródło ]} Jego szybkość można przypisać temu, że nie opiera się na porównaniach i używa tablic zamiast dynamicznie przydzielanych obiektów i wskaźników, których należy przestrzegać, tak jak ma to miejsce w przypadku korzystania z drzewa wyszukiwania binarnego .

ProxmapSort pozwala na wykorzystanie ProxmapSearch. Pomimo czasu $kompilacji$ O (n), ProxMapSearch nadrabia to średnim czasem dostępu, co czyni go bardzo atrakcyjnym w przypadku Jeśli dane nie muszą być często aktualizowane, czas dostępu może sprawić, że ta funkcja będzie bardziej korzystna niż inne sortowanie oparte na sortowaniu bez porównania .

Ogólne sortowanie segmentów powiązane z ProxmapSort

Podobnie jak ProxmapSort, sortowanie segmentowe zazwyczaj działa na liście n danych wejściowych numerycznych od zera do pewnego maksymalnego klucza lub wartości M i dzieli zakres wartości na n segmentów, każdy o rozmiarze M / n . Jeśli każdy segment jest sortowany przy użyciu sortowania przez wstawianie , można wykazać, że ProxmapSort i sortowanie segmentowe działają w przewidywanym czasie liniowym. ^{[ oryginalne badania? ]} Jednak wydajność tego rodzaju spada w przypadku klastrowania (lub zbyt małej liczby segmentów ze zbyt dużą liczbą kluczy). jeśli wiele wartości występuje blisko siebie, wszystkie zostaną wrzucone do jednego pojemnika, a wydajność zostanie poważnie zmniejszona. To zachowanie dotyczy również ProxmapSort: jeśli segmenty są zbyt duże, jego wydajność znacznie się pogorszy.

^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sekcja 8.4: Sortowanie kubełkowe, s. 174–177.

Thomas A. Standish. Struktury danych w Javie. Addison Wesley Longman, 1998. ISBN 0-201-30564-X . Sekcja 10.6, s. 394–405.
Standish, Tajlandia; Jacobson, N. (2005). „Używanie sortowania $O (n)$ Proxmap i $O (1)$ wyszukiwania Proxmap w celu motywowania uczniów CS2 (część I)”. Biuletyn ACM SIGCSE . 37 (4). doi : 10.1145/1113847.1113874 .
Standish, Teksas; Jacobson, N. (2006). „Używanie sortowania $O (n)$ Proxmap i $O (1)$ wyszukiwania Proxmap w celu motywowania uczniów CS2, część II”. Biuletyn ACM SIGCSE . 38 (2). doi : 10.1145/1138403.1138427 .
Norman Jacobson „Streszczenie ProxmapSort i ProxmapSearch” z Wydziału Informatyki, Donald Bren School of Information and Computer Sciences , UC Irvine .

Linki zewnętrzne

[1] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sekcja 8.4: Sortowanie kubełkowe, s. 174–177.

Algorytmy sortowania
Teoria	Teoria złożoności obliczeniowej Notacja dużego O Całkowite zamówienie Listy Umieszczenie Stabilność Sortowanie porównawcze Sortowanie adaptacyjne Sieć sortowania Sortowanie całkowite Sortowanie X + Y Model transdychotomiczny Sortowanie kwantowe
Rodzaje wymiany	Sortowanie bąbelkowe Rodzaj shakera do koktajli Rodzaj nieparzysty – parzysty Sortowanie grzebieniowe Rodzaj gnoma Sortowanie z rozciąganiem proporcjonalnym Szybkie sortowanie Powolne sortowanie Rodzaj stooge'u Bogosort
Sortowanie przez wybór	Sortowanie przez wybór Sortowanie na stosie Gładkie sortowanie Sortowanie drzew kartezjańskich Rodzaj turnieju Sortowanie cykliczne Sortowanie według słabej sterty
Sortowanie przez wstawianie	Sortowanie przez wstawianie Sortowanie skorupowe Sortowanie Sortowanie drzew Sortowanie biblioteczne Sortowanie cierpliwości
Sortowanie przez scalanie	Sortowanie przez scalanie Sortowanie kaskadowe przez scalanie Sortowanie oscylacyjne przez scalanie Sortowanie przez scalanie wielofazowe
Rodzaje dystrybucji	Rodzaj flagi amerykańskiej Sortowanie koralików Sortowanie wiadro Sortowanie seryjne Sortowanie zliczające Sortowanie interpolacyjne Rodzaj szufladki Sortowanie Proxmapy Sortowanie radiacyjne Sortowanie błyskawiczne
Sortowanie współbieżne	Sortownik bitoniczny Sortowanie parzyste i nieparzyste wsadowe Sieć sortowania parami Sortowanie próbek
Rodzaje hybrydowe	Blokuj sortowanie przez scalanie Sortowanie Kirkpatricka – Reischa Timsort Wprowadzenie Sortowanie Sortowanie przez scalanie i wstawianie
Inny	Sortowanie topologiczne Porządek przedtopologiczny Sortowanie naleśników Rodzaj spaghetti