Dada una gran lista de fechas en los años 20, cómo ordenar la lista de manera eficiente.
Ejemplo:
Input:
Date arr[] = {{20, 1, 2014},
{25, 3, 2010},
{ 3, 12, 2000},
{18, 11, 2001},
{19, 4, 2015},
{ 9, 7, 2005}}
Output:
Date arr[] = {{ 3, 12, 2000},
{18, 11, 2001},
{ 9, 7, 2005},
{25, 3, 2010},
{20, 1, 2014},
{19, 4, 2015}}
Una solución simple es usar un algoritmo O (N log N) como Merge Sort y un comparador personalizado. Pero podemos ordenar la lista en tiempo O(n) usando Radix Sort . En una implementación típica de Radix Sort , primero ordenamos por el último dígito, luego por el penúltimo dígito, y así sucesivamente. Se recomienda encarecidamente pasar primero por la ordenación radix para comprender este método. En este método ordenamos en el siguiente orden:
- Primero ordene por día usando la ordenación por conteo
- Luego ordene por mes usando la ordenación por conteo
- Finalmente, ordene por año usando ordenamiento por conteo
Como el número de días, meses y años es fijo, los tres pasos toman O(n) tiempo. Por lo tanto, la complejidad temporal total es O(n).
A continuación se muestra la implementación en C++ de la idea anterior:
C++
// C++ program to sort an array
// of dates using Radix Sort
#include <bits/stdc++.h>
using namespace std;
// Utilitiy function to obtain
// maximum date or month or year
int getMax(int arr[][3],int n, int q)
{
int maxi = INT_MIN;
for(int i=0;i<n;i++){
maxi = max(maxi,arr[i][q]);
}
return maxi;
}
// A function to do counting sort of arr[]
// according to given q i.e.
// (0 for day, 1 for month, 2 for year)
void sortDatesUtil(int arr[][3],
int n, int q)
{
int maxi = getMax(arr,n,q);
int p = 1;
while(maxi>0){
//to extract last digit divide
// by p then %10
// Store count of occurrences in cnt[]
int cnt[10]={0};
for(int i=0;i<n;i++)
{
cnt[(arr[i][q]/p)%10]++;
}
for(int i=1;i<10;i++)
{
cnt[i]+=cnt[i-1];
}
int ans[n][3];
for(int i=n-1;i>=0;i--)
{
int lastDigit = (arr[i][q]/p)%10;
// Build the output array
for(int j=0;j<3;j++)
{
ans[cnt[lastDigit]-1][j]
=arr[i][j];
}
cnt[lastDigit]--;
}
// Copy the output array to arr[],
// so that arr[] now
// contains sorted numbers
// according to current digit
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{
arr[i][j] = ans[i][j];
}
}
// update p to get
// the next digit
p*=10;
maxi/=10;
}
}
// The main function that sorts
// array of dates
// using Radix Sort
void sortDates(int dates[][3], int n)
{
// First sort by day
sortDatesUtil(dates, n, 0);
// Then by month
sortDatesUtil(dates, n, 1);
// Finally by year
sortDatesUtil(dates, n, 2);
}
// A utility function to print an array
void printArr(int arr[][3], int n)
{
for(int i=0;i<6;i++)
{
for(int j=0;j<3;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
// Driver Code
int main()
{
int dates[][3] = {{20, 1, 2014},
{25, 3, 2010},
{ 3, 12, 2000},
{18, 11, 2000},
{19, 4, 2015},
{ 9, 7, 2005}};
int n = sizeof(dates)/sizeof(dates[0]);
// Function Call
sortDates(dates,n);
cout<<"\nSorted Dates\n";
printArr(dates,n);
return 0;
}
Java
// Java program to sort an array
// of dates using Radix Sort
import java.util.*;
class GFG{
// Utilitiy function to obtain
// maximum date or month or year
static int getMax(int arr[][], int n, int q)
{
int maxi = Integer.MIN_VALUE;
for(int i = 0; i < n; i++)
{
maxi = Math.max(maxi, arr[i][q]);
}
return maxi;
}
// A function to do counting sort of arr[]
// according to given q i.e.
// (0 for day, 1 for month, 2 for year)
static void sortDatesUtil(int arr[][],
int n, int q)
{
int maxi = getMax(arr,n,q);
int p = 1;
while(maxi > 0)
{
// to extract last digit divide
// by p then %10
// Store count of occurrences in cnt[]
int []cnt = new int[10];
for(int i = 0; i < n; i++)
{
cnt[(arr[i][q]/p) % 10]++;
}
for(int i = 1; i < 10; i++)
{
cnt[i] += cnt[i - 1];
}
int [][]ans = new int[n][3];
for(int i = n - 1; i >= 0; i--)
{
int lastDigit = (arr[i][q]/p) % 10;
// Build the output array
for(int j = 0; j < 3; j++)
{
ans[cnt[lastDigit]-1][j]
=arr[i][j];
}
cnt[lastDigit]--;
}
// Copy the output array to arr[],
// so that arr[] now
// contains sorted numbers
// according to current digit
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 3; j++)
{
arr[i][j] = ans[i][j];
}
}
// update p to get
// the next digit
p *= 10;
maxi /= 10;
}
}
// The main function that sorts
// array of dates
// using Radix Sort
static void sortDates(int dates[][], int n)
{
// First sort by day
sortDatesUtil(dates, n, 0);
// Then by month
sortDatesUtil(dates, n, 1);
// Finally by year
sortDatesUtil(dates, n, 2);
}
// A utility function to print an array
static void printArr(int arr[][], int n)
{
for(int i = 0; i < 6; i++)
{
for(int j = 0; j < 3; j++)
{
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
int dates[][] = {{20, 1, 2014},
{25, 3, 2010},
{ 3, 12, 2000},
{18, 11, 2000},
{19, 4, 2015},
{ 9, 7, 2005}};
int n = dates.length;
// Function Call
sortDates(dates,n);
System.out.print("\nSorted Dates\n");
printArr(dates,n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to sort an array
# of dates using Radix Sort
import sys
# Utilitiy function to obtain
# maximum date or month or year
def getMax(arr, n, q):
maxi = sys.maxsize;
for i in range(n):
maxi = max(maxi, arr[i][q]);
return maxi;
# A function to do counting sort of arr
# according to given q i.e.
# (0 for day, 1 for month, 2 for year)
def sortDatesUtil(arr, n, q):
maxi = getMax(arr, n, q);
p = 1;
while (maxi > 0):
# to extract last digit divide
# by p then %10
# Store count of occurrences in cnt
cnt = [0 for i in range(10)];
for i in range(n):
cnt[(arr[i][q] // p) % 10]+=1;
for i in range(1,10):
cnt[i] += cnt[i - 1];
ans = [[0 for i in range(3)] for j in range(n)];
for i in range(n-1, -1,-1):
lastDigit = (arr[i][q] // p) % 10;
# Build the output array
for j in range(3):
ans[cnt[lastDigit] - 1][j] = arr[i][j];
cnt[lastDigit] -= 1;
# Copy the output array to arr,
# so that arr now
# contains sorted numbers
# according to current digit
for i in range(n):
for j in range(3):
arr[i][j] = ans[i][j];
# update p to get
# the next digit
p *= 10;
maxi = maxi//10;
# The main function that sorts
# array of dates
# using Radix Sort
def sortDates(dates, n):
# First sort by day
sortDatesUtil(dates, n, 0);
# Then by month
sortDatesUtil(dates, n, 1);
# Finally by year
sortDatesUtil(dates, n, 2);
# A utility function to print an array
def printArr(arr, n):
for i in range(6):
for j in range(3):
print(arr[i][j], end=" ");
print();
# Driver Code
if __name__ == '__main__':
dates = [[ 20, 1, 2014 ],[ 25, 3, 2010 ],[ 3, 12, 2000 ],[ 18, 11, 2000 ],[ 19, 4, 2015 ],
[ 9, 7, 2005 ]] ;
n = len(dates);
# Function Call
sortDates(dates, n);
print("\nSorted Dates");
printArr(dates, n);
# This code is contributed by gauravrajput1
C#
// C# program to sort an array
// of dates using Radix Sort
using System;
public class GFG
{
// Utilitiy function to obtain
// maximum date or month or year
static int getMax(int [,]arr, int n, int q)
{
int maxi = int.MinValue;
for(int i = 0; i < n; i++)
{
maxi = Math.Max(maxi, arr[i,q]);
}
return maxi;
}
// A function to do counting sort of []arr
// according to given q i.e.
// (0 for day, 1 for month, 2 for year)
static void sortDatesUtil(int [,]arr,
int n, int q)
{
int maxi = getMax(arr,n,q);
int p = 1;
while(maxi > 0)
{
// to extract last digit divide
// by p then %10
// Store count of occurrences in cnt[]
int []cnt = new int[10];
for(int i = 0; i < n; i++)
{
cnt[(arr[i,q]/p) % 10]++;
}
for(int i = 1; i < 10; i++)
{
cnt[i] += cnt[i - 1];
}
int [,]ans = new int[n,3];
for(int i = n - 1; i >= 0; i--)
{
int lastDigit = (arr[i,q]/p) % 10;
// Build the output array
for(int j = 0; j < 3; j++)
{
ans[cnt[lastDigit]-1,j]
=arr[i,j];
}
cnt[lastDigit]--;
}
// Copy the output array to []arr,
// so that []arr now
// contains sorted numbers
// according to current digit
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 3; j++)
{
arr[i,j] = ans[i,j];
}
}
// update p to get
// the next digit
p *= 10;
maxi /= 10;
}
}
// The main function that sorts
// array of dates
// using Radix Sort
static void sortDates(int [,]dates, int n)
{
// First sort by day
sortDatesUtil(dates, n, 0);
// Then by month
sortDatesUtil(dates, n, 1);
// Finally by year
sortDatesUtil(dates, n, 2);
}
// A utility function to print an array
static void printArr(int [,]arr, int n)
{
for(int i = 0; i < 6; i++)
{
for(int j = 0; j < 3; j++)
{
Console.Write(arr[i, j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
int [,]dates = {{20, 1, 2014},
{25, 3, 2010},
{ 3, 12, 2000},
{18, 11, 2000},
{19, 4, 2015},
{ 9, 7, 2005}};
int n = dates.GetLength(0);
// Function Call
sortDates(dates,n);
Console.Write("\nSorted Dates\n");
printArr(dates,n);
}
}
// This code is contributed by aashish1995.
Javascript
<script>
// javascript program to sort an array
// of dates using Radix Sort
// Utilitiy function to obtain
// maximum date or month or year
function getMax(arr , n , q) {
var maxi = Number.MIN_VALUE;
for (var i = 0; i < n; i++) {
maxi = Math.max(maxi, arr[i][q]);
}
return maxi;
}
// A function to do counting sort of arr
// according to given q i.e.
// (0 for day, 1 for month, 2 for year)
function sortDatesUtil(arr , n , q)
{
var maxi = getMax(arr, n, q);
var p = 1;
while (maxi > 0)
{
// to extract last digit divide
// by p then %10
// Store count of occurrences in cnt
var cnt = Array(10).fill(0);
for (var i = 0; i < n; i++) {
cnt[parseInt((arr[i][q] / p)) % 10]++;
}
for (var i = 1; i < 10; i++) {
cnt[i] += cnt[i - 1];
}
var ans = Array(n).fill().map(()=>Array(3).fill(0));
for (var i = n - 1; i >= 0; i--) {
var lastDigit = parseInt((arr[i][q] / p) % 10);
// Build the output array
for (var j = 0; j < 3; j++) {
ans[cnt[lastDigit] - 1][j] = arr[i][j];
}
cnt[lastDigit]--;
}
// Copy the output array to arr,
// so that arr now
// contains sorted numbers
// according to current digit
for (var i = 0; i < n; i++) {
for (var j = 0; j < 3; j++) {
arr[i][j] = ans[i][j];
}
}
// update p to get
// the next digit
p *= 10;
maxi = parseInt(maxi/10);
}
}
// The main function that sorts
// array of dates
// using Radix Sort
function sortDates(dates , n) {
// First sort by day
sortDatesUtil(dates, n, 0);
// Then by month
sortDatesUtil(dates, n, 1);
// Finally by year
sortDatesUtil(dates, n, 2);
}
// A utility function to print an array
function printArr(arr , n) {
for (var i = 0; i < 6; i++) {
for (var j = 0; j < 3; j++) {
document.write(arr[i][j] + " ");
}
document.write("<br/>");
}
}
// Driver Code
var dates = [ [ 20, 1, 2014 ],
[ 25, 3, 2010 ],
[ 3, 12, 2000 ],
[ 18, 11, 2000 ],
[ 19, 4, 2015 ],
[ 9, 7, 2005 ] ];
var n = dates.length;
// Function Call
sortDates(dates, n);
document.write("\nSorted Dates\n");
printArr(dates, n);
// This code is contributed by gauravrajput1
</script>
Producción
Sorted Dates 18 11 2000 3 12 2000 9 7 2005 25 3 2010 20 1 2014 19 4 2015
Este artículo es una contribución de tpriyanshu . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA