Реализация быстрой сортировки на языке программирования C

Быстрая сортировка (англ. Quick Sort) – алгоритм сортировки, который использует принцип «разделяй и властвуй». Он считается одним из самых быстрых алгоритмов сортировки среди всех известных сегодня.

Основная идея алгоритма заключается в том, что из списка элементов выбирается один элемент (обычно первый), который называется опорным. Затем остальные элементы массива сравниваются с этим элементом и на основе этого они разделяются на две группы – больше, чем опорный элемент, и меньше или равны опорному элементу. Каждая группа сортируется отдельно. Операция разделения выполняется рекурсивно, пока все подмассивы не будут отсортированы.

Пример кода на языке С++:

#include  
using namespace std; 
  
void quickSort(int *arr, int left, int right){ 
    int i = left, j = right; 
    int pivot = arr[(left + right) / 2]; // выбор опорного элемента (пример: центральный элемент) 
  
    // разделение на две группы 
    while (i <= j) { 
        while (arr[i] < pivot) 
            i++; 
        while (arr[j] > pivot) 
            j--; 
        if (i <= j) { 
            swap(arr[i], arr[j]); 
            i++; 
            j--; 
        } 
    } 
  
    // рекурсивная сортировка каждой группы 
    if (left < j) 
        quickSort(arr, left, j); 
    if (i < right) 
        quickSort(arr, i, right); 
} 
  
int main() { 
    int arr[] = {6, 2, 1, 8, 7, 3, 5, 4}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    
    cout << "Unsorted array n:"; 
    for (int i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    
    quickSort(arr, 0, size - 1); // вызов функции сортировки 
  
    cout << endl << "Sorted array n:"; 
    for (int i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    
    return 0; 
} 

В данном примере мы объявляем функцию `quickSort`, принимающую указатель на массив и индексы начала (`left`) и конца (`right`) обрабатываемой части массива. Первым делом мы выбираем опорный элемент `pivot`, в примере это центральный элемент.

Затем мы проходим по всем элементам подмассива и перемещаем элементы в нужные группы, используя два указателя `i` и `j`, которые проходят массив справа налево и слева направо соответственно. Элементы меньше опорного перемещаются в левую группу, а больше – в правую.

Мы продолжаем процесс, пока `i` и `j` не пересекутся. Затем мы вызываем рекурсивно функцию `quickSort` для каждой из двух подгрупп (левой и правой), пока все элементы не будут отсортированы.

В конечном итоге, функция `main` вызывает функцию `quickSort` с указателем на массив и начальным и конечным индексами, и затем выводит отсортированный массив на экран.

Таким образом, быстрая сортировка предлагает эффективный способ сортировки больших объемов данных, и широко применяется в области программирования.