Рубрики

3-Way QuickSort (голландский национальный флаг)

В простом алгоритме QuickSort мы выбираем элемент как pivot, разделяем массив вокруг pivot и повторяем для подмассивов слева и справа от pivot.
Рассмотрим массив, который имеет много избыточных элементов. Например, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Если в Simple QuickSort выбрана точка 4, то мы фиксируем только одну четверку и рекурсивно обрабатываем оставшиеся вхождения.

Идея 3 way QuickSort заключается в обработке всех вхождений пивота и основана на алгоритме голландского национального флага.

In 3 Way QuickSort, an array arr[l..r] is divided in 3 parts:
a) arr[l..i] elements less than pivot.
b) arr[i+1..j-1] elements equal to pivot.
c) arr[j..r] elements greater than pivot.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для 3-х сторонней быстрой сортировки
#include <bits/stdc++.h>

using namespace std;

  
/ * Эта функция разбивает [] на три части

   a) a [l..i] содержит все элементы, меньшие, чем пивот

   б) a [i + 1..j-1] содержит все вхождения пивота

   c) a [j..r] содержит все элементы, больше чем pivot * /

void partition(int a[], int l, int r, int &i, int &j)

{

    i = l-1, j = r;

    int p = l-1, q = r;

    int v = a[r];

  

    while (true)

    {

        // Слева найти первый элемент больше

        // или равно v. Этот цикл обязательно завершится

        // так как v последний элемент

        while (a[++i] < v);

  

        // Находим справа первый элемент меньше или

        // равно v

        while (v < a[--j])

            if (j == l)

                break;

  

        // Если я и j пересекаются, то мы закончили

        if (i >= j) break;

  

        // Поменяйте местами, чтобы меньший шел налево, больший шел направо

        swap(a[i], a[j]);

  

        // Переместить все то же левое вхождение точки поворота в начало

        // массив и счетчик, используя p

        if (a[i] == v)

        {

            p++;

            swap(a[p], a[i]);

        }

  

        // Переместить все то же правильное вхождение точки поворота в конец массива

        // и продолжаем считать используя q

        if (a[j] == v)

        {

            q--;

            swap(a[j], a[q]);

        }

    }

  

    // Переместить элемент сводки в его правильный индекс

    swap(a[i], a[r]);

  

    // Переместить все левые одинаковые вхождения с начала

    // рядом с arr [i]

    j = i-1;

    for (int k = l; k < p; k++, j--)

        swap(a[k], a[j]);

  

    // Перемещаем все права на одни и те же вхождения с конца

    // рядом с arr [i]

    i = i+1;

    for (int k = r-1; k > q; k--, i++)

        swap(a[i], a[k]);

}

  
// быстрая сортировка на основе 3-х секционных разделов

void quicksort(int a[], int l, int r)

{

    if (r <= l) return;

  

    int i, j;

  

    // Обратите внимание, что i и j передаются как ссылки

    partition(a, l, r, i, j);

  

    // Recur

    quicksort(a, l, j);

    quicksort(a, i, r);

}

  
// Вспомогательная функция для печати массива

void printarr(int a[], int n)

{

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

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

    printf("\n");

}

  
// Драйвер программы

int main()

{

    int a[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};

    int size = sizeof(a) / sizeof(int);

    printarr(a, size);

    quicksort(a, 0, size - 1);

    printarr(a, size);

    return 0;

}

C #

// C # программа для 3-х сторонней быстрой сортировки

using System; 

    

class GFG 

    // Функция, которая используется для обмена значениями

    static void swap<T>(ref T lhs, ref T rhs)

    {

        T temp;

        temp = lhs;

        lhs = rhs;

        rhs = temp;

    }

    / * Эта функция разбивает [] на три части

       a) a [l..i] содержит все элементы, меньшие, чем пивот

       б) a [i + 1..j-1] содержит все вхождения пивота

       c) a [j..r] содержит все элементы, больше чем pivot * /

    public static void partition(int[] a, int l, int r, ref int i, ref int j) 

    

        i = l-1; j = r; 

        int p = l-1, q = r; 

        int v = a[r]; 

        

        while (true

        

            // Слева найти первый элемент больше

            // или равно v. Этот цикл обязательно завершится

            // так как v последний элемент

            while (a[++i] < v); 

        

            // Находим справа первый элемент меньше или

            // равно v

            while (v < a[--j]) 

                if (j == l) 

                    break

        

            // Если я и j пересекаются, то мы закончили

            if (i >= j) break

        

            // Поменяйте местами, чтобы меньший шел налево, больший шел направо

            swap(ref a[i], ref a[j]); 

        

            // Переместить все то же левое вхождение точки поворота в начало

            // массив и счетчик, используя p

            if (a[i] == v) 

            

                p++; 

                swap(ref a[p], ref a[i]); 

            

        

            // Переместить все то же правильное вхождение точки поворота в конец массива

            // и продолжаем считать используя q

            if (a[j] == v) 

            

                q--; 

                swap(ref a[j], ref a[q]); 

            

        

        

        // Переместить элемент сводки в его правильный индекс

        swap(ref a[i], ref a[r]); 

        

        // Переместить все левые одинаковые вхождения с начала

        // рядом с arr [i]

        j = i-1; 

        for (int k = l; k < p; k++, j--) 

            swap(ref a[k], ref a[j]); 

        

        // Перемещаем все права на одни и те же вхождения с конца

        // рядом с arr [i]

        i = i+1; 

        for (int k = r-1; k > q; k--, i++) 

            swap(ref a[i], ref a[k]); 

    

        

    // быстрая сортировка на основе 3-х секционных разделов

    public static void quicksort(int[] a, int l, int r) 

    

        if (r <= l) return

        

        int i = 0, j = 0; 

        

        // Обратите внимание, что i и j передаются как ссылки

        partition(a, l, r, ref i, ref j); 

        

        // Recur

        quicksort(a, l, j); 

        quicksort(a, i, r); 

    

        

    // Вспомогательная функция для печати массива

    public static void printarr(int[] a, int n) 

    

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

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

        Console.Write("\n"); 

    

        

    // Драйвер программы

    static void Main() 

    

        int[] a = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4}; 

        int size = a.Length; 

        printarr(a, size); 

        quicksort(a, 0, size - 1); 

        printarr(a, size); 

    }

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

}

Выход:

4  9  4  4  1  9  4  4  9  4  4  1  4
1  1  4  4  4  4  4  4  4  4  9  9  9

Спасибо Utkarsh за предложенную выше реализацию.

Еще одна реализация с использованием алгоритма голландского национального флага

C ++

// C ++ программа для 3-х сторонней быстрой сортировки
#include <bits/stdc++.h>

using namespace std;

  

void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Вспомогательная функция для печати массива

void printarr(int a[], int n)

{

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

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

    printf("\n");

}

  
/ * Эта функция разбивает [] на три части
a) a [l..i] содержит все элементы, меньшие, чем пивот
б) a [i + 1..j-1] содержит все вхождения пивота
c) a [j..r] содержит все элементы, больше чем pivot * /

  
// Использует алгоритм голландского национального флага

void partition(int a[], int low, int high, int &i, int &j)

{

    // Для обработки 2 элементов

    if (high - low <= 1)

    {

        if (a[high] < a[low])

            swap(&a[high], &a[low]);

        i = low;

        j = high;

        return;

    }

  

    int mid = low;

    int pivot = a[high];

    while (mid <= high)

    {

        if (a[mid]<pivot)

            swap(&a[low++], &a[mid++]);

        else if (a[mid]==pivot)

            mid++;

        else if (a[mid]>pivot)

            swap(&a[mid], &a[high--]);

    }

  

    // обновить i и j

    i = low-1;

    j = mid; // или high-1

}

  
// быстрая сортировка на основе 3-х секционных разделов

void quicksort(int a[], int low, int high)

{

    if (low>=high) // 1 или 0 элементов

        return;

  

    int i, j;

  

    // Обратите внимание, что i и j передаются как ссылки

    partition(a, low, high, i, j);

  

    // Повторяем две половины

    quicksort(a, low, i);

    quicksort(a, j, high);

}

  
// Драйвер программы

int main()

{

    int a[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};

    // int a [] = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64, 11, 41};

    // int a [] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // int a [] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};

    // int a [] = {4, 9, 4, 4, 9, 1, 1, 1};

    int size = sizeof(a) / sizeof(int);

  

    printarr(a, size);

    quicksort(a, 0, size - 1);

    printarr(a, size);

    return 0;

}

C #

// C # программа для 3-х сторонней быстрой сортировки

using System; 

    

class GFG 

    // Функция, которая используется для обмена значениями

    static void swap<T>(ref T lhs, ref T rhs)

    {

        T temp;

        temp = lhs;

        lhs = rhs;

        rhs = temp;

    }

        

    // Вспомогательная функция для печати массива

    public static void printarr(int[] a, int n) 

    

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

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

        Console.Write("\n"); 

    

        

    / * Эта функция разбивает [] на три части

    a) a [l..i] содержит все элементы, меньшие, чем пивот

    б) a [i + 1..j-1] содержит все вхождения пивота

    c) a [j..r] содержит все элементы, больше чем pivot * /

        

    // Использует алгоритм голландского национального флага

    public static void partition(int[] a, int low, int high, ref int i, ref int j) 

    

        // Для обработки 2 элементов

        if (high - low <= 1) 

        

            if (a[high] < a[low]) 

                swap(ref a[high], ref a[low]); 

            i = low; 

            j = high; 

            return

        

        

        int mid = low; 

        int pivot = a[high]; 

        while (mid <= high) 

        

            if (a[mid]<pivot) 

                swap(ref a[low++], ref a[mid++]); 

            else if (a[mid]==pivot) 

                mid++; 

            else if (a[mid]>pivot) 

                swap(ref a[mid], ref a[high--]); 

        

        

        // обновить i и j

        i = low-1; 

        j = mid; // или high-1

    

        

    // быстрая сортировка на основе 3-х секционных разделов

    public static void quicksort(int[] a, int low, int high) 

    

        if (low>=high) // 1 или 0 элементов

            return

        

        int i = 0 , j = 0; 

        

        // Обратите внимание, что i и j передаются как ссылки

        partition(a, low, high, ref i, ref j); 

        

        // Повторяем две половины

        quicksort(a, low, i); 

        quicksort(a, j, high); 

    

        

    // Драйвер программы

    static void Main() 

    

        int[] a = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4}; 

        // int [] a = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64, 11, 41};

        // int [] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        // int [] a = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};

        // int [] a = {4, 9, 4, 4, 9, 1, 1, 1};

        int size = a.Length; 

        

        printarr(a, size); 

        quicksort(a, 0, size - 1); 

        printarr(a, size); 

    }

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

}

Выход:

4  9  4  4  1  9  4  4  9  4  4  1  4
1  1  4  4  4  4  4  4  4  4  9  9  9

Спасибо Aditya Goel за эту реализацию.

Ссылка:
http://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf
http://www.sorting-algorithms.com/quick-sort-3-way

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

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

3-Way QuickSort (голландский национальный флаг)

0.00 (0%) 0 votes