C - Algorytmy - Szybkie sortowanie

Tym razem szybki post dotyczący algorytmu szybkiego sortowania.

[Źródło: https://icons.com/icon/40670/c-programming]

Program:

Na samym początku należy wybrać element zwany piwotem. Tutaj nie ma znaczenia, który z elementów to będzie. Natomiast najczęściej wybiera się do tego celu element środkowy wybierany  w następujący sposób:

1. static uint16_t selectPivot(uint16_t startIndex, uint16_t endIndex)
2. {
3.     return((startIndex + endIndex) / 2);
4. }

Tutaj bierzemy początkowy oraz końcowy index tablicy i dzielimy na pół. Dalej w algorytmie zamienia się pozycjami wartość piwotu z pierwszą pozycją w zbiorze. Następnie wyznacza się dwa indeksy jeden z wartością występującą po piwocie (w tym momencie drugi element zbioru) drugi jest ostatnim elementem w przeszukiwanej tablicy. 

Dalej porównuje się elementy w tablicy i porównuje się je z wartością piwotu. Następnie gdy wartość dolnego wskaźnika jest mniejsza od wartości z drugiej strony to następuje zamiana wartości.

Gdy już przejdziemy przez tablicę to zamieniamy miejscami element pierwszy drugim wskaźnikiem, który przesuwa się od końca tablicy. Po tej operacji wywołujemy rekurencyjne tą samą funkcję tylko ze zmienionymi parametrami. Czyli pierwsze wywołanie dla dolnej połowy zbioru, drugie wywołanie dla górnej połowy zbioru. Funkcje przechodzą aż do momentu gdy element na pozycji drugiej będzie mniejszy od górnej granicy przeszukiwania, czyli aż przejdziemy przez całą tablicę.

1. void quickSortTable(uint16_t *list, uint16_t beginElement, uint16_t searchSize)
2. {
3.     uint16_t keyValue = 0;
4.     uint16_t i = 0;
5.     uint16_t j = 0;
6.     uint16_t pivotElementIndex = 0;
8.     if (beginElement < searchSize)
9.     {
10.         pivotElementIndex = selectPivot(beginElement, searchSize);
11.         swapElements(&list[beginElement], &list[pivotElementIndex]);
12.         keyValue = list[beginElement];
13.         i = beginElement + 1;
14.         j = searchSize;
16.         while (i <= j)
17.         {
18.             while ((i <= searchSize) && (list[i] <= keyValue))
19.             {
20.                 i++;
21.             }
22.             while ((j >= beginElement) && (list[j] > keyValue))
23.             {
24.                 j--;
25.             }
26.             if (i < j)
27.             {
28.                 swapElements(&list[i], &list[j]);
29.             }
30.         }
31.         swapElements(&list[beginElement], &list[j]);
33.         quickSortTable(list, beginElement, j - 1);
34.         quickSortTable(list, j + 1, searchSize);
35.     }
36. }

Funkcja zmiany wartości miejscami przez podanie wskaźników:

1. static void swapElements(uint16_t *x, uint16_t *y)
2. {
3.     uint16_t temp;
4.     temp = *x;
5.     *x = *y;
6.     *y = temp;
7. }

Pliki do postu można pobrać z dysku Google pod tym linkiem.