Odświeżanie algorytmu. Dlaczego heapsort jest algorytmem insortującym?

15

Nie rozumiem, dlaczego heapsort jest uważany za algorytm sortowania w miejscu .

Mam na myśli dodatkową strukturę danych zapełnioną elementami tablicy do sortowania, tj. Stertę, która jest używana do pomocy w wydobyciu wartości minimalnej i procesie sortowania.

Może więc nie rozumiem tutaj definicji miejsca na miejscu?

Ale na przykład rodzaj wstawiania jest oczywisty, że jest to algorytm zastępczy, tj. Nie jest wymagana dodatkowa pamięć dla elementów.

Więc dlaczego uważa się to za miejsce?

— użytkownik10326
źródło

12

Mam na myśli dodatkową strukturę danych zapełnioną elementami tablicy do sortowania, tj. Stertę, która jest używana do pomocy w wydobyciu wartości minimalnej i procesie sortowania.

Nie. Tablica jest przekształcana, aby była zgodna z ograniczeniem sterty bez użycia dodatkowej pamięci większej niż O (1). (W rzeczywistości wszystko, czego potrzebujesz, to dodatkowa pamięć wystarczająca do przechowywania jednego elementu tablicy do celów wymiany, a także wartość logiczna lub dwa oraz zmienna pętli lub dwa).

Ok, technicznie rzecz biorąc może się zdarzyć, że heapsort jest zwykle wyjaśniany jako użycie osobnej hałdy, ale można go zaimplementować na miejscu.

— Peter Taylor
źródło

3

Jedyne miejsce, w którym spodziewałbym się zobaczyć „stos rozsypisk” z oddzielną stertą (w kodzie), jest w funkcjonalnym języku, takim jak Haskell, z tego samego powodu, dla którego zwykły funkcjonalny „Quicksort” też nie jest na miejscu - funkcjonalni programiści, tacy jak ich list jest dużo, a sortowanie na miejscu jest stanowe - zmienia stan tablicy / cokolwiek zawierającego dane. Przerażające cytaty, ponieważ tak naprawdę nie akceptuję tego, że szybki zbiór poza miejscem jest w ogóle szybkim ruchem, lub że rozsypisko na miejscu jest w ogóle rozsypiskiem - przynajmniej nie bez wyraźnego stwierdzenia, że nie jest miejsce.

— Steve314,

1

@ Steve314, myślę, że widziałem jakiś materiał dydaktyczny, który mówi coś o efekcie „ułóż go na stosie, a następnie wyciągnij elementy pojedynczo i umieść je w tablicy”. Ale po sprawdzeniu CLR mogę zgłosić, że pokazują wersję lokalną.

— Peter Taylor

2

@PeterTaylor: Tak, książka, którą recenzowałem (Skiena) przedstawiła heapsort, budując dodatkową kupę.

— user10326,

4

Być może brakuje ci podstawowego zrozumienia, że do określenia układu drzewa można użyć tablicy.

Załóżmy, że masz drzewo binarne, a węzeł wewnętrzny znajduje się w indeksie i tablicy. Następnie indeks tablicy rodzica i potomków tego węzła można znaleźć:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Widzieć:

http://www.personal.kent.edu/~rmuhamma/Alameterms/MyAlgorithms/Sorting/heapSort.htm

Ponieważ stertę można przechowywać i organizować w całości w tablicy, heapsort może działać w miejscu, przesuwając elementy wewnątrz tablicy wejściowej. Rzeczywiście, sterta jest budowana i przetwarzana przy użyciu oryginalnej tablicy wejściowej.

— stackoverflowuser2010
źródło

: Wiem o tym. Wydaje się, że problem polega na tym, że książka, którą czytam, przedstawiała stertę za pomocą osobnej sterty. Nie zrozumiałem ani nie pomyślałem, że ta prezentacja miała ułatwić zrozumienie algorytmu (być może? Nie jestem pewien, dlaczego to był przedstawione w ten sposób)

— user10326,

Gorąco polecam zakup książki „Wprowadzenie do algorytmów” autorstwa Cormen i in. Wyraźnie odpowiada na wszystkie pytania związane z algorytmem. Jeśli poważnie myślisz o karierze jako informatyk lub inżynier oprogramowania, musisz mieć tę książkę.

— stackoverflowuser2010,

1

Jeśli, jak mówisz, naprawdę potrzebna jest dodatkowa struktura do zbudowania sterty, wówczas heapsort rzeczywiście NIE byłby algorytmem sortowania w miejscu.

Tak jednak nie jest. Możesz zbudować stertę na tej samej tablicy, którą chcesz posortować, a następnie zastosować algorytm heapsort, aby sortować na miejscu.

— Daniel Scocco
źródło

Zasadniczo istnieje algorytm „heapify”, który służy do zmiany kolejności danych w tablicy, tak aby była zgodna z regułami stosu w czasie O (n) IIRC. Zobacz pseudokod na programmers.stackexchange.com/questions/116904/… . Po tym głównie chodzi o powtarzanie wyciągów z korzenia sterty i śledzenie, ile macierzy jest nadal „stertą”, a ile posortowany wynik końcowy.

— Steve314,

0

W informatyce algorytm lokalny (lub łaciński in situ) to algorytm, który przekształca dane wejściowe przy użyciu struktury danych z małą, stałą ilością dodatkowej przestrzeni dyskowej. Dane wejściowe są zwykle nadpisywane przez dane wyjściowe podczas wykonywania algorytmu. Algorytm, który nie jest na miejscu, jest czasem nazywany „nie na miejscu” lub „na miejscu”.

Wikipedia - algorytm lokalny

— Rein Henrichs
źródło

Dlaczego zatem scalesort jest uważany za algorytm nie na miejscu?

— user10326,

3

To nie jest przydatna odpowiedź. Nie ma to nic wspólnego z heapsortem i nie odpowiada na pytanie.

— stackoverflowuser2010

Oczywiście ma to coś wspólnego z heapsortem. Heapsort jest algorytmem sortowania na miejscu, co powinno wynikać z definicji. W rzeczywistości był to link ze strony heapsortu.

— Rein Henrichs,

0

Uważa się, że jest na miejscu, ponieważ jego wymagania dotyczące miejsca są znikome (stałe lub wcale, jeśli używasz operacji bitowych do zamiany przedmiotów). Na przykład MergeSort nie istnieje, ponieważ zestaw danych wejściowych nie jest modyfikowany w każdej iteracji przykładu wyszukiwania.

Najlepszym sposobem zilustrowania różnic między algorytmami lokalnymi i algorytmami zewnętrznymi jest prawdopodobnie sprawdzenie następującego kodu odwracającego łańcuch C / C ++, który to robi (z K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Jeśli na przykład odczytujesz łańcuch wejściowy od końca i umieszczasz znaki w innym buforze, byłby to algorytm odwracania łańcucha na nie na miejscu.

— rdasxy
źródło

1

Mergesort jest cholernie denerwujący - łatwo jest błędnie przekonać się, że masz strategię na miejscu. Zwykle działa tylko w przypadku małych tablic. Myślę jednak, że pobrałem papierze raz, gdy ktoś zrobił wypracować wariantu w miejscu algorytmu sortowania korespondencji seryjnej. Zobaczę, czy uda mi się go jeszcze znaleźć.

— Steve314,