Czy można uniknąć kroku „dzielenia” w rodzaju scalania?

13

Scal sortowanie

Więc scalanie to algorytm dzielenia i zdobywania. Kiedy patrzyłem na powyższy schemat, zastanawiałem się, czy można w zasadzie ominąć wszystkie kroki podziału.

Jeśli iterowałeś po oryginalnej tablicy podczas przeskakiwania o dwa, możesz uzyskać elementy o indeksie i i i + 1 i umieścić je w ich własnych sortowanych tablicach. Po uzyskaniu wszystkich tych pod-tablic ([7,14], [3,12], [9,11] i [2,6], jak pokazano na schemacie), możesz po prostu przejść do normalnej procedury scalania, aby uzyskać posortowana tablica.

Czy iteracja po tablicy i natychmiastowe generowanie wymaganych pod-macierzy jest mniej wydajne niż wykonywanie kroków podziału w całości?

algorithms sorting efficiency mergesort Jimmy_Rustle
źródło
Powiązane: cs.stackexchange.com/questions/77075/…
Omar

Odpowiedzi:

29

Pomyłka wynika z różnicy między koncepcyjnym opisem algorytmu a jego implementacją .

Logiczne scalanie sortowania jest opisywane jako podział tablicy na mniejsze tablice, a następnie scalenie ich z powrotem. Jednak „dzielenie tablicy” nie oznacza „tworzenia całkowicie nowej tablicy w pamięci” lub czegoś podobnego - można ją zaimplementować w kodzie jako

/*
 * Note: array is now split into  [0..n) and [n..N)
 */

tzn. nie ma miejsca żadna faktyczna praca, a „podział” jest czysto koncepcyjny. To, co sugerujesz, z pewnością działa, ale logicznie nadal „dzielisz” tablice - po prostu nie potrzebujesz do tego żadnej pracy z komputera :-)

psmears
źródło
4
Osobiście bardzo podoba mi się sortowanie metodą scalania od dołu do góry, ponieważ jest łatwiejsze do wdrożenia w sposób, który pozwala uniknąć przydzielania bufora tymczasowego na każdym poziomie rekurencji. Zamiast tego przydzielasz bufor raz i ping-pong między nimi.
maniak zapadkowy
To - dzielenie jest obliczeniowo nieobsługiwane ... plus sugestia PO to tylko wprowadzenie odpowiednika połączenia tablic jednoelementowych i rozpoczęcie używania scalania od drugiego kroku, co wydaje się zbędne, ponieważ oryginalne scalanie działa równie dobrze. Optymalizacja tego nie ma sensu. Wprowadza tylko zbędne koncepcje i logikę.
luk32
@ratchetfreak: Ja też to uwielbiam, ale niestety nie jest to równoważne odgórnemu (przynajmniej wersja, którą znam). Scalenie wykona się inaczej, w zasadzie zaokrąglając w górę do następnej długości macierzy potęgi-2, co moim zdaniem może być nawet nieco wolniejsze. Czy znasz wersję oddolną, która łączy dokładnie to samo, nie ponosząc przy tym dużych kosztów?
user541686,
@Mehrdad jedynym prawdziwym problemem jest mały ogon, który musi zostać scalony. W najgorszym przypadku oznacza to kolejne przejście do połączenia w jeden element dla tablic długości 1<<n+1. Chociaż jestem pewien, że możesz dostosować rzeczy, aby zbyt mały ogon wtapiał się w dolne przejście.
Ratchet Freak
@psmears „po prostu nie potrzebujesz do tego żadnej pracy z komputera” - więc przypuszczam, że koszt wydajności n wywołań funkcji rekurencyjnej podziału (7 wywołań na przykładowym schemacie) jest w zasadzie nieistotny?
Jimmy_Rustle,
11

Myślę, że masz na myśli implementację oddolną . W implementacji oddolnej zaczynasz od elementów pojedynczej komórki, przesuwając się w górę, łącząc elementy w większe posortowane listy / tablice. Wystarczy odwrócić strzałki na powyższym rysunku, zaczynając od środkowej tablicy, tj. Tablic jednoelementowych.

Możesz także zoptymalizować sortowanie przez scalanie , dzieląc tablice, aż osiągną pewien stały rozmiar, a następnie po prostu posortuj je, używając na przykład sortowania wstawianego.

W przeciwnym razie sortowanie bez podziału tablicy nie jest możliwe. W rzeczywistości istotą sortowania scalającego jest dzielenie i sortowanie podcieni, tj. Dzielenie i podbijanie.

fade2black
źródło