Рубрики

Программа C для итеративной быстрой сортировки

// Итеративная реализация быстрой сортировки
#include <stdio.h>

  
// Утилита для замены двух элементов

void swap(int* a, int* b)

{

    int t = *a;

    *a = *b;

    *b = t;

}

  
/ * Эта функция одинакова как в итеративной, так и в рекурсивной * /

int partition(int arr[], int l, int h)

{

    int x = arr[h];

    int i = (l - 1);

  

    for (int j = l; j <= h - 1; j++) {

        if (arr[j] <= x) {

            i++;

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[h]);

    return (i + 1);

}

  
/ * A [] -> Массив для сортировки,

   l -> Начальный индекс,

   h -> Конечный индекс * /

void quickSortIterative(int arr[], int l, int h)

{

    // Создать вспомогательный стек

    int stack[h - l + 1];

  

    // инициализировать вершину стека

    int top = -1;

  

    // помещаем начальные значения l и h в стек

    stack[++top] = l;

    stack[++top] = h;

  

    // Продолжаем выталкивать из стека пока не пусто

    while (top >= 0) {

        // Pop h и l

        h = stack[top--];

        l = stack[top--];

  

        // Установить элемент поворота в правильное положение

        // в отсортированном массиве

        int p = partition(arr, l, h);

  

        // Если есть элементы на левой стороне оси,

        // затем сдвигаем левую сторону в стек

        if (p - 1 > l) {

            stack[++top] = l;

            stack[++top] = p - 1;

        }

  

        // Если есть элементы на правой стороне оси,

        // затем вставляем правую сторону в стек

        if (p + 1 < h) {

            stack[++top] = p + 1;

            stack[++top] = h;

        }

    }

}

  
// Утилита для печати содержимого arr

void printArr(int arr[], int n)

{

    int i;

    for (i = 0; i < n; ++i)

        printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };

    int n = sizeof(arr) / sizeof(*arr);

    quickSortIterative(arr, 0, n - 1);

    printArr(arr, n);

    return 0;

}

Выход:

1 2 2 3 3 3 4 5

Вышеупомянутые оптимизации для быстрой рекурсивной сортировки также могут быть применены к итерационной версии.

1) Процесс разбиения одинаков как в рекурсивном, так и итеративном. Те же методы для выбора оптимального центра также могут быть применены к итерационной версии.

Рекомендуемые посты:

Программа C для итеративной быстрой сортировки

0.00 (0%) 0 votes