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