Quick sort C/C++

Nejznámější a nejrychlejší řadící algoritmus. Se svou náročností Ο(N log N) je vhodný i pro velká pole dat. Nevýhodou je jeho paměťová náročnost při velkém objemu dat. Při programování je pořeba dát pozor na indexy pole, zejména při rozdělování na podúseky. Pokud je potřeba roztřídit jen malé množství dat, spíše doporučuji jednodušší bubble sort.

Quick sort v C

Verzi v C jsem napsal kompletně i s tělem main. Program můžete spustit hned po nakopírování. Není zde co řešit.

#include <stdio.h>
#define DATA_SIZE 20

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void quick_sort(int data[DATA_SIZE], int start, int end)
{
    int pivot, startIndex, endIndex;
    if (start >= end)
        return;
    pivot = start;
    startIndex = start + 1;
    endIndex = end;

    while (startIndex < endIndex)
    {
        if (data[pivot] >= data[startIndex])
        {
            startIndex++;
        }
        else
        {
            swap(data + startIndex, data + endIndex--);
        }
    }

    if (pivot + 1 == startIndex)
    {
        if (data[pivot] > data[startIndex])
        {
            swap(data + pivot, data + startIndex);
        }
    }
    else
    {
        if (data[pivot] < data[startIndex])
            startIndex--;
        swap(data + pivot, data + startIndex);
    }

    pivot = startIndex;

    quick_sort(data, start, pivot - 1);
    quick_sort(data, pivot + 1, end);
}

int main(int argc, const char * argv[])
{

    int data[20] = { 12, 4, 6, 43, 68, 35, 79, 3, 11, 18,
        26, 21, 2, 88, 34, 13, 90, 57, 77, 19 };

    int i;

    for (i = 0; i < DATA_SIZE; i++)
        printf("%d | ", data[i]);
    printf("\n");

    quick_sort(data, 0, DATA_SIZE -1);

    for (i = 0; i < DATA_SIZE; i++)
        printf("%d | ", data[i]);
    printf("\n");

    return 0;
}

Quicksort v C++

Verzi v C++ jsem udělal jako šablonu. Funkce je stejná jako v C, ale můžeme se zvolit, jestli budeme třídit int, long…

#include <iostream>
#include <vector>

#define DATATYPE int

using std::vector;
using std::cout;
using std::endl;

template <typename T>
void swap(std::vector<T> *data, int a, int b)
{
    T tmp;
    tmp = data->at(a);
    data->at(a) = data->at(b);
    data->at(b) = tmp;
}

template <typename T>
void quick_sort(std::vector<T> *data, int start, int end)
{
    int pivot, startIndex, endIndex;
    if (start >= end)
        return;

    pivot = start;
    startIndex = start + 1;
    endIndex = end;

    while (startIndex < endIndex)
    {
        if (data->at(pivot) >= data->at(startIndex))
            startIndex++;
        else
            swap(data, startIndex, endIndex--);
    }

    if (pivot + 1 == startIndex)
    {
        if (data->at(pivot) > data->at(startIndex))
        {
            swap(data, pivot, startIndex);
        }
    }
    else
    {
        if (data->at(pivot) < data->at(startIndex))
            startIndex--;
        swap(data, pivot, startIndex);
    }

    pivot = startIndex;

    quick_sort(data, start, pivot - 1);
    quick_sort(data, pivot + 1, end);
}

int main(int argc, const char * argv[])
{
    DATATYPE dataSource[20] = { 12, 4, 6, 43, 68, 35, 79, 3, 11, 18,
        26, 21, 2, 88, 34, 13, 90, 57, 77, 19 };

    vector<DATATYPE> data(dataSource, dataSource + sizeof(dataSource)/sizeof(DATATYPE));

    for (vector<DATATYPE>::iterator idx = data.begin(); idx < data.end(); idx++)
        cout << "" << *idx;
    cout << endl;

    quick_sort<DATATYPE>(&data, 0, (int)data.size() - 1);

    for (vector<DATATYPE>::iterator idx = data.begin(); idx < data.end(); idx++)
        cout << "" << *idx;

    return 0;
}