[Algorytmy] Mergesort - Problem przy sortowaniu

[nowik1991]

Witam

Chciałbym się dowiedzieć czy dobrze rozumiem ideę MergeSort.

Weźmy sobie dowolny zbiór \(\displaystyle{ A}\) który będzie wartościowany następująco: \(\displaystyle{ A=\left\{ 5,2,4,6,1,3,2,6\right\}}\) jest to zbiór 8-elementowy.

W myśl MargeSort po podzieleniu \(\displaystyle{ A/2}\) mamy dwa podzbiory 4 -elementowe nazwijmy je \(\displaystyle{ X}\) oraz \(\displaystyle{ Y}\). \(\displaystyle{ X=\left\{ 5,2,4,6\right\}}\) i \(\displaystyle{ Y=\left\{ 1,3,2,6\right\}}\) weźmy również jakiś zbiór \(\displaystyle{ Z}\) do którego będziemy wrzucać wyniki zatem porównujemy kolejno np \(\displaystyle{ 5}\) z \(\displaystyle{ 1}\) i nasza liczba \(\displaystyle{ 1}\) trafia do zbioru \(\displaystyle{ Z}\) potem \(\displaystyle{ 5}\) z \(\displaystyle{ 3}\) i \(\displaystyle{ 3}\) trafia do \(\displaystyle{ Z}\)...taki jest aż do porównania z liczbą \(\displaystyle{ 6}\) potem kolejno ze zbioru \(\displaystyle{ X}\) również są przepisywane do zbioru \(\displaystyle{ Z}\) do momentu \(\displaystyle{ 6=6}\) po tym zbiory się zerują i \(\displaystyle{ Z= \left\{ 1,3,2,5,2,4,6,6\right\}}\) i właśnie nie jest to posortowany ciąg czy mógłby ktoś powiedzieć mi o czym może zapomniałem czy też może źle to robię?

[Afish]

Masz dzielić zbiory tak długo, aż uzyskasz zbiory jednoelementowe.

[nowik1991]

Rozumiem...czyli taki kod w C++ mógłby załatwić dzielenie na /2 i sort?

Kod: Zaznacz cały

void merge(int array[], int start, int middle, int end) 
{
 
int *array_pom = new int[(end - start)];// utworzenie tablicy pomocniczej
      int i = start, j = middle + 1, k = 0;
 
             while (i <= middle && j <= end) 
               {
                  if (array[j] < array[i]) 
                      {
                         array_pom[k] = array[j];
                                  j++;
                      }
                  else 
                      {
                       array_pom[k] = array[i];
                                 i++; 
                      }
                                k++;
}

Biorąc powyższy przykład działało by to tak:

A={ 5,2,4,6|1,3,2,6} | <--środek

array [j]=2<= array =5
array [j]=4<= array =5
array [j]=5<= array =6
array [j]=3<= array =1
array [j]=2<= array =3
array [j]=6<= array =3
następnie do array_pom = {2,4,5,6 |1,2,3,6} i co dalej?

[royas]

Czym innym jest merge, a czym innym merge_sort.
Samo merge daje ciąg posortowany tylko jeśli wejściowe ciągi były posortowane.
To co masz to jedynie merge. Potrzebujesz jeszcze procedury merge_sort, która podzieli daną tablicę na dwie, posortuje każdą z nich merge_sortem i "zmerdżuje" je (przy pomocy merge, które już masz) w posortowaną tablicę.
Np. na angielskiej Wikipedii jest prosta animacja, która to wyjaśnia.

[nowik1991]

To już się pogubiłem to ten mój kod do jakiego momentu dochodzi?

[royas]

Raczej OD jakiego. Twój kod daje posortowany ciąg, o ile oba wejściowe ciągi były posortowane. Jeśli nie były, to jak sam zauważyłeś nie daje nic sensownego. Musisz zadbać o to, żeby były posortowane PRZED ich merdżowaniem, czyli zanim je połączysz posortuj każdą z połówek. Na polskiej wiki masz na to pseudokod.
Zauważ, że pojedyncze elementy tablicy są posortowane.
Jeśli masz tablice \(\displaystyle{ t}\) osmioelementową, to łączysz
\(\displaystyle{ t[1]}\) z \(\displaystyle{ t[2]}\)
\(\displaystyle{ t[3]}\) z \(\displaystyle{ t[4]}\)
\(\displaystyle{ t[5]}\) z \(\displaystyle{ t[6]}\)
\(\displaystyle{ t[7]}\) z \(\displaystyle{ t[8]}\)

\(\displaystyle{ t[1..2]}\) z \(\displaystyle{ t[3..4]}\)
\(\displaystyle{ t[5..6]}\) z \(\displaystyle{ t[7..8]}\)

\(\displaystyle{ t[1..4]}\) z \(\displaystyle{ t[5..8]}\)

[nowik1991]

Skorzystałem z pomocy neta no i zauważyłem że w większości do mojego kodu dodane jeszcze jest

Kod: Zaznacz cały

if (i <= srodek) {
while (i <= srodek) {
tab_pom[k] = tablica[i];
i++;
k++;
}
}
else {
while (j <= koniec) {
tab_pom[k] = tablica[j];
j++;
k++;
}
}
 
for (i = 0; i <= koniec - start; i++)
tablica[start + i] = tab_pom[i];
 
cout << endl;
for (i = start; i <= koniec; i++)// wypisanie posortowanej tablicy
cout << "tablica[" << i << "] = " << tablica[i] << endl;
}

Jak dobrze sądzę to jest to przypisanie z tablicy pomocniczej do tablicy normalnej posortowanych elementow tak?

[royas]

Linie 16-17: tak. Ale dalej jest to jedynie merge, a nie merge_sort.