Sortowanie poprzez scalanie(Merge sort)

[SarKter]

Siedzę już nad tym kilka dni i nie mogę znaleźć błędu w kodzie. Zamiast poprawnego wyniku otrzymuję jakieś bzdury , nijak mające się do podanych liczb. Kompiluje w DEVie i nie mam pojęcia co jest źle.

#include <iostream>


using namespace std;

void Merge(int low, int mid, int high);

void MergeSort(int low, int high);

#define N 4


int tab[N] = {1,2,3,4}; //Tworzę tablicę z 4 elementami

int tab2[N]; // oraz tablicę pomocniczą


int main(int argc, char *argv[])

{

    MergeSort(0,N-1); //Wywołanie funkcji

    for(int i=0;i<N;i++) cout << tab[i] << "  "; //Wypisanie wyniku

    system("PAUSE");

    return 0;

}


void MergeSort(int low, int high)

{

 if(low<high) //Jeżeli > niż 1 element

 {

 int mid = (low+high)/2; //Podzielenie na dwie części

 MergeSort(low,mid); //Wywołanie sortowania dla dwóch części

 MergeSort(mid+1,high);

 Merge(low,mid,high);//Połączenie dwóch części

 }

}

void Merge(int low,int mid,int high)

{

int count1,count2,pos;//Zmienne potrzebne do kopiowania liczb

count1=low;

count2=mid+1;

pos = low;

 while(count1<=mid&&count2<=high)//Gdy oba zbiory mają liczby

 {

  if(tab[count1]<=tab[count2]) { tab2[pos]=tab[count1]; count1++; pos++; } //Jeżeli liczby z pierwszego zbioru są mniejsze, to następuje kopiowanie do tablicy pomocniczej i zwiększenie zmiennych

  else { tab2[pos]=tab[count2]; count2++; pos++; }// albo z drugiego

 }

 while(count1<=mid) //Kopiowanie reszty liczb do tablicy pomocniczej

 {

 tab2[pos]=count1; count1++; pos++;

 }

 while(count2<=high)

 {

 tab2[pos]=count2; count2++; pos++;

 }

for(int i=low;i<=high;i++) tab[i]=tab2[i]; //Skopiowanie liczb z tablicy pomocniczej do głównej

}

Proszę o pomoc!

[hixohe]

Witam,

Popracuj nad formatowaniem kodu - bo się tego czytać nie da.

Błąd masz w funkcji Merge konkretnie:

tab2[pos]=count2; count2++; pos++;

powinno być

tab2[pos]=tab[count2]; count2++; pos++;

i

tab2[pos]=count1; count1++; pos++;

powinno być

tab2[pos]=tab[count1]; count1++; pos++;

[[Ekspert] Hakken]

Problem znajduje sie w funkcji merge().

Na poczatku tej funkcji przepisz elementy z tablicy glownej do pomocniczej.

Glowna petla while - ok, natomiast to co robisz w tej petli, juz ok nie jest.

W "if-ie" musisz sprawdzic, ktora z rozpatrywanych liczb jest mniejsza, jednak robisz to na zlej tablicy.

Przepisujesz tez do zlej tablicy. (powinienes przepisywac to tab, nie tab2)

Ostatnie 2 petle w funkcji merge() tez sa niepotrzebne. Ten trzeci while, to nawet nie wiem co ma robic, a for nie bedzie potrzebny, bo bedziesz przepisywal do poprwanej tablicy.

EDIT:

doublekill ^^

I jeszcze jedno: po co pisac

tab2[pos]=tab[count1]; count1++; pos++;

skoro mozna napisac

tab2[pos++]=tab[count1++];

[hixohe]

I jeszcze jedno: po co pisac

tab2[pos]=tab[count1]; count1++; pos++;

skoro mozna napisac

tab2[pos++]=tab[count1++];

Dlatego, że taki zapis jest mniej czytelny i może prowadzić do pomyłek.

[[Ekspert] Hakken]

Mniej czytelny? kwestia przyzwyczajenia. Napewno szybszy.

I jeszcze jedna uwaga. zdecyduj sie na jeden jezyk. Najlepiej angielski. Bo z polowa zmiennych po polsku, a polowa po angielsku wygalda... dziwnie o.o

[SarKter]

Dzięki wielkie. Zaraz przepiszę i zobaczę co się będzie działo.

Edit: Napisałem to jeszcze raz, tak jak mi powiedzieliście - wszystko działa jak powinno. Dzięki;)

Mam jeszcze tylko jedno pytanie: w kodzie na samej górze były trzy pętle while, dwie ostatnie kopiowały resztę elementów, gdy jedna ze zmiennych count1 albo count2 osiągnęła maksimum.

Obecnie funkcja Merge wygląda tak:

void Merge(int low, int mid, int high)

{

for(int i=0;i<=high;i++) temp[i]=numbers[i];


int count1, count2, pos;


count1=low;

count2=mid+1;

pos=low;


 while(count1<=mid&&count2<=high)

 {

 if(temp[count1]<=temp[count2]) numbers[pos++]=temp[count1++];

 else numbers[pos++]=temp[count2++];

 }


 while(count1<=mid)

 {

 numbers[pos++]=temp[count1++];

 }

}

Nie rozumiem w jaki sposób druga część liczb(count2 do high) ulega skopiowaniu, gdy count1 osiągnie wartość mid(podczas trwania pierwszej pętli while), wtedy nic nie kopiuje tych liczb.

[[Ekspert] Hakken]

Spojrz na warunek w while, jest napisane

while(count1<=mid&&count2<=high)

Zwroc uwage na ampersant.

[SarKter]

Gdy będę scalać np. 3 1 5 4 to będzie to po chwili wyglądać tak:

Liczby A: 1 3

Liczby B: 4 5

Nowa lista: 1

Liczby A : 3

Liczby B : 4 5

Nowa lista: 1 3

Liczby A : puste

Liczby B: 4 5

I właśnie teraz nie wiem co się dzieje(warunek wtedy jest, po podstawieniu liczb, 2<=2&&3<=4 - czyli pętla jeszcze raz zadziała).

W przypadku, gdy np.:

Liczby A: 4

Liczby B: puste

to druga pętla while kopiuje pozostałe liczby z A. Znowu pewnie coś pokręciłem, ale tak mniej więcej to rozumiem.

[[Ekspert] Hakken]

tutaj jest ladny obrazek ilusturjacy "rozbijanie" tablicy:

http://upload.wikimedia.org/wikipedia/comm...thm_diagram.png

[SarKter]

Ok, dzięki wielkie:)