Quotient – Remainder Sort is a non-comparison based sorting algorithm. Steps to perform Quotient – Remainder sort as described below :
- Find MIN and MAX of the array.
- Create an ROW*COL matrix consisting of 0s, where ROW = MAX/MIN+1 and COL = MIN.
- For each element in the input array, calculate quotient and remainder and store in the matrix[quotient][remainder]
- For each element in matrix, if element != 0, append element to sorted array
Examples:
Input : 2 5 3 7 4 8
MAX = 8, MIN = 2, ROW = 4, COL 2
matrix : 2 3
4 5
0 7
8 0
Output : 2 3 4 5 7 8
C++
// CPP program to implement Quotient - Remainder// Sort#include <algorithm>#include <iostream>using namespace std;void QRsort(int arr[], int size){ // max_element finds maximum element in an array int MAX = *max_element(arr, arr + size); // min_element finds minimum element in an array int MIN = *min_element(arr, arr + size); cout << "Maximum Element found is : " << MAX << endl; cout << "Minimum Element found is : " << MIN << endl; int COL = MIN; int ROW = MAX / MIN + 1; // Creating a ROW * COL matrix of all zeros int matrix[ROW][COL] = { 0 }; for (int i = 0; i < size; i++) { int quotient = arr[i] / MIN; int remainder = arr[i] % MIN; matrix[quotient][remainder + 1] = arr[i]; } int k = 0; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (matrix[i][j] != 0) { arr[k++] = matrix[i][j]; } } }}void printArray(int arr[], int size){ for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl;}int main(){ int arr[] = { 5, 3, 7, 4, 8, 2, 6 }; int size = sizeof(arr) / sizeof(arr[0]); cout << "Initial Array : " << endl; printArray(arr, size); QRsort(arr, size); cout << "Array after sorting : " << endl; printArray(arr, size);} |
Java
// Java program to implement // Quotient - Remainder Sort import java.util.*;class GFG {static void QRsort(int arr[], int size) { // max_element finds maximum element in an array int MAX = Arrays.stream(arr).max().getAsInt(); // min_element finds minimum element in an array int MIN = Arrays.stream(arr).min().getAsInt(); System.out.println("Maximum Element found is : " + MAX); System.out.println("Minimum Element found is : " + MIN); int COL = MIN; int ROW = MAX / MIN + 1; // Creating a ROW * COL matrix of all zeros int[][] matrix = new int[ROW][COL]; for (int i = 0; i < size; i++) { int quotient = arr[i] / MIN; int remainder = arr[i] % MIN; matrix[quotient][remainder] = arr[i]; } int k = 0; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (matrix[i][j] != 0) { arr[k++] = matrix[i][j]; } } }}static void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } System.out.println();}// Driver Codepublic static void main(String[] args){ int arr[] = {5, 3, 7, 4, 8, 2, 6}; int size = arr.length; System.out.println("Initial Array : "); printArray(arr, size); QRsort(arr, size); System.out.println("Array after sorting : "); printArray(arr, size);}}// This code is contributed by Princi Singh |
Python3
# Python program to implement Quotient - Remainder# Sortdef QRsort(arr, size): # max_element finds maximum element in an array MAX = max(arr) # min_element finds minimum element in an array MIN = min(arr) print("Maximum Element found is : {}".format(MAX)) print("Minimum Element found is : {}".format(MIN)) COL = MIN ROW = (MAX//MIN) + 1 # Creating a ROW * COL matrix of all zeros matrix = [[0 for i in range(COL)] for j in range(ROW)] for i in range(size): quotient = arr[i]//MIN remainder = arr[i] % MIN matrix[quotient][remainder] = arr[i] k = 0 for i in range(ROW): for j in range(COL): if(matrix[i][j] != 0): arr[k] = matrix[i][j] k = k + 1def printArray(arr, size): for i in range(size): print(arr[i], end = ' ') print()# Driver Codearr = [5, 3, 7, 4, 8, 2, 6]size = len(arr)print("Initial Array : ")printArray(arr, size)QRsort(arr, size)print("Array after sorting : ")printArray(arr, size)# This code is contributed by Pushpesh Raj |
C#
// C# program to implement // Quotient - Remainder Sort using System;using System.Linq;class GFG {static void QRsort(int []arr, int size) { // max_element finds maximum element in an array int MAX = arr.Max(); // min_element finds minimum element in an array int MIN = arr.Min(); Console.WriteLine("Maximum Element found is : " + MAX); Console.WriteLine("Minimum Element found is : " + MIN); int COL = MIN; int ROW = MAX / MIN + 1; // Creating a ROW * COL matrix of all zeros int[,] matrix = new int[ROW, COL]; for (int i = 0; i < size; i++) { int quotient = arr[i] / MIN; int remainder = arr[i] % MIN; matrix[quotient, remainder] = arr[i]; } int k = 0; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (matrix[i, j] != 0) { arr[k++] = matrix[i, j]; } } }}static void printArray(int []arr, int size) { for (int i = 0; i < size; i++) { Console.Write(arr[i] + " "); } Console.WriteLine();}// Driver Codepublic static void Main(String[] args){ int []arr = {5, 3, 7, 4, 8, 2, 6}; int size = arr.Length; Console.WriteLine("Initial Array : "); printArray(arr, size); QRsort(arr, size); Console.WriteLine("Array after sorting : "); printArray(arr, size);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to implement // Quotient - Remainder Sort function QRsort(arr , size) { // max_element finds maximum element in an array var MAX = Math.max.apply(null, arr); // min_element finds minimum element in an array var MIN = Math.min.apply(null, arr); document.write("Maximum Element found is : " + MAX); document.write("<br>Minimum Element found is : " + MIN); var COL = MIN; var ROW = MAX / MIN + 1; // Creating a ROW * COL matrix of all zeros var matrix = Array(ROW).fill(0).map(x => Array(COL).fill(0));; for (var i = 0; i < size; i++) { var quotient = parseInt(arr[i] / MIN); var remainder = arr[i] % MIN; matrix[quotient][remainder] = arr[i]; } var k = 0; for (var i = 0; i < ROW; i++) { for (var j = 0; j < COL; j++) { if (matrix[i][j] != 0) { arr[k++] = matrix[i][j]; } } }}function printArray(arr , size) { for (var i = 0; i < size; i++) { document.write(arr[i] + " "); } document.write('<br>');}// Driver Codevar arr = [5, 3, 7, 4, 8, 2, 6];var size = arr.length;document.write("Initial Array : ");printArray(arr, size);QRsort(arr, size);document.write("Array after sorting : <br>");printArray(arr, size);// This code is contributed by shikhasingrajput </script> |
Output:
Initial Array : 5 3 7 4 8 2 6 Maximum Element found is : 8 Minimum Element found is : 2 Array after sorting : 2 3 4 5 6 7 8
Time Complexity: O(r*c) where c = MIN and r = MAX/MIN where MAX and MIN are the maximum and minimum elements of the array respectively.
Auxiliary Space: O(r*c)
References
Abul Hasnat, Tanima Bhattacharyya, Atanu Dey, Santanu Halder, and Debotosh Bhattachajee, 2017. A Novel Sorting Algorithm using Quotient and Remainder,
J. Eng. Applied Sci, 12 (Special Issue 7): 8016-8020, 2017, ISSN : 1816-949X
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
