Avatar billede dehdar Nybegynder
04. april 2008 - 12:59 Der er 7 kommentarer og
1 løsning

merge() funktion

Hej, er der nogen som kan spotte en fejl i min merge() funktion? Meningen er, at jeg skal sortere mit data-array således, at alle tal står i stigende orden. Det jeg gør er at flytte indholdet af mit data-array over i et temp-array, hvorefter jeg gemmer alt hvad jeg har i temp-array over i data-array igen. Problemet er, at det ikke virker efter hensigten, eftersom jeg ikke får sorteret tallene korrekt.




void merge(int data[], size_t n1, size_t n2)
{
    size_t p1;
    size_t p2;

    if( n1 == n2 )
    {
        p1 = 0;
        p2 = n1;
    }
    else
    {
        p1 = 0;
        p2 = ( n1 + 1 );
    }
   
    int* tempData;
    tempData = new int [n1 + n2];

    for( int i = 0; i < ( n1 + n2  ); i++ )
    {
        if( ((data[p1] < data[p2]) && (p1 != n1)) || ((p1 != n1) && (p2 == n2+n1)) )
        {
            tempData[i] = data[p1];
            p1++;
        }
        else if( ((data[p1] > data[p2]) && (p2 != (n2 + n1))) || ((p2 != (n2+n1)) && (p1 == n1)) )
        {
            tempData[i] = data[p2];
            p2++;
        }
        else
        {
            tempData[i] = data[p1];
            p1++;       
        }
    }

    for( int i = 0; i < (n1 + n2); i++ )
    {
        data[i] = tempData[i];
    }

    delete []tempData;
}
Avatar billede soerenlyn Nybegynder
04. april 2008 - 13:34 #1
Jeg forstår ikke helt måden du implementerer din Merge-Sort ... Hvad angiver n1, n2, p1 og p2??

Merge-Sort fungerer på følgende måde:
1) Merge-Sort modtager et array.
2) Den deler det op i midten og kalder sig selv rekursivt på begge dele.
3) Den merger (fletter) de to sorterede arrays den modtager fra de rekursive kald.

Jeg håber det kan hjælpe dig lidt. Jeg er ikke C++-programmør, men jeg kan lige se på om jeg kan implementere det :)
Avatar billede segmose Nybegynder
04. april 2008 - 13:46 #2
Forusætning: For at det kan virke skal de 2 dele af arrayet være sorteret i stigende orden allerede.

p2 = ( n1 + 1 ); <---- hvorfor dette?

ellers bør den indre betingelse nok omskrives til noget lettere hvis der ikke er tale om at sortere unike objekter.

for( int i = 0; i < ( n1 + n2  ); i++ ) {
  if( ((data[p1] <= data[p2]) && (p1 != n1)) ||
      (p2 == n2+n1) ) { // slut på del 2.
    tempData[i] = data[p1];
    p1++;
  } else {
    // hvis den ikke er mindre eller lig med så er den større, eller del 1 er slut.
    tempData[i] = data[p2];
    p2++;
  }
}
Avatar billede soerenlyn Nybegynder
04. april 2008 - 13:53 #3
Noget pseudo-kode-agtigt kan lyde sådan:

void merge(int data[])
{
    int len = data.length       
    int split = round(len / 2);

    int part1[] = data[0..split];
    int part2[] = data[split+1..len-1];

    part1[] = merge(part1[]);
    part2[] = merge(part2[]);


    int res = p1 = p2 = 0;
    int result[len-1];

    while(p1!=split && p2!=len-1){
        if(p1<=p2){
            result[res] = p1;
            p1++;
            res++;
        }else{
            result[res] = p2;
            p2++;
            res++;
        }
    }

    if(p1 == split){
        while(p2!=len-1){
            result[res] = p2;
            res++;
        }
    }else if(p2 == len-1){
        while(p1!=split){
            result[res] = p1;
            res++;
        }
    }

    data[] = result[];
}
Avatar billede soerenlyn Nybegynder
04. april 2008 - 13:55 #4
Muligvis vil der være lidt problemer i basis-tilfældet hvor data.length == 1... men tror det burde virke :)
Avatar billede dehdar Nybegynder
04. april 2008 - 14:17 #5
soerenlyn:

Tak for din interesse. Jeg har fået det til at virke nu. Jeg sætter lige implementeringen ind, så du kan se, hvordan jeg gør.

void mergesort(int data[], size_t n)

  size_t n1;  // size of the first subarray
  size_t n2;  // size of the second subarray
 
  if (n > 1)
  { 
      n1=n/2; 
      n2=n-n1;

      mergesort(data,n1);
      mergesort(data+n1, n2);

      merge(data, n1, n2);
  }
}

segmose:

Efter jeg satte p2 = n1, så virker det :) Jeg tænkte at hvis arrayet var af ulige størrelse, så skulle dette problem håndteres, men... ja det gav ikke nogen mening alligevel :) Tak for hjælpen.
Avatar billede soerenlyn Nybegynder
04. april 2008 - 14:19 #6
Jeps .. mangler du ikke at runde n1 op eller ned? Hvis nu længden er ulige .. Koden er også kun så kort fordi at merge-funktionen gør alt arbejdet :)
Avatar billede dehdar Nybegynder
04. april 2008 - 19:59 #7
Det var også det jeg havde tænkt til at starte med, men det er ikke nødvendigt for selvom n1 og n2 ikke er lig hinanden, så kører min for løkke jo n1+n2 gange. Jeg skal bare sørge for, at min "pegepind" p1 går fra plads 0 til plads n1 og at min pegepind p2 starter fra n1 og går til n1 + n2.

n = 13;
n1 = 13 / 2 = 6
n2 = n - n1 = 13 - 6 = 7

p1 går fra 0 til 6 (n1)
p2 går fra 6 (n1) til 13 (n1 + n2)
Avatar billede soerenlyn Nybegynder
05. april 2008 - 10:37 #8
Yes yes, men det er fordi a 13 / 2 = 6 ... Det er jo 6½, og så vil det ikke fungere helt ... Men godt det virker :)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester