sortowanie c++ quick sort

Question

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;
}

 

Answer 1

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;
}