problem z quick sort

Question

Witam, w celu pocwiczenia programowania postanowilem samemu napisac w/w algorytm, tak dla lepszego zrozumienia tematu. Program dziala jednak nie dla wszystkich konfiguracji liczb, dla liczb: 9,5,7,0,5,7,7,9 program sie juz sypie. Klika dni probuje juz wymyslic co moze byc nie tak i niestety bez skutku. Z gory dziekuje za pomoc. Ponizej kod programu:

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

void sortowanie(int liczby[], int p, int q)  //posylamy funkcji: tablice, indeks pierwszej liczby, indeks ostatniej liczby
{
    int os,m,w=q,y=p;
    os=liczby[(p+q)/2];
    while(p<q)
    {
        while(liczby[p]<os) p++;
        while(liczby[q]>os) q--;
        if(p<q)
        {
            //zamiana miejscami
            m=liczby[p];
            liczby[p]=liczby[q];
            liczby[q]=m;
            p++;
            q--;
        }
    }
    if(w>y)
    {
        sortowanie (liczby,p,(y+w)/2);
        sortowanie (liczby,(y+w)/2 +1,w);
    }

}

 

int main()
{
    //--WPROWADZENIE I SPRAWDZENIE DANYCH--
    int n;
    cout << "Wprowadz ile liczb chcesz posortowac: ";
    cin>>n;
    //n - ilosc liczb
    while (n<=0)
    {
        cout<<"Liczba musi byc dodatnia!"<<endl;
        cout << "Wprowadz ile liczb chcesz posortowac: ";
        cin>>n;
    }
    int liczby[n];
    //tablica w ktorej beda przechowywane wprowadzone liczby
    //ponizej wprowadzanie liczb
    cout<<"Wprowadz pierwsza liczbe: ";
    cin>>liczby[0];
    for(int i=1; i<n; i++)
    {
        cout<<"Wprowadz kolejna liczbe: ";
        cin>>liczby[i];
    }

 

    //--SORTOWANIE (rosnaco) I MIERZENIE CZASU SORTOWANIA--
    clock_t start,stop;
    int czas;
    czas=(double)(stop-start)/CLOCKS_PER_SEC;

    sortowanie(liczby,0,n-1);

    //--WYPROWADZENIE DANYCH--
    for(int j=0; j<n; j++)
    {
        cout<<liczby[j]<<" ";
    }
    cout<<endl<<"Czas sortowania: "<<czas;

    return 0;
}

 

Answer 1

1. tablica jest kopiowana przez kolejne wykonywane funkcje -> tablica powinna byc przesylana przez referencje czy wskaznik albo druga opcja utworzyc klase i zmianiac wartosc danego obiektu

2. tablica nie moze byc statyczna, w Twoim przypadku n powinno byc static, jezeli chcesz miec zmienna wielkosc tablicy poczytaj o dynamicznych tablica, a jakbys poznal std::vector to by pewnie bylo Ci latwiej

Comments

1. Tablica zawsze jest przekazywana jako orginał 2. Gdyby n było static i tak dalej nie było by to poprawne, niech najlepiej użyje vector'ów

Answer 2

Błędny jest ostatni if w funkcji sortowanie a dokładniej zawarty w nim warunek, spróbuj użyć tego:

if( y<q ) {
        sortowanie (liczby,y,q); 
    }
    
if( w>p ) {
    	sortowanie (liczby,p,w);
     }

i rozkminić dlaczego tak powinno być :P Swoją drogą czasami łatwiej jest zobaczyć błąd w kodzie kiedy używasz bardziej opisowych zmiennych typu "poczIndex" lub "koncIndex" zamiast "p" czy "q", może nie jest to dość wygodne wpisywanie takiej zmiennej ale znacznie ułatwia to czytanie i zrozumienie danego kodu ;)