Ordenar una array casi ordenada (o K ordenada)

Dada una array de n elementos, donde cada elemento está a lo sumo k lejos de su posición objetivo, diseñe un algoritmo que ordene en O (n log k) tiempo. Por ejemplo, consideremos k es 2, un elemento en el índice 7 en la array ordenada, puede estar en los índices 5, 6, 7, 8, 9 en la array dada.

Ejemplos: 

Entrada: arr[] = {6, 5, 3, 2, 8, 10, 9}
            k = 3 
Salida: arr[] = {2, 3, 5, 6, 8, 9, 10}

Entrada: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}
         k = 4
Salida: arr[] = {4, 7, 8, 9, 10, 50, 60, 70}

Podemos usar la ordenación por inserción para ordenar los elementos de manera eficiente. A continuación se muestra el código C para la clasificación por inserción estándar.  

/* Function to sort an array using insertion sort*/
void insertionSort(int A[], int size)
{
   int i, key, j;
   for(i = 1; i < size; i++)
   {
       key = A[i];
       j = i - 1;
 
       /* Move elements of A[0..i-1], that are
          greater than key, to one
          position ahead of their current position.
          This loop will run at most k times */
       while (j >= 0 && A[j] > key)
       {
           A[j + 1] = A[j];
           j = j - 1;
       }
       A[j + 1] = key;
   }
}
 
// This code is contributed by Shivani

/* Function to sort an array using insertion sort*/
void insertionSort(int A[], int size)
{
   int i, key, j;
   for (i = 1; i < size; i++)
   {
       key = A[i];
       j = i-1;
 
       /* Move elements of A[0..i-1], that are
          greater than key, to one
          position ahead of their current position.
          This loop will run at most k times */
       while (j >= 0 && A[j] > key)
       {
           A[j+1] = A[j];
           j = j-1;
       }
       A[j+1] = key;
   }
}

/* Function to sort an array using insertion sort*/
static void insertionSort(int A[], int size)
{
    int i, key, j;
    for (i = 1; i < size; i++)
    {
        key = A[i];
        j = i-1;
 
        /* Move elements of A[0..i-1], that
            are greater than key, to one
            position ahead of their current position.
            This loop will run at most k times */
        while (j >= 0 && A[j] > key)
        {
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = key;
    }
}

# Function to sort an array using
# insertion sort
 
def insertionSort(A, size):
    i, key, j = 0, 0, 0
    for i in range(size):
        key = A[i]
        j = i-1
 
        # Move elements of A[0..i-1], that are
        # greater than key, to one position
        # ahead of their current position.
        # This loop will run at most k times
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

/* C# Function to sort an array using insertion sort*/
static void insertionSort(int A[], int size)
{
    int i, key, j;
   
    for (i = 1; i < size; i++) {
        key = A[i];
        j = i - 1;
 
        /* Move elements of A[0..i-1], that are greater than
           key, to one position ahead of their current
           position. This loop will run at most k times */
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j + 1] = key;
    }
}

/* Function to sort an array using insertion sort*/
function insertionSort(A, size)
{
   var i, key, j;
   for (i = 1; i < size; i++)
   {
       key = A[i];
       j = i-1;
 
       /* Move elements of A[0..i-1], that are
          greater than key, to one
          position ahead of their current position.
          This loop will run at most k times */
       while (j >= 0 && A[j] > key)
       {
           A[j+1] = A[j];
           j = j-1;
       }
       A[j+1] = key;
   }
}
 
// This code is contributed by itsok.

Complejidad de tiempo: O (nk), el bucle interno se ejecutará como máximo k veces. Para mover cada elemento a su lugar correcto, es necesario mover como máximo k elementos. 
Espacio Auxiliar: O(1)

Podemos ordenar dichas arrays de manera más eficiente con la ayuda de la estructura de datos Heap . A continuación se muestra el proceso detallado que utiliza Heap. 
1) Cree un montón mínimo de tamaño k+1 con los primeros k+1 elementos. Esto llevará O(k) tiempo (Ver este GFact ). Estamos creando un montón de tamaño k, ya que el elemento puede estar como máximo a una distancia k de su índice en una array ordenada. 
2) Uno por uno, elimine el elemento mínimo del montón, colóquelo en la array de resultados y agregue un nuevo elemento al montón de los elementos restantes.
Quitar un elemento y agregar un nuevo elemento al montón mínimo llevará un tiempo log k. Entonces, la complejidad general será O(k) + O((nk) * log(k)).

// A STL based C++ program to sort a nearly sorted array.
#include <bits/stdc++.h>
using namespace std;
 
// Given an array of size n, where every element
// is k away from its target position, sorts the
// array in O(n logk) time.
void sortK(int arr[], int n, int k)
{
     
    // Insert first k+1 items in a priority queue (or min
    // heap)
    //(A O(k) operation). We assume, k < n.
  //if size of array = k i.e k away from its target position
  //then
    int size;
    size=(n==k)?k:k+1;
    priority_queue<int, vector<int>, greater<int> > pq(arr, arr +size);
 
    // i is index for remaining elements in arr[] and index
    // is target index of for current minimum element in
    // Min Heap 'pq'.
    int index = 0;
    for (int i = k + 1; i < n; i++) {
        arr[index++] = pq.top();
        pq.pop();
        pq.push(arr[i]);
    }
 
    while (pq.empty() == false) {
        arr[index++] = pq.top();
        pq.pop();
    }
}
 
// A utility function to print array elements
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver program to test above functions
int main()
{
    int k = 3;
    int arr[] = { 2, 6, 3, 12, 56, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortK(arr, n, k);
 
    cout << "Following is sorted array" << endl;
    printArray(arr, n);
 
    return 0;
}

// A java program to sort a nearly sorted array
import java.util.Iterator;
import java.util.PriorityQueue;
 
class GFG {
    private static void kSort(int[] arr, int n, int k)
    {
        if (arr == null || arr.length == 0) {
          return;
        }
        // min heap
        PriorityQueue<Integer> priorityQueue
            = new PriorityQueue<>();
       // if there are less than k + 1 elements present in the array
        int minCount = Math.min(arr.length, k + 1);
        // add first k + 1 items to the min heap
        for (int i = 0; i < minCount; i++) {
            priorityQueue.add(arr[i]);
        }
 
        int index = 0;
        for (int i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue.peek();
            priorityQueue.poll();
            priorityQueue.add(arr[i]);
        }
 
        Iterator<Integer> itr = priorityQueue.iterator();
 
        while (itr.hasNext()) {
            arr[index++] = priorityQueue.peek();
            priorityQueue.poll();
        }
    }
 
    // A utility function to print the array
    private static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int k = 3;
        int arr[] = { 2, 6, 3, 12, 56, 8 };
        int n = arr.length;
        kSort(arr, n, k);
        System.out.println("Following is sorted array");
        printArray(arr, n);
    }
}
 
// This code is contributed by
// Manpreet Singh(manpreetsngh294)

# A Python3 program to sort a
# nearly sorted array.
 
from heapq import heappop, heappush, heapify
 
 
# A utility function to print
# array elements
def print_array(arr: list):
    for elem in arr:
        print(elem, end=' ')
 
# Given an array of size n, where every
# element is k away from its target
# position, sorts the array in O(nLogk) time.
 
 
def sort_k(arr: list, n: int, k: int):
    """
    :param arr: input array
    :param n: length of the array
    :param k: max distance, which every
     element is away from its target position.
    :return: None
    """
    # List of first k+1 items
    heap = arr[:k + 1]
 
    # using heapify to convert list
    # into heap(or min heap)
    heapify(heap)
 
    # "rem_elmnts_index" is index for remaining
    # elements in arr and "target_index" is
    # target index of for current minimum element
    # in Min Heap "heap".
    target_index = 0
    for rem_elmnts_index in range(k + 1, n):
        arr[target_index] = heappop(heap)
        heappush(heap, arr[rem_elmnts_index])
        target_index += 1
 
    while heap:
        arr[target_index] = heappop(heap)
        target_index += 1
 
 
# Driver Code
k = 3
arr = [2, 6, 3, 12, 56, 8]
n = len(arr)
sort_k(arr, n, k)
 
print('Following is sorted array')
print_array(arr)
 
# This code is contributed by
# Veerat Beri(viratberi)

// A C# program to sort a nearly sorted array
using System;
using System.Collections.Generic;
class GFG {
 
    static void kSort(int[] arr, int n, int k)
    {
 
        // min heap
        List<int> priorityQueue = new List<int>();
 
        // add first k + 1 items to the min heap
        for (int i = 0; i < k + 1; i++) {
            priorityQueue.Add(arr[i]);
        }
 
        priorityQueue.Sort();
 
        int index = 0;
        for (int i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.RemoveAt(0);
            priorityQueue.Add(arr[i]);
            priorityQueue.Sort();
        }
 
        int queue_size = priorityQueue.Count;
 
        for (int i = 0; i < queue_size; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.RemoveAt(0);
        }
    }
 
    // A utility function to print the array
    static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver code
    static void Main()
    {
        int k = 3;
        int[] arr = { 2, 6, 3, 12, 56, 8 };
        int n = arr.Length;
        kSort(arr, n, k);
        Console.WriteLine("Following is sorted array");
        printArray(arr, n);
    }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// A javascript program to sort a nearly sorted array
 
function kSort(arr,n,k)
{
    let priorityQueue=[];
    // add first k + 1 items to the min heap
        for (let i = 0; i < k + 1; i++) {
            priorityQueue.push(arr[i]);
        }
        priorityQueue.sort(function(a,b){return a-b;});
  
        let index = 0;
        for (let i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.shift();
            priorityQueue.push(arr[i]);
            priorityQueue.sort(function(a,b){return a-b;});
        }
  
         
  
        while (priorityQueue.length != 0) {
            arr[index++] = priorityQueue[0];
            priorityQueue.shift();
        }
}
 
// A utility function to print the array
function printArray(arr,n)
{
    for (let i = 0; i < n; i++)
            document.write(arr[i] + " ");
}
 
// Driver Code
let k = 3;
let arr = [ 2, 6, 3, 12, 56, 8 ];
let n = arr.length;
kSort(arr, n, k);
document.write("Following is sorted array<br>");
printArray(arr, n);
 
// This code is contributed by unknown2108
</script>

Following is sorted array
2 3 6 8 12 56 

Complejidad de tiempo: O(k) + O((m) * log(k)), donde m = n – k
Espacio auxiliar: O(k)

También podemos usar un árbol de búsqueda binaria balanceada en lugar de Heap para almacenar k+1 elementos. Las operaciones de inserción y eliminación en BST balanceado también toman tiempo O (log k). Por lo tanto, el método basado en BST equilibrado también tomará un tiempo O (n log k), pero el método basado en Heap parece ser más eficiente ya que el elemento mínimo siempre estará en la raíz. Además, Heap no necesita espacio adicional para los punteros izquierdo y derecho.

El algoritmo anterior es bueno, la complejidad del tiempo y el espacio se puede mejorar con una variación del algoritmo Quick Sort . Si no está familiarizado con Quicksor , no le eche un vistazo antes de leer esta solución.

El algoritmo usa ordenación rápida pero cambia la función de partición de 2 maneras.

1. Selecciona el elemento pivote como el elemento central en lugar del primer o último elemento.
2. Escanea la array de max(low, mid – k) a min(mid + k, high) en lugar de menor a mayor.

El elemento central se elige como pivote para dividir la array en casi 2 mitades para una complejidad de tiempo logarítmica.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
int sort(vector<int>& array, int l, int h, int k)
{
    int mid = l + (h - l) / 2; //Choose middle element as pivot
    int i = max(l, mid - k), j = i, end = min(mid + k, h); // Set appropriate range
    swap(array[mid], array[end]); //Swap middle and last element to avoid extra complications
    while (j < end) {
        if (array[j] < array[end]) {
            swap(array[i++], array[j]);
        }
        j = j + 1;
    }
    swap(array[end], array[i]);
    return i;
}
 
void ksorter(vector<int>& array, int l, int h, int k)
{
    if (l < h) {
        int q = sort(array, l, h, k);
        ksorter(array, l, q - 1, k);
        ksorter(array, q + 1, h, k);
    }
}
 
int main()
{
    vector<int> array(
        { 3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12 });
    int k = 3;
    cout << "Array before k sort\n";
    for (int& num : array)
        cout << num << ' ';
    cout << endl;
    ksorter(array, 0, array.size() - 1, k);
    cout << "Array after k sort\n";
    for (int& num : array)
        cout << num << ' ';
    return 0;
}

// Java program for above approach
import java.io.*;
import java.util.*;
  
class GFG
{
  public static int sort(ArrayList<Integer> arr,int l,int h,int k)
  {
    int mid = l + (h-l)/2; //choose middle element as pivot
    int i = Math.max(l,mid-k), j=i, end = Math.min(mid+k,h); //set appropriate ranges
    Collections.swap(arr,end,mid); //swap middle and last element to avoid extra complications
    while(j<end)
    {
        if(arr.get(j)<arr.get(end))
        {
            Collections.swap(arr,j,i++);
        }
        j=j+1;
    }
    Collections.swap(arr,end,i);
    return i;
  }
   
  public static void ksorter(ArrayList<Integer> arr, int l,int h,int k)
  {
    if(l<h)
    {
        int q = sort(arr,l,h,k);
        ksorter(arr,l,q-1,k);
        ksorter(arr,q+1,h,k);
    }
  }
  
  // Driver Code
  public static void main(String[] args)
  {
    ArrayList<Integer> arr = new ArrayList<>(List.of(3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12 )); 
    int k = 3;
    int N = arr.size();
     
    System.out.println("Array before k sort\n");
    System.out.println(arr);
    System.out.println("\n");
     
    ksorter(arr, 0, N - 1, k);
     
    System.out.println("Array after k sort\n");
    System.out.println(arr);
     
  }
}
//this code is contributed by aditya942003patil

Array before k sort
3 3 2 1 6 4 4 5 9 7 8 11 12 
Array after k sort
1 2 3 3 4 4 5 6 7 8 9 11 12 

Complejidad de Tiempo: O(KLogN) 
Espacio Auxiliar: O(LogN)

Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto o encuentra otras formas de resolver el mismo problema.