• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Pokazanie kroków algorytmu quicksort

VPS Starter Arubacloud
0 głosów
487 wizyt
pytanie zadane 2 listopada 2018 w C i C++ przez Maciek6997 Nowicjusz (160 p.)

Witam, otóż studiuję matematykę stosowaną i na przedmiocie algorytmy i struktury danych dostałem do napisania algorytm quicksort, program jednak oprócz zwykłego sortowania ma pokazywać każdy krok jaki algorytm ten wykonuję więc muszę wyświetlać oprócz gotowego i posortowanego zbioru również podzbiory na jakie główny zbiór zostaje podzielony. Niestety nie mam pojęcia jak to zrobić, sam algorytm udało mi się napisać i działa chyba poprawnie, niestety gdy próbuję modyfikować go tak aby wyświetlał pojedyńcze podzbiory to nie wyświetla je w postaci nieskładnego ciągu cyfr, próbuję wstawić cout w miejscu gdzie dokonuję dzielenia na partycję ale to nie działa tak jak myślałem,Próbowałem już różnych rozwiązań ale nie potrafię nic wykombinować,Wklejam kod działającego programu 

#include <iostream>

using namespace std;

void Sortowanie( int tab[], int left, int right )
{
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
    do
    {
        while( tab[ i ] < x )
             i++;

        while( tab[ j ] > x )
             j--;


        if( i <= j )
        {
            swap( tab[ i ], tab[ j ] );

            i++;
            j--;
        }
    }
    while( i <= j );

    if( left < j )  Sortowanie( tab, left, j );
        cout << tab[i];
    if( right > i )  Sortowanie( tab, i, right );
        cout << tab[j];
}
int main()
{

    int ilosc_liczb, i;
cout << "Podaj ilosc licz do posortowania: ";
cin >> ilosc_liczb;
int *tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow

for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
cout << "Podaj liczbe ";
cin >> tablica[i];
}
cout << "TABLICA PRZED SORTOWANIEM" << endl;
 for(i = 0; i<ilosc_liczb; i++)
{
  cout << tablica[i] << " ";
}
cout << endl;
Sortowanie(tablica,0,ilosc_liczb-1);
cout << "TABLICA POSORTOWANA" << endl;
for (i = 0; i < ilosc_liczb; i++) // wypisanie posortowanej tablicy
cout  << tablica[i] << "  ";

delete [] tablica; // usuniecie tablicy zaalokowanej dynamicznie

return 0;
}

 

4 odpowiedzi

+1 głos
odpowiedź 3 listopada 2018 przez niezalogowany

Na początku funkcji wypisz wszystkie elementy analizowanego ciągu.:

void Sortowanie( int tab[], int left, int right )
{
    for (int k = lewy_poczatek; k <= prawy_kuniec; ++k) // <=, bo w main zaczyna sie od 0 a konczy na ilosc_liczb - 1; lewy_poczatek i prawy_kuniec sam wprowadz ;)
    {
        cout << tab[k] << " ";
    }
    cout << "\n";
// ...

Przykładowy wynik:

10 9 8 7 6 8 4 3 2 1 
1 2 3 4 
3 4 
8 7 8 9 10 
8 7 
8 9 10 

Można się jeszcze też tak pobawić (żeby wszystko było lepiej widoczne):

Na poczatku funkcji: {10, 9, 8, 7, 6, 8, 4, 3, 2, 1}
Zamieniane elementy: 10, 1
{10, 9, 8, 7, 6, 8, 4, 3, 2, 1} 
{1, 9, 8, 7, 6, 8, 4, 3, 2, 10}
Zamieniane elementy: 9, 2
{1, 9, 8, 7, 6, 8, 4, 3, 2, 10} 
{1, 2, 8, 7, 6, 8, 4, 3, 9, 10}
Zamieniane elementy: 8, 3
{1, 2, 8, 7, 6, 8, 4, 3, 9, 10} 
{1, 2, 3, 7, 6, 8, 4, 8, 9, 10}
Zamieniane elementy: 7, 4
{1, 2, 3, 7, 6, 8, 4, 8, 9, 10} 
{1, 2, 3, 4, 6, 8, 7, 8, 9, 10}
Zamieniane elementy: 6, 6 [uwaga: i == j]
{1, 2, 3, 4, 6, 8, 7, 8, 9, 10} 
{1, 2, 3, 4, 6, 8, 7, 8, 9, 10}

Na poczatku funkcji: {1, 2, 3, 4}
Zamieniane elementy: 2, 2 [uwaga: i == j]
{1, 2, 3, 4} 
{1, 2, 3, 4}

Na poczatku funkcji: {3, 4}
Zamieniane elementy: 3, 3 [uwaga: i == j]
{3, 4} 
{3, 4}

Na poczatku funkcji: {8, 7, 8, 9, 10}
Zamieniane elementy: 8, 8
{8, 7, 8, 9, 10} 
{8, 7, 8, 9, 10}

Na poczatku funkcji: {8, 7}
Zamieniane elementy: 8, 7
{8, 7} 
{7, 8}

Na poczatku funkcji: {8, 9, 10}
Zamieniane elementy: 9, 9 [uwaga: i == j]
{8, 9, 10} 
{8, 9, 10}

TABLICA POSORTOWANA
1  2  3  4  6  7  8  8  9  10  
0 głosów
odpowiedź 3 listopada 2018 przez obl Maniak (51,280 p.)

Ja zrobiłem to w wersji graficznej w JavaScrip-cie tutaj. Na twoim miejscu to bym zrobił tak jak napisał Hipcio najpierw wypisujesz całą tablicę, później zakres, na którym wykonujesz operację sortowania aż do momentu, gdzie pozostają ci tylko dwie liczby więc wypisujesz, że je zamieniasz, gdy posortowany podzbiór masz to piszesz, że wychodzisz z niego do podzbioru nadrzędnego i jeżeli ten ma już wszystkie podzbiory posortowane to piszesz, że zaczynasz sortować podzbiór taki i śmaki. Wypisujesz tutaj jakie liczby zamieniasz miejscami. No i tak w kółko aż do zrealizowania celu. Z resztą Hipcio już cię obdarował częściowo zrobionym tak jak napisałem kodem, resztę tylko trzeba dopracować.

0 głosów
odpowiedź 3 listopada 2018 przez mokrowski Mędrzec (155,460 p.)
edycja 3 listopada 2018 przez mokrowski

Stwórz funkcję która będzie wyświetlała na konsoli bieżącą zawartość tablicy i przekaż wskaźnik na tę funkcję do Sortowanie(...). Przed każdym uruchomieniem ciała kodu w Sortowanie(...), uruchom przekazaną funkcję. Tu żadnej innej konstrukcji nie potrzebujesz :) 

PS. Masz nieco "niezręczności" w kodzie... 

1. Nadużywasz endl. To wyprowadza znak nowej linii na konsolę ale także robi (kosztowne i tu niepotrzebne) opróżnienie strumienia.

2. Radzę nigdy nie tworzyć pętli z ciałem bez klamer. Będzie później bardzo trudno utrzymać taki kod. Klamry zawsze pokażą że masz świadomość 1 instrukcji.

3. Ogólnie stosowanie "gołego new i delete" to proszenie się o kłopoty. Tu zakładam że kazano :)

4. Zbędne jest wyświetlanie wartości w Sortowanie. Wystarczy na końcu.

5. Jakieś literówki i braki znaczków... 

#include <iostream>
#include <cstddef>

using namespace std;

void Sortowanie( int tab[], int left, int right )
{
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
    do
    {
        while( tab[ i ] < x )
        {
            i++;
        }

        while( tab[ j ] > x )
        {
            j--;
        }

        if( i <= j )
        {
            swap( tab[ i ], tab[ j ] );

            i++;
            j--;
        }
    }
    while( i <= j );

    if( left < j )
    {
        Sortowanie( tab, left, j );
    }
    if( right > i )
    {
        Sortowanie( tab, i, right );
    }
}

int main()
{
    size_t ilosc_liczb;
    cout << "Podaj ilosc liczb do posortowania: ";
    cin >> ilosc_liczb;

    int * tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow

    for (size_t i = 0; i < ilosc_liczb; ++i) // wczytywanie liczb do tablicy
    {
        cout << "Podaj liczbe: ";
        cin >> tablica[i];
    }

    cout << "TABLICA PRZED SORTOWANIEM" << '\n';
    for(size_t i = 0; i < ilosc_liczb; ++i)
    {
        cout << tablica[i] << ' ';
    }
    cout << '\n';

    Sortowanie(tablica, 0, ilosc_liczb - 1);

    cout << "TABLICA POSORTOWANA" << '\n';
    for (size_t i = 0; i < ilosc_liczb; ++i) // wypisanie posortowanej tablicy
    {
        cout  << tablica[i] << ' ';
    }
    cout << '\n';

    delete [] tablica; // usuniecie tablicy zaalokowanej dynamicznie

    return 0;
}

A co do rozwiązania, żeby nie tworzyć spojlera, spróbuj najpierw sam. Elementarność rozwiązania zamierzona :)

#include <iostream>
#include <cstddef>

using namespace std;

// Nie wiem czy znasz funktory oraz lambdy, dlatego posłużę się 
// zmienną statyczną globalną. Ogólnie to zła praktyka ale nie
// wiem co wiesz :)

static size_t ilosc;

void Sortowanie( int tab[], int left, int right, void (*pokaz)(int *) )
{
    // sprawdzenie czy przekazano funkcję i jeśli tak to jej uruchomienie.
    if( pokaz )
    {
        pokaz( tab );
    }
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
    do
    {
        while( tab[ i ] < x )
        {
            i++;
        }

        while( tab[ j ] > x )
        {
            j--;
        }

        if( i <= j )
        {
            swap( tab[ i ], tab[ j ] );

            i++;
            j--;
        }
    }
    while( i <= j );

    if( left < j )
    {
        Sortowanie( tab, left, j, pokaz );
    }
    if( right > i )
    {
        Sortowanie( tab, i, right, pokaz );
    }
}

void PokazTablice(int * tab)
{
    for(size_t i = 0; i < ilosc; ++i) {
        cout << tab[i] << ' ';
    }
    cout << '\n';
}

int main()
{
    size_t ilosc_liczb;
    cout << "Podaj ilosc liczb do posortowania: ";
    cin >> ilosc_liczb;

    ilosc = ilosc_liczb; // przypisanie do statycznej zmiennej dla funkcji wyswietlania

    int * tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow

    for (size_t i = 0; i < ilosc_liczb; ++i) // wczytywanie liczb do tablicy
    {
        cout << "Podaj liczbe: ";
        cin >> tablica[i];
    }

    cout << "TABLICA PRZED SORTOWANIEM" << '\n';
    PokazTablice(tablica);

    cout << "KROKI SORTOWANIA" << '\n';
    Sortowanie(tablica, 0, ilosc_liczb - 1, PokazTablice);

    cout << "TABLICA POSORTOWANA" << '\n';
    PokazTablice(tablica);

    delete [] tablica; // usuniecie tablicy zaalokowanej dynamicznie

    return 0; 
}

 

 

1
komentarz 3 listopada 2018 przez niezalogowany

W obu kodach wyskakuje segmentation fault przy takim teście:

10
10 9 8 7 6 5 4 3 2 1

Wydaje mi się, że problem tkwi w użyciu std::size_t, bo np zmienna 'j' może być ujemna.

komentarz 3 listopada 2018 przez mokrowski Mędrzec (155,460 p.)
Ach.. no tak ... to jest ta naiwna (i nieco niebezpieczna) implementacja bez optymalizacji.. poprawione... Thx.

Tu jak ktoś jest zainteresowany optymalizacją. Ma już swoje lata :)

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf
0 głosów
odpowiedź 3 listopada 2018 przez Maciek6997 Nowicjusz (160 p.)
Dziękuję wszystkim za pomoc i wskazówki, dziś wieczorem chyba uda mi się to skończyć :)

Podobne pytania

0 głosów
1 odpowiedź 458 wizyt
pytanie zadane 23 grudnia 2017 w Algorytmy przez Sensej Użytkownik (540 p.)
0 głosów
1 odpowiedź 242 wizyt
pytanie zadane 7 czerwca 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)
0 głosów
0 odpowiedzi 1,198 wizyt
pytanie zadane 6 czerwca 2018 w C i C++ przez qlucha Obywatel (1,790 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...