Рубрики

Итеративная быстрая сортировка

Сортировка

Ниже приведена типичная рекурсивная реализация быстрой сортировки, которая использует последний элемент в качестве сводной.

C ++

// код CPP для рекурсивной функции быстрой сортировки
#include <bits/stdc++.h>

  

using namespace std;

  
// Функция для обмена номерами

void swap(int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

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

   помещает элемент поворота в правильное положение

   положение в отсортированном массиве и места

   все меньше (меньше, чем шарнир) слева

   поворота и всех больших элементов к

   право поворота * /

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 quickSort(int A[], int l, int h)

{

    if (l < h) {

        / * Индекс разделения * /

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

        quickSort(A, l, p - 1);

        quickSort(A, p + 1, h);

    }

}

  
// Код драйвера

int main()

{

  

    int n = 5;

    int arr[n] = { 4, 2, 6, 9, 2 };

  

    quickSort(arr, 0, n - 1);

  

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

        cout << arr[i] << " ";

    }

  

    return 0;

}

Джава

// Java-программа для реализации QuickSort

import java.util.*;

  

class QuickSort {

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

    помещает элемент поворота в правильное положение

    положение в отсортированном массиве, и помещает все

    меньше (меньше, чем шарнир) слева от

    стержень и все большие элементы направо

    оси * /

    static int partition(int arr[], int low, int high)

    {

        int pivot = arr[high];

        int i = (low - 1); // индекс меньшего элемента

        for (int j = low; j <= high - 1; j++) {

            // Если текущий элемент меньше или

            // равно pivot

            if (arr[j] <= pivot) {

                i++;

  

                // поменять местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        int temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

  

        return i + 1;

    }

  

    / * Основная функция, которая реализует QuickSort ()

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

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

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

    static void qSort(int arr[], int low, int high)

    {

        if (low < high) {

            / * pi - индекс разбиения, arr [pi] -

            сейчас в нужном месте * /

            int pi = partition(arr, low, high);

  

            // Рекурсивно сортировать элементы перед

            // раздел и после раздела

            qSort(arr, low, pi - 1);

            qSort(arr, pi + 1, high);

        }

    }

  

    // Код драйвера

    public static void main(String args[])

    {

  

        int n = 5;

        int arr[] = { 4, 2, 6, 9, 2 };

  

        qSort(arr, 0, n - 1);

  

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

            System.out.print(arr[i] + " ");

        }

    }

}

python3

# Типичный рекурсивный Python
# реализация QuickSort

  
# Функция принимает последний элемент в качестве оси,
# помещает элемент поворота в правильное положение
# позиция в отсортированном массиве и размещает все
# меньше (меньше, чем шарнир) слева от
# поворот и все большие элементы справа
Количество точек разворота

def partition(arr, low, high):

    i = (low - 1)         # индекс меньшего элемента

    pivot = arr[high]     # пивот

  

    for j in range(low, high):

  

        # Если текущий элемент меньше

        # чем или равно Pivot

        if arr[j] <= pivot:

          

            # индекс приращения

            # меньший элемент

            i += 1

            arr[i], arr[j] = arr[j], arr[i]

  

    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    return (i + 1)

  
# Основная функция, реализующая QuickSort
# arr [] -> Массив для сортировки,
# low -> Начальный индекс,
# high -> Конечный индекс

  
# Функция для быстрой сортировки

def quickSort(arr, low, high):

    if low < high:

  

        # pi - индекс разделения, теперь arr [p]

        # в нужном месте

        pi = partition(arr, low, high)

  

        # Отдельно сортировать элементы перед

        # раздел и после раздела

        quickSort(arr, low, pi-1)

        quickSort(arr, pi + 1, high)

  
Код водителя

if __name__ == '__main__' :

      

    arr = [4, 2, 6, 9, 2]

    n = len(arr)

      

    # Вызов функции быстрой сортировки

    quickSort(arr, 0, n - 1)

      

    for i in range(n):

        print(arr[i], end = " ")

C #

// C # программа для реализации
// Быстрая сортировка

using System;

  

class GFG {

  

    / * Эта функция занимает последний элемент

    как опорный элемент, помещает опорный элемент

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

    массив, а местами все поменьше

    (меньше, чем шарнир) слева от

    стержень и все большие элементы

    право поворота * /

    static int partition(int[] arr,

                         int low, int high)

    {

        int temp;

        int pivot = arr[high];

  

        // индекс меньшего элемента

        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {

  

            // Если текущий элемент

            // меньше или

            // равно pivot

            if (arr[j] <= pivot) {

                i++;

  

                // поменять местами arr [i] и arr [j]

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high]

        // (или разворот)

        temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

  

        return i + 1;

    }

  

    / * Основная функция, которая реализует

    QuickSort () arr [] -> Массив, который будет

    отсортированный,

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

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

    static void qSort(int[] arr, int low,

                      int high)

    {

        if (low < high) {

            / * pi - индекс разделения,

            arr [pi] теперь в нужном месте * /

            int pi = partition(arr, low, high);

  

            // Рекурсивно сортировать элементы

            // до раздела и после

            // раздел

            qSort(arr, low, pi - 1);

            qSort(arr, pi + 1, high);

        }

    }

  

    // Код драйвера

    public static void Main()

    {

  

        int n = 5;

        int[] arr = { 4, 2, 6, 9, 2 };

  

        qSort(arr, 0, n - 1);

  

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

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-код для рекурсивной функции
// быстрой сортировки

  
// Функция для обмена номерами

function swap(&$a, &$b)

{ 

    $temp = $a; 

    $a = $b; 

    $b = $temp; 

} 

  
/ * Эта функция принимает последний элемент в качестве оси,
помещает элемент поворота в правильное положение
положение в отсортированном массиве и места
все меньше (меньше, чем шарнир) слева
поворота и всех больших элементов к
право поворота * /

function partition (&$arr, $l, $h) 

{ 

    $x = $arr[$h]; 

    $i = ($l - 1); 

  

    for ($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 -> Конечный индекс * /

function quickSort(&$A, $l, $h) 

{ 

    if ($l < $h) 

    { 

        / * Индекс разделения * /

        $p = partition($A, $l, $h); 

        quickSort($A, $l, $p - 1); 

        quickSort($A, $p + 1, $h); 

    } 

      
} 

  
// Код драйвера

$n = 5; 

$arr = array(4, 2, 6, 9, 2); 

  

quickSort($arr, 0, $n - 1); 

  

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

{ 

    echo $arr[$i] . " "; 

} 

  
// Этот код предоставлен
// ратбхупендра
?>


Выход:

2 2 4 6 9

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

1) Приведенная выше реализация использует последний индекс в качестве точки разворота. Это вызывает наихудшее поведение на уже отсортированных массивах, что часто встречается. Эту проблему можно решить, выбрав либо произвольный индекс для стержня, либо выбрав средний индекс раздела, либо выбрав медиану первого, среднего и последнего элемента раздела для стержня. (Смотрите это для деталей)

2) Чтобы уменьшить глубину рекурсии, вернитесь сначала для меньшей половины массива и используйте хвостовой вызов для рекурсии в другую.

3) Сортировка вставок работает лучше для небольших подмассивов. Сортировка вставки может использоваться для вызовов на таких небольших массивах (т. Е. Когда длина меньше порога t, определенного экспериментально). Например, эта реализация библиотеки qsort использует сортировку вставкой ниже размера 7.

Несмотря на приведенные выше оптимизации, функция остается рекурсивной и использует стек вызовов функций для хранения промежуточных значений l и h. Стек вызовов функций хранит другую бухгалтерскую информацию вместе с параметрами. Кроме того, вызовы функций включают в себя издержки, такие как сохранение записи активации функции вызывающей стороны и затем возобновление выполнения.

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

C ++

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

using namespace std;

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

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)

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

}

  
// Это код, предоставленный rathbhupendra

С

// Итеративная реализация быстрой сортировки
#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;

}

Джава

// Java-программа для реализации QuickSort

import java.util.*;

  

class QuickSort {

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

    помещает элемент поворота в правильное положение

    положение в отсортированном массиве, и помещает все

    меньше (меньше, чем шарнир) слева от

    стержень и все большие элементы направо

    оси * /

    static int partition(int arr[], int low, int high)

    {

        int pivot = arr[high];

  

        // индекс меньшего элемента

        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {

            // Если текущий элемент меньше или

            // равно pivot

            if (arr[j] <= pivot) {

                i++;

  

                // поменять местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        int temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

  

        return i + 1;

    }

  

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

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

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

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

    {

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

        int[] stack = new int[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;

            }

        }

    }

    // Код драйвера

    public static void main(String args[])

    {

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

        int n = 8;

  

        // вызов функции

        quickSortIterative(arr, 0, n - 1);

  

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

            System.out.print(arr[i] + " ");

        }

    }

}

питон

# Python программа для реализации Quicksort

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

def partition(arr, l, h):

    i = ( l - 1 )

    x = arr[h]

  

    for j in range(l, h):

        if   arr[j] <= x:

  

            # индекс приращения меньшего элемента

            i = i + 1

            arr[i], arr[j] = arr[j], arr[i]

  

    arr[i + 1], arr[h] = arr[h], arr[i + 1]

    return (i + 1)

  
# Функция для быстрой сортировки
# arr [] -> Массив для сортировки,
# l -> Начальный индекс,
# h -> Конечный индекс

def quickSortIterative(arr, l, h):

  

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

    size = h - l + 1

    stack = [0] * (size)

  

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

    top = -1

  

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

    top = top + 1

    stack[top] = l

    top = top + 1

    stack[top] = h

  

    # Продолжайте выскакивать из стека, пока не пусто

    while top >= 0:

  

        # Поп ч и л

        h = stack[top]

        top = top - 1

        l = stack[top]

        top = top - 1

  

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

        # отсортированный массив

        p = partition( arr, l, h )

  

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

        # затем нажмите левую сторону, чтобы сложить

        if p-1 > l:

            top = top + 1

            stack[top] = l

            top = top + 1

            stack[top] = p - 1

  

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

        # затем нажмите правую сторону, чтобы сложить

        if p + 1 < h:

            top = top + 1

            stack[top] = p + 1

            top = top + 1

            stack[top] = h

  
# Код драйвера для проверки выше

arr = [4, 3, 5, 2, 1, 3, 2, 3]

n = len(arr)

quickSortIterative(arr, 0, n-1)

print ("Sorted array is:")

for i in range(n):

    print ("% d" % arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

C #

// C # программа для реализации QuickSort

using System;

  

class GFG {

  

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

    помещает элемент поворота в правильное положение

    положение в отсортированном массиве, и помещает все

    меньше (меньше, чем шарнир) слева от

    стержень и все большие элементы направо

    оси * /

    static int partition(int[] arr, int low,

                         int high)

    {

        int temp;

        int pivot = arr[high];

  

        // индекс меньшего элемента

        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {

            // Если текущий элемент меньше

            // чем или равно Pivot

            if (arr[j] <= pivot) {

                i++;

  

                // поменять местами arr [i] и arr [j]

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high]

        // (или разворот)

  

        temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

  

        return i + 1;

    }

  

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

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

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

    static void quickSortIterative(int[] arr,

                                   int l, int h)

    {

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

        int[] stack = new int[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;

            }

        }

    }

  

    // Код драйвера

    public static void Main()

    {

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

        int n = 8;

  

        // вызов функции

        quickSortIterative(arr, 0, n - 1);

  

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

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// Итеративная реализация быстрой сортировки

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

function swap ( &$a, &$b ) 

{ 

    $t = $a; 

    $a = $b; 

    $b = $t; 

} 

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

function partition (&$arr, $l, $h) 

{ 

    $x = $arr[$h]; 

    $i = ($l - 1); 

  

    for ($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 -> Конечный индекс * /

function quickSortIterative (&$arr, $l, $h) 

{ 

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

    $stack=array_fill(0, $h - $l + 1, 0); 

  

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

    $top = -1; 

  

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

    $stack[ ++$top ] = $l; 

    $stack[ ++$top ] = $h; 

  

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

    while ( $top >= 0 ) 

    { 

        // Pop h и l

        $h = $stack[ $top-- ]; 

        $l = $stack[ $top-- ]; 

  

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

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

        $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

function printArr( $arr, $n ) 

{ 

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

        echo $arr[$i]." "; 

} 

  
// Код драйвера

    $arr = array(4, 3, 5, 2, 1, 3, 2, 3); 

    $n = count($arr); 

    quickSortIterative($arr, 0, $n - 1 ); 

    printArr($arr, $n ); 

  
// Этот код предоставлен chandan_jnu
?>


Выход:

1 2 2 3 3 3 4 5

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

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

2) Чтобы уменьшить размер стека, сначала нажмите индексы меньшей половины.

3) Используйте сортировку вставки, когда размер уменьшается ниже экспериментально рассчитанного порога.

Ссылки:
http://en.wikipedia.org/wiki/Quicksort

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Итеративная быстрая сортировка

0.00 (0%) 0 votes