Avatar billede kar Nybegynder
07. oktober 2002 - 18:23 Der er 7 kommentarer og
1 løsning

Quicksort

Hej alle!
Mit program skal kunne sorterer et array i størrelsesorden efter pricippet "opdel", hvor arrayet hele tiden bliver opdelt i mindre bidder. De mindre tal før privot tallet og de større tal efter osv.
Mit problem er at programmet udskriver arrayet som flg: 47 33 24 13 8 6 7 23 - imens jeg gerne vil have en udskrift der er : 6 7 8 1
23 24 33 47
Hvad er forkert?
På forhånd tak
Hilsner karina

mit program ser ud som flg:

#include <iostream>
#include <conio>
using namespace std;

void ombyt(int &n, int &m);

int opdel(int arr[], int startIx, int SlutIx);

void quick(int arr[], int startIx, int slutIx);

void skriv(const int t[], int v, int h);

int main()
{
int arr[]={23,7,13,24,6,47,8,33};

skriv(arr, 0, 7);
quick(arr, 0, 7);
skriv(arr, 0, 7);

cout<< "tryk paa en tast";
getch();

return 0;
}

void ombyt(int &n, int &m)
{
int gem=n;
n=m;
m=gem;
}
int opdel(int arr[], int startIx, int slutIx)
{
  int opIx=startIx, nedIx=slutIx;

  do
  {
  opIx++;
  while (opIx<slutIx && arr[opIx]<=arr[startIx])
  opIx++;
  while (arr[nedIx]<arr[startIx])
  nedIx--;
  if(opIx<nedIx)    //her
  ombyt(arr[opIx], arr[nedIx]);
  }
  while (opIx<=nedIx);
  ombyt(arr[startIx], arr[nedIx]);
  return nedIx;
}

void quick(int arr[], int startIx, int slutIx)
{
if (startIx<slutIx)
{
int pivotIx;
pivotIx=opdel(arr, startIx, slutIx);
skriv(arr, startIx, slutIx);
quick(arr, startIx, slutIx-1);
quick(arr, pivotIx+1, slutIx);
}
}

void skriv(const int t[], int v, int h)
{
for (int i=0; i<8; i++)
{
if(i<v || i>h) cout <<"  ";
else          cout <<(t[i]>9?"":" ") <<t[i];
cout <<(i==7?'\n':' ');
}
}
Avatar billede erikjacobsen Ekspert
07. oktober 2002 - 18:48 #1
Er din betingelse ikke forkert:

  if(opIx<nedIx)    //her

Du skal nødvendigvis kigge på indholdet af arrayet - ikke
indexerne - for at afgøre om du skal bytte elementerne.
Avatar billede chries Nybegynder
08. oktober 2002 - 09:14 #2
alle ændringer skulle være makeret med // RETTELSE

#include <iostream>
#include <conio.h>
using namespace std;

void ombyt(int &n, int &m);

int opdel(int arr[], int startIx, int SlutIx);

void quick(int arr[], int startIx, int slutIx);

void skriv(const int t[], int v, int h);

int main()
{
    int arr[]={23,7,13,24,6,47,8,33};

    skriv(arr, 0, 7);
    quick(arr, 0, 7);
    skriv(arr, 0, 7);

    cout<< "tryk paa en tast";
    getch();

    return 0;
}

void ombyt(int &n, int &m)
{
    int gem=n;
    n=m;
    m=gem;
}

int opdel(int arr[], int startIx, int slutIx)
{
    int opIx=startIx, nedIx=slutIx;

      while(opIx < nedIx)    // RETTELSE
    {
        opIx++;
 
        while (arr[opIx]<=arr[startIx]) // RETTELSE
            opIx++;
 
        while (arr[nedIx]>arr[startIx]) // RETTELSE
            nedIx--;
 
        if(opIx<nedIx)    //her
            ombyt(arr[opIx], arr[nedIx]);
    }

    ombyt(arr[startIx], arr[nedIx]);
 
    return nedIx;
}

void quick(int arr[], int startIx, int slutIx)
{
    if (startIx<slutIx)
    {
        int pivotIx;
       
        pivotIx=opdel(arr, startIx, slutIx);

        skriv(arr, startIx, slutIx);

        quick(arr, startIx, pivotIx-1); // RETTELSE
        quick(arr, pivotIx+1, slutIx);
    }
}


void skriv(const int t[], int v, int h)
{
    for (int i=0; i<8; i++)
    {
        if(i<v || i>h)
            cout <<"  ";
        else         
            cout <<(t[i]>9?"":" ") <<t[i];

        cout <<(i==7?'\n':' ');
    }
}
Avatar billede soepro Nybegynder
08. oktober 2002 - 09:40 #3
Du har lavet en grundlæggende fejl i qsort algoritmen og din opdel() metode. Princippet i en qsort er at opdele data-sættet et eller andet sted (pivot'en), og så sørge for at alle elementer til venstre for dette sted er MINDRE og alle elementer til højre er STØRRE en elementet på stedet.

En almindelig teknik til at sikre dette, er at vælge det element der ligger i midten at tabellen og så bytte med elementer fra venstre side, som er større end midten. Derefter at gøre det samme med højre side. Dette gentages indtil der er byttet rundt så pivot'en opfylder ovenstående.

Din qsort metode skal derfor se sådan her ud:
Avatar billede kar Nybegynder
08. oktober 2002 - 09:51 #4
Hej Chris!
Dit svar hjalp.
Hilsner karina
Avatar billede soepro Nybegynder
08. oktober 2002 - 10:18 #5
void quick(int arr[], int startIx, int slutIx)
{
  int opIx=startIx, nedIx=slutIx, pivot;

  if (startIx >= slutIx)
    return;

  pivot = opIx + (slutIx - startIx) / 2; // A* Find pivot i stf. opdel

  while (opIx < nedIx)
  {
    // B* Ingen optælning af opIx her.
    while (opIx < pivot && arr[opIx] <= arr[pivot]) // C* Kun op til pivot'en
      opIx++;
    while (arr[nedIx] > arr[pivot])
      nedIx--;

    if (opIx < nedIx)
    {
      ombyt(arr[opIx], arr[nedIx]);

      // D* Flyt pivot til nye plads, hvis pivot blev ombyttet.
      if (pivot == opIx)
        pivot = nedIx;
      else
        if (pivot == nedIx)
          pivot = opIx;
    };
  };

  // Nu står 'pivot' korrekt.
  skriv(arr, startIx, slutIx);

  /* Så skal venstre og højre side sorteres. */
  quick(arr, startIx, pivot - 1);
  quick(arr, pivot + 1, slutIx);
}

Du skal bemærke følgende ændringer:

A* Pivot vælges simpelthen som det midterste element.
B* opIx må IKKE tælles op uden for while løkken.
C* opIx må ikke overstige pivot'en indeks
D* Indeks på pivot'en skal justeres hvis ombytningen "ramte" pivot'en.

Jeg har lagt ovenstående ind i dit program, og så kører det.
Avatar billede soepro Nybegynder
08. oktober 2002 - 10:24 #6
Schade, der var jeg åbenbart ikke hurtig nok !!! (Tja, sådan kan det gå, når man gerne vil lave noget der virker.)
Avatar billede kar Nybegynder
08. oktober 2002 - 10:57 #7
hej soepro!
kan du så ikke skrive noget med et "svar", jeg vil meget gerne give dig point også.
hilsner karina
ps for det er jo altid rart at der er nogle som gider hjælpe
Avatar billede soepro Nybegynder
08. oktober 2002 - 11:45 #8
Jotak som byder - men man kan ikke svare på denne her mere.
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