Introduction au Graal Sort - GeeksforGeeks

Introduction au Graal Sort – GeeksforGeeks

Dans cet article, nous aborderons le tri du Graal. Le tri Graal est un algorithme de tri qui a été introduit par Vladimir Yaroslavskiy. Il s’agit d’un algorithme de tri efficace pour les grands ensembles de données contenant de nombreuses valeurs en double. Le nom “Graal” fait référence au fait que l’algorithme est basé sur l’idée de trouver un “Saint Graal” d’algorithmes de tri qui soit à la fois rapide et capable de gérer de grandes quantités de doublons.

Exemple:

Saisir: [7, 7, 4, 1, 5, 3, 2]
Sortir: [1, 2, 3, 4, 5, 7, 7]

Approche: Pour résoudre le problème, suivez les étapes ci-dessous :

Divisez le tableau d’entrée en blocs de taille sqrt(n), où n est la longueur du tableau d’entrée.
Triez chaque bloc à l’aide d’un algorithme de tri basé sur la comparaison.
Fusionnez les blocs triés en un seul tableau trié à l’aide d’un algorithme similaire au tri par fusion.
Répétez les étapes 2 et 3 jusqu’à ce que tous les blocs aient été fusionnés en un seul tableau trié.

Fonctionnement de l’approche ci-dessus :

Divisez le tableau en blocs de taille 1 :

[7] [7] [4] [1] [5] [3] [2]

Fusionner les blocs adjacents :

Faites pivoter les blocs restants :

Fusionner les blocs adjacents :

Divisez le tableau en blocs de taille 2 :

Fusionner les blocs adjacents :

Divisez le tableau en blocs de taille 4 :

(8) Fusionner les blocs adjacents :

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

Python3

# Python code for implementation of the
# above approach


def grail_sort(arr):

    # Split the array into blocks
    # of size sqrt(n)
    block_size = int(len(arr) ** 0.5)
    num_blocks = (len(arr) + block_size - 1) // block_size
    blocks = [arr[i * block_size:(i + 1) * block_size]
              for i in range(num_blocks)]

    # Sort each block using a
    # comparison sort
    for block in blocks:
        block.sort()

    # Merge the blocks using an algorithm
    # similar to merge sort
    # Initialize the pointers to the
    # beginning of each block
    pointers = [0] * num_blocks
    result = []
    while True:

        # Find the minimum element among
        # the active blocks
        min_val = float('inf')
        min_idx = None
        for i in range(num_blocks):
            if pointers[i] < len(blocks[i]) and blocks[i][pointers[i]] < min_val:
                min_val = blocks[i][pointers[i]]
                min_idx = i
        # If all blocks are exhausted,
        # we're done
        if min_idx is None:
            break
        # Otherwise, add the minimum
        # element to the result and
        # increment the pointer
        # for that block
        result.append(min_val)
        pointers[min_idx] += 1

    return result


# Original Array
arr = [7, 7, 4, 1, 5, 3, 2, 0]
print('Input :  ', arr)

# Printing result
print("Output:  ", grail_sort(arr))

C++

// C++ implementation for the above approach.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

// grail sort for returning the sorted array
vector<int> grailSort(vector<int> arr)
{
    // Split the array into blocks of size sqrt(n)
    int blockSize = sqrt(arr.size());
    int numBlocks
        = (arr.size() + blockSize - 1) / blockSize;
    vector<vector<int> > blocks(numBlocks);
    for (int i = 0; i < numBlocks; i++) {
        blocks[i].resize(blockSize);
        copy(arr.begin() + i * blockSize,
             arr.begin() + (i + 1) * blockSize,
             blocks[i].begin());
        // copying values from array to blocks

        // Sort the blocks using insertion sort
        for (int j = 1; j < blockSize; j++) {
            int key = blocks[i][j];
            int k = j - 1;
            while (k >= 0 && blocks[i][k] > key) {
                blocks[i][k + 1] = blocks[i][k];
                k--;
            }
            blocks[i][k + 1] = key;
        }
    }

    // Merge the blocks using an algorithm
    // similar to merge sort and initialize
    // the pointers to the beginning of each block
    vector<int> pointers(numBlocks);
    vector<int> result;
    while (true) {
        // Find the minimum element among the
        // active blocks
        int minVal = numeric_limits<int>::max();
        // minVal currently INT_MAX at start
        int minIdx = -1;
        for (int i = 0; i < numBlocks; i++) {
            if (pointers[i] < blocks[i].size()
                && blocks[i][pointers[i]] < minVal) {
                minVal = blocks[i][pointers[i]];
                minIdx = i;
            }
        }
        // If all blocks are exhausted, we're done
        if (minIdx == -1) {
            break;
        }
        // Otherwise, add the minimum element
        // to the result and increment the
        // pointer for that block
        result.push_back(minVal);
        pointers[minIdx]++;
    }

    return result;
}

// Driver's code
int main()
{
    // Original Array
    vector<int> arr = { 7, 7, 4, 1, 5, 3, 2, 0 };
    cout << "Input :  ";
    for (auto x : arr) {
        cout << x << " ";
    }
    cout << endl;

    // Printing result
    vector<int> result = grailSort(arr);
    cout << "Output:  ";
    for (auto x : result) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

// Contributed by SR.Dhanush

Sortir

Input :   [7, 7, 4, 1, 5, 3, 2, 0]
Output:   [0, 1, 2, 3, 4, 5, 7, 7]

Complexité temporelle : O(nlog(n)), où n est la taille de l’entrée,
Espace Auxiliaire : O(1)