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

sortowanie c++ quick sort

VPS Starter Arubacloud
0 głosów
735 wizyt
pytanie zadane 22 października 2020 w C i C++ przez milosz123 Użytkownik (720 p.)

Cześć uczę się ostatnio algorytmów sortowania i napisałem quick sorta chciałbym się dowiedzieć czy algorytm działa poprawnie a jeśli tak czy da się go w jakiś sposób udoskonalić oto kod:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int rozdzielanie(int *tab, int l, int r) {

    int q = r - 1;

    while (l != q) {
        if (tab[l] > tab[r]) {
            while (tab[q] > tab[r] && q > l) q--;
            if (q > l) swap(tab[l],tab[q]);
        }
        if (q > l) l++;
    }
    if (tab[l] > tab[r]) {
        swap(tab[l],tab[r]);
        return l;
    }
    return l+1;
}

void sortowanie_szybkie(int *tab, int l, int r) {

    if (l < r) {
        int q = rozdzielanie(tab,l,r);
        sortowanie_szybkie(tab,l,q-1);
        sortowanie_szybkie(tab,q+1,r);
    }
}

int main()
{
    int n,l = 0;

    cin >> n;

    int *tab = new int[n];

    for (int i = 0; i < n; i++) cin >> tab[i];
    sortowanie_szybkie(tab,l,n-1);
    for (int i = 0; i < n; i++) cout << tab[i] << "\n";
    cout << "\n";

    return 0;
}

 

1 odpowiedź

0 głosów
odpowiedź 23 października 2020 przez TOM_CPP Pasjonat (22,640 p.)
wybrane 25 października 2020 przez milosz123
 
Najlepsza

czy algorytm działa poprawnie a jeśli tak czy da się go w jakiś sposób udoskonalić oto kod

Tak , algorytm jest poprawny.

Jeżeli chcesz udoskonalić swój kod to możesz w funkcji rozdzielanie użyć pętli for , co zmniejszy ilość kodu, oraz przystosować funkcje ( użyć szablonów ) do obsługi każdej struktury danych, która pozwala na zastosowanie funkcji std:begin(), std::end() , std::size() ( wymaga to standardu C++17 )

Poniżej przykładowy kod:

#include <iostream>
#include <vector>

using namespace std;

template< typename T >
int partition( T& tab , int low , int high )
{
    const auto pivot {tab[high]};
    auto i {low-1};

    for( int j {low} ; j <= high-1 ; ++j )
    {
        if( tab[j] < pivot )
        {
            ++i;
            swap( tab[i] , tab[j] );
        }
    }
    swap( tab[i+1] , tab[high] );
    return i+1;
}

template< typename T >
void quicksort( T& tab , int low = 0 , int high = -1 )
{
    if( high == -1 ) high = size(tab)-1;
    if( low < high )
    {
        const auto div = partition(tab,low,high);
        quicksort(tab,low,div-1);
        quicksort(tab,div+1,high);
    }
}

template< typename T >
void print( const T& tab )
{
    for( const auto& element : tab ) cout << element << " ";
    cout << endl;
}

int main()
{
    int sequence1[] = {0,200,34,-6,998,567,76,54,0};
    quicksort(sequence1);
    print(sequence1);

    vector<int> sequence2 {45,350,4,-62,-8,1156,2,6,-40,8,7,33};
    quicksort(sequence2);
    print(sequence2);

    return 0;
}

 

Podobne pytania

–3 głosów
2 odpowiedzi 384 wizyt
pytanie zadane 13 marca 2018 w C i C++ przez Damian918 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 278 wizyt
pytanie zadane 24 stycznia 2018 w C i C++ przez Elijah Romashchenko Nowicjusz (220 p.)
0 głosów
0 odpowiedzi 192 wizyt
pytanie zadane 27 listopada 2017 w C i C++ przez barti22062 Początkujący (370 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 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!

...