Dada una array , arr[] de N elementos, donde cada elemento está como máximo a K de su posición de destino, la tarea es diseñar un algoritmo que ordene en tiempo O(N*log(K)) .
Ejemplos:
Entrada: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, K = 4
Salida: 4 7 8 9 10 50 60 70
Explicación:
siga los pasos a continuación para ordenar la array:
- Comience con Gap = K (es decir, 4)
- 10 9 8 7 4 70 60 50, intercambie los elementos en los índices 0 y 4. Luego, la array se modifica a {4, 9, 8, 7, 10, 70, 60, 50}.
4 9 8 7 10 70 60 50, No intercambie los elementos en los índices 1 y 5.
4 9 8 7 10 70 60 50, No intercambie los elementos en los índices 2 y 6.
4 9 8 7 10 70 60 50, Sí no intercambie los elementos en los índices 3 y 7.- Brecha = techo de 4/2 = 2
- 4 9 8 7 10 70 60 50, no intercambie los elementos en los índices 0 y 2.
4 9 8 7 10 70 60 50, intercambie los elementos en los índices 1 y 3. Luego, la array se modifica a {4, 7, 8, 9, 10, 70, 60, 50}.
4 7 8 9 10 70 60 50, No intercambie los elementos en los índices 2 y 4.
4 7 8 9 10 70 60 50, No intercambie los elementos en los índices 3 y 5.
4 7 8 9 10 70 60 50, Sí no intercambie los elementos en los índices 4 y 6.
4 7 8 9 10 70 60 50,intercambie los elementos en los índices 5 y 7. Luego, la array se modifica a {4, 7, 8, 9, 10, 70, 60, 50}.
4 7 8 9 10 50 60 70- Brecha = techo de 2/2 = 1
- 4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 0 y 1.
4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 1 y 2.
4 7 8 9 10 50 60 70, Sí no intercambie los elementos en los índices 2 y 3.
4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 3 y 4.
4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 4 y 5.
4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 5 y 6.
4 7 8 9 10 50 60 70, No intercambie los elementos en los índices 6 y 7.Entrada: arr[] = {6, 5, 3, 2, 8, 10, 9}, K = 3
Salida: 2 3 5 6 8 9 10
Enfoque: El problema dado Ordenar una array casi ordenada (o K ordenada) ya está resuelto. Aquí la idea es usar la ordenación de shell para ordenar la array. La idea utilizada aquí es similar al paso de fusión de In-Place Merge Sort . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos Gap con un valor K para ordenar cada elemento Gap de cada sublista .
- Iterar hasta que Gap sea mayor que 0 y realizar los siguientes pasos:
- Itere sobre el rango [0, N-Gap] usando la variable i , y en cada iteración, si arr[i] es mayor que arr[i+Gap], entonces intercambie los elementos de la array.
- Actualice el Gap como Gap = ceil (Gap/2).
- Finalmente, después de completar el paso anterior, imprima los elementos de la array arr[] .
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the nextGap
int nextGap(double k)
{
if (k < 2)
return 0;
return ceil(k / 2);
}
// A utility function to print the array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Function to sort a K sorted array
void kSort(int arr[], int K, int n)
{
// Iterate until gap is atleast
// greater than 0
for (int gap = K; gap > 0; gap = nextGap(gap)) {
// Iterate over the range [0, N]
for (int i = 0; i + gap < n; i++) {
// If arr[i] is greater
// than arr[i+gap]
if (arr[i] > arr[i + gap]) {
// Swap arr[i] and
// arr[i+gap]
swap(arr[i], arr[i + gap]);
}
}
}
printArray(arr, n);
}
// Driver Code
int main()
{
// Input
int arr[] = { 10, 9, 8, 7, 4, 70, 60, 50 };
int K = 3;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
kSort(arr, K, n);
return 0;
}
// This code is contributed by lokesh potta.
Java
// Java program for the above approach
import java.util.Iterator;
import java.util.PriorityQueue;
class GFG {
// Function to sort a K sorted array
static void kSort(int[] arr, int K)
{
// Iterate until gap is atleast
// greater than 0
for (int gap = K; gap > 0; gap = nextGap(gap)) {
// Iterate over the range [0, N]
for (int i = 0; i + gap < arr.length; i++) {
// If arr[i] is greater
// than arr[i+gap]
if (arr[i] > arr[i + gap]) {
// Swap arr[i] and
// arr[i+gap]
swap(arr, i, i + gap);
}
}
}
printArray(arr);
}
// Function to find the nextGap
static int nextGap(double k)
{
if (k < 2)
return 0;
return (int)Math.ceil(k / 2);
}
// Function to swap two elements
// of the array arr[]
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A utility function to print the array
private static void printArray(int[] arr)
{
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Input
int arr[] = { 10, 9, 8, 7, 4, 70, 60, 50 };
int K = 3;
// Function call
kSort(arr, K);
}
}
Python3
# Python3 program for the above approach import math # Function to find the nextGap def nextGap(k): if (k < 2): return 0 return math.ceil(k / 2) # A utility function to print array def printArray(arr, n): for i in range(n): print(arr[i], end = " ") # Function to sort a K sorted array def kSort(arr, K, n): # Iterate until gap is atleast # greater than 0 gap = K while (gap > 0): # Iterate over the range [0, N] i = 0 while (i + gap < n): # If arr[i] is greater # than arr[i+gap] if (arr[i] > arr[i + gap]): # Swap arr[i] and # arr[i+gap] arr[i], arr[i + gap] = arr[i + gap], arr[i] i += 1 gap = nextGap(gap) printArray(arr, n) # Driver Code # Input arr = [ 10, 9, 8, 7, 4, 70, 60, 50 ] K = 3 n = len(arr) # Function call kSort(arr, K, n) # This code is contributed by target_2
C#
// C# program for the above approach
using System;
class GFG {
// Function to sort a K sorted array
static void kSort(int[] arr, int K)
{
// Iterate until gap is atleast
// greater than 0
for (int gap = K; gap > 0; gap = nextGap(gap)) {
// Iterate over the range [0, N]
for (int i = 0; i + gap < arr.Length; i++) {
// If arr[i] is greater
// than arr[i+gap]
if (arr[i] > arr[i + gap]) {
// Swap arr[i] and
// arr[i+gap]
swap(arr, i, i + gap);
}
}
}
printArray(arr);
}
// Function to find the nextGap
static int nextGap(double k)
{
if (k < 2)
return 0;
return (int)Math.Ceiling(k / 2);
}
// Function to swap two elements
// of the array arr[]
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A utility function to print the array
private static void printArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(string[] args)
{
// Input
int []arr = { 10, 9, 8, 7, 4, 70, 60, 50 };
int K = 3;
// Function call
kSort(arr, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find the nextGap
function nextGap(k)
{
if (k < 2)
return 0;
return Math.ceil(k / 2);
}
// A utility function to print the array
function printArray(arr, n)
{
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to sort a K sorted array
function kSort(arr, K, n)
{
// Iterate until gap is atleast
// greater than 0
for(let gap = K; gap > 0; gap = nextGap(gap))
{
// Iterate over the range [0, N]
for(let i = 0; i + gap < n; i++)
{
// If arr[i] is greater
// than arr[i+gap]
if (arr[i] > arr[i + gap])
{
// Swap arr[i] and
// arr[i+gap]
let temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
}
}
}
printArray(arr, n);
}
// Driver Code
// Input
let arr = [ 10, 9, 8, 7, 4, 70, 60, 50 ];
let K = 3;
let n = arr.length;
// Function call
kSort(arr, K, n);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
4 7 8 9 10 50 60 70
Complejidad de tiempo: O(N*log K)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mittulmandhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA