Horje
Introduction to Grail Sort

In this article, we will discuss the grail sort. Grail sort is a sorting algorithm that was introduced by Vladimir Yaroslavskiy. It is an efficient sorting algorithm for large data sets that have a lot of duplicate values. The name “grail” refers to the fact that the algorithm is based on the idea of finding a “holy grail” of sorting algorithms that is both fast and capable of handling large amounts of duplicates.

Example:

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

Approach: To solve the problem follow the below steps:

  • Divide the input array into blocks of size sqrt(n), where n is the length of the input array.
  • Sort each block using a comparison-based sorting algorithm.
  • Merge the sorted blocks into a single sorted array using an algorithm similar to merge sort.
  • Repeat steps 2 and 3 until all blocks have been merged into a single sorted array.

Working of above approach:

  1. Divide the array into blocks of size 1:
    • [7] [7] [4] [1] [5] [3] [2]
  2. Merge adjacent blocks:
    • [7, 7] [1, 4] [3, 5] [2]
  3. Rotate the remaining blocks:
    • [7, 7] [4, 1] [5, 3] [2]
  4. Merge adjacent blocks:
    • [1, 4, 7, 7] [2, 3, 5]
  5. Divide the array into blocks of size 2:
    • [1, 4] [7, 7] [2, 3] [5]
  6. Merge adjacent blocks:
    • [1, 4, 7, 7] [2, 3, 5]
  7. Divide the array into blocks of size 4:
    • [1, 4, 7, 7, 2, 3, 5]
  8. (8) Merge adjacent blocks:
    • [1, 2, 3, 4, 5, 7, 7]

Below is the implementation for the above approach:

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

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class GrailSort {
 
    // Grail sort for returning the sorted array
    public static List<Integer> grailSort(List<Integer> arr)
    {
        // Split the array into blocks of size sqrt(n)
        int blockSize = (int)Math.sqrt(arr.size());
        // Determine the block size as
        // sqrt(n)
        int numBlocks
            = (arr.size() + blockSize - 1) / blockSize;
        // Calculate the number
        // of blocks needed
        List<List<Integer> > blocks = new ArrayList<>(
            numBlocks); // Create a list to hold the blocks
        for (int i = 0; i < numBlocks; i++) {
            blocks.add(new ArrayList<>(Collections.nCopies(
                blockSize,
                0))); // Initialize each block with 0s
            Collections.copy(
                blocks.get(i),
                arr.subList(i * blockSize,
                            Math.min((i + 1) * blockSize,
                                     arr.size())));
            // Copy the elements
            // from the original
            // array to the
            // blocks
 
            // Sort the blocks using insertion sort
            for (int j = 1; j < blockSize; j++) {
                int key = blocks.get(i).get(j);
                int k = j - 1;
                while (k >= 0
                       && blocks.get(i).get(k) > key) {
                    blocks.get(i).set(k + 1,
                                      blocks.get(i).get(k));
                    k--;
                }
                blocks.get(i).set(k + 1, key);
            }
        }
 
        // Merge the blocks using an algorithm
        // similar to merge sort and initialize
        // the pointers to the beginning of each block
        List<Integer> pointers
            = new ArrayList<>(Collections.nCopies(
                numBlocks,
                0)); // Create a list to hold the pointers
        List<Integer> result
            = new ArrayList<>(); // Create a list to hold
                                 // the sorted result
        while (true) {
            // Find the minimum element among the
            // active blocks
            int minVal
                = Integer.MAX_VALUE; // Set the minimum
                                     // value as the maximum
                                     // possible integer
            int minIdx = -1;
            for (int i = 0; i < numBlocks; i++) {
                if (pointers.get(i)
                        < blocks.get(i)
                              .size() // Check if the
                                      // pointer is within
                                      // the bounds of the
                                      // block
                    && blocks.get(i).get(pointers.get(i))
                           < minVal) { // Check if the value
                                       // at the pointer is
                                       // less than the
                                       // current minimum
                                       // value
                    minVal = blocks.get(i).get(
                        pointers.get(i));
                    minIdx = i; // Update the index of the
                                // block containing the
                                // minimum value
                }
            }
            // 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.add(minVal);
            pointers.set(minIdx, pointers.get(minIdx) + 1);
        }
 
        return result; // Return the sorted result
    }
 
    // Driver's code
    public static void main(String[] args)
    {
        // Original Array
        List<Integer> arr = List.of(7, 7, 4, 1, 5, 3, 2, 0);
        System.out.print("Input :  ");
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
 
        // Printing result
        List<Integer> result = grailSort(arr);
        System.out.print("Output: ");
        for (int x : result)
            System.out.print(x + " ");
    }
}

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.
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
 
  // grail sort for returning the sorted array
  static List<int> GrailSort(List<int> arr)
  {
 
    // Split the array into blocks of size sqrt(n)
    int blockSize = (int)Math.Sqrt(arr.Count);
    int numBlocks
      = (arr.Count + blockSize - 1) / blockSize;
    List<List<int> > blocks
      = new List<List<int> >(numBlocks);
    for (int i = 0; i < numBlocks; i++) {
      blocks.Add(new List<int>(blockSize));
      blocks[i].AddRange(
        arr.Skip(i * blockSize).Take(blockSize));
      // 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
    List<int> pointers = new List<int>(numBlocks);
    for (int i = 0; i < numBlocks; i++) {
      pointers.Add(0);
    }
    List<int> result = new List<int>();
    while (true) {
      // Find the minimum element among the
      // active blocks
      int minVal = int.MaxValue;
      // minVal currently INT_MAX at start
      int minIdx = -1;
      for (int i = 0; i < numBlocks; i++) {
        if (pointers[i] < blocks[i].Count
            && 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.Add(minVal);
      pointers[minIdx]++;
    }
 
    return result;
  }
 
  static void Main(string[] args)
  {
    // Original Array
    List<int> arr
      = new List<int>{ 7, 7, 4, 1, 5, 3, 2, 0 };
    Console.Write("Input :  ");
    foreach(int x in arr) { Console.Write(x + " "); }
    Console.WriteLine();
 
    // Printing result
    List<int> result = GrailSort(arr);
    Console.Write("Output:  ");
    foreach(int x in result) { Console.Write(x + " "); }
    Console.WriteLine();
  }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// JavaScript code for implementation of the
// above approach
function grail_sort(arr)
{
 
  // Split the array into blocks
  // of size sqrt(n)
  let block_size = parseInt(Math.sqrt(arr.length));
  let num_blocks = Math.ceil(arr.length / block_size);
  let blocks = new Array(num_blocks);
  for (let i = 0; i < num_blocks; i++) {
    blocks[i] = arr.slice(i * block_size, (i + 1) * block_size);
  }
 
  // Sort each block using a
  // comparison sort
  for (let block of blocks) {
    block.sort();
  }
 
  // Merge the blocks using an algorithm
  // similar to merge sort
  // Initialize the pointers to the
  // beginning of each block
  let pointers = new Array(num_blocks).fill(0);
  let result = [];
  while (true)
  {
   
    // Find the minimum element among
    // the active blocks
    let min_val = Infinity;
    let min_idx = null;
    for (let i = 0; i < num_blocks; i++) {
      if (pointers[i] < blocks[i].length && 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 === null) {
      break;
    }
    // Otherwise, add the minimum
    // element to the result and
    // increment the pointer
    // for that block
    result.push(min_val);
    pointers[min_idx]++;
  }
  return result;
}
 
// Original Array
let arr = [7, 7, 4, 1, 5, 3, 2, 0];
console.log("Input: " + arr.join(" "));
 
let result = grail_sort(arr);
 
// Printing result
console.log('Output: '+ result.join(" "));
 
// This code is contributed by Susobhan Akhuli.

Output

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

Time Complexity: O(nlog(n)), where n is the size of the input, 
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimize product of two integers by swapping any number of their digits Minimize product of two integers by swapping any number of their digits
Maximum triplets containing atleast one x and one y Maximum triplets containing atleast one x and one y
Find length of the longest non-intersecting anagram Subsequence Find length of the longest non-intersecting anagram Subsequence
Minimize the indices of consecutive ones Minimize the indices of consecutive ones
Difference between Sequential Organization and Linked Organization Difference between Sequential Organization and Linked Organization

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje