Cociente – Ordenación por resto

Posted on by Rudeus Greyrat

Quotient – ​​Remainder Sort es un algoritmo de clasificación que no se basa en la comparación. Pasos para realizar la clasificación Cociente – Resto como se describe a continuación: 

  1. Encuentre MIN y MAX de la array.
  2. Cree una array ROW*COL que consta de 0, donde ROW = MAX/MIN+1 y COL = MIN.
  3. Para cada elemento en la array de entrada, calcule el cociente y el resto y guárdelo en la array[cociente][resto]
  4. Para cada elemento en la array, si el elemento! = 0, agregue el elemento a la array ordenada

Ejemplos:  

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 Code
public 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
# Sort
def 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 + 1
 
def printArray(arr, size):
    for i in range(size):
        print(arr[i], end = ' ')
    print()
 
# Driver Code
arr = [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 Code
public 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 Code
var 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>
Producción: 

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

 

Complejidad de tiempo : O(r*c) donde c = MIN y r = MAX/MIN donde MAX y MIN son los elementos máximo y mínimo de la array respectivamente.
Espacio Auxiliar : O(r*c)

Referencias 
Abul Hasnat, Tanima Bhattacharyya, Atanu Dey, Santanu Halder y Debotosh Bhattachajee, 2017. A Novel Sorting Algorithm using Quotient and Remainder, 
J. Eng. Applied Sci, 12 (número especial 7): 8016-8020, 2017, ISSN: 1816-949X

Publicación traducida automáticamente

Artículo escrito por BabanGain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *