Ordenar una array casi ordenada usando STL

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. Puede suponerse que k < n.

Ejemplo:  

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

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

Enfoque simple: la solución básica es ordenar la array utilizando cualquier algoritmo de clasificación estándar. 

// 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 Log n) time.
int sortK(int arr[], int n, int k)
{
    // Sort the array using
    // inbuilt function
    sort(arr, arr + n);
}
 
// An 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\n";
    printArray(arr, n);
 
    return 0;
}

// A STL based Java program to
// sort a nearly sorted array.
import java.util.*;
public class GFG
{
 
  // Given an array of size n,
  // where every element
  // is k away from its target
  // position, sorts the
  // array in O(n Log n) time.
  static void sortK(int[] arr, int n, int k)
  {
 
    // Sort the array using
    // inbuilt function
    Arrays.sort(arr);
  }
 
  // An utility function to print
  // array elements
  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 k = 3;
    int[] arr = { 2, 6, 3, 12, 56, 8 };
    int n = arr.length;
    sortK(arr, n, k);
 
    System.out.println("Following is sorted array");
    printArray(arr, n);
  }
}
 
// This code is contributed by divyesh072019.

# A STL based Java program to
# sort a nearly sorted array.
 
# Given an array of size n,
# where every element
# is k away from its target
# position, sorts the
# array in O(n Log n) time.
def sortK(arr, n, k):
   
    # Sort the array using
    # inbuilt function
    arr.sort()
 
# An utility function to print
# array elements
def printArray(arr, size):
    for i in range(size):
        print(arr[i], end = " ")
    print()
 
# Driver code
k = 3
arr = [ 2, 6, 3, 12, 56, 8]
n = len(arr)
sortK(arr, n, k)
print("Following is sorted array")
printArray(arr, n)
 
# This code is contributed by avanitrachhadiya2155

// A STL based C# program to
// sort a nearly sorted array.
using System;
class GFG
{
     
    // Given an array of size n,
    // where every element
    // is k away from its target
    // position, sorts the
    // array in O(n Log n) time.
    static void sortK(int[] arr, int n, int k)
    {
       
        // Sort the array using
        // inbuilt function
        Array.Sort(arr);
    }
       
    // An utility function to print
    // array elements
    static void printArray(
        int[] arr, int size)
    {
        for (int i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
 
  // Driver code
  static void Main()
  {
    int k = 3;
    int[] arr = { 2, 6, 3, 12, 56, 8 };
    int n = arr.Length;
    sortK(arr, n, k);
   
    Console.WriteLine("Following is sorted array");
    printArray(arr, n);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// A STL based Javascript program to
// sort a nearly sorted array.
 
// Given an array of size n,
// where every element
// is k away from its target
// position, sorts the
// array in O(n Log n) time.
function sortK(arr,n,k)
{
    // Sort the array using
    // inbuilt function
    (arr).sort(function(a,b){return a-b;});
}
 
// An utility function to print
// array elements
function printArray(arr,size)
{
    for (let i = 0; i < size; i++)
      document.write(arr[i] + " ");
    document.write("<br>");
}
 
// Driver code
let k = 3;
let arr=[ 2, 6, 3, 12, 56, 8 ];
let n = arr.length;
sortK(arr, n, k);
document.write("Following is sorted array<br>");
printArray(arr, n);
 
 
// This code is contributed by ab2127
</script>

Following is sorted arrayn2 3 6 8 12 56

Análisis de Complejidad: 

• Complejidad temporal: O(n log n), donde n es el tamaño de la array. 
  El algoritmo de clasificación toma el tiempo log n. Dado que el tamaño de la array es n, todo el programa toma un tiempo O (n log n).
• Complejidad espacial: O(1). 
  Como no se requiere espacio adicional.

Solución Eficiente: Técnica de Ventana Deslizante. 
Enfoque: una mejor solución es usar una cola de prioridad (o una estructura de datos de montón). Use la técnica de la ventana deslizante para mantener los k elementos consecutivos de una ventana en un montón. Luego, elimine el elemento superior (el elemento más pequeño) y reemplace el primer elemento de la ventana con él. 
Como cada elemento estará a una distancia máxima de k, por lo tanto, será suficiente mantener k elementos consecutivos en una ventana mientras se reemplaza el i-ésimo elemento con el elemento más pequeño de i a (i + k) (se ordenan los primeros i-1 elementos).
Algoritmo: 

1. Cree una cola de prioridad pq ​​de los primeros (k+1) elementos.
2. Inicializar índice = 0 (para array de resultados).
3. Haga lo siguiente para los elementos de k+1 a n-1. 
   1. Extraiga un elemento de pq y colóquelo en el índice, incremente el índice.
   2. Empuje arr[i] a pq.
4. Si bien pq no está vacío, 
   extraiga un elemento de pq y colóquelo en el índice, incremente el índice.

Hemos discutido una implementación simple en Ordenar una array casi ordenada (o K ordenada) . En esta publicación, se realiza una implementación basada en STL. 

// 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(nLogk) time.
int sortK(int arr[], int n, int k)
{
    // Insert first k+1 items in a
    // priority queue (or min heap)
    // (A O(k) operation)
    priority_queue<int, vector<int>,
                   greater<int> >
        pq(arr, arr + k + 1);
 
    // i is index for remaining
    // elements in arr[] and index
    // is target index of for
    // current minimum element in
    // Min Heapm 'hp'.
    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 arrayn";
    printArray(arr, n);
 
    return 0;
}

Following is sorted arrayn2 3 6 8 12 56

Análisis de Complejidad: 

• Complejidad Temporal: O(n Log k). 
  Para cada elemento, se coloca en la cola de prioridad y la inserción y eliminación necesita un tiempo O (log k) ya que hay k elementos en la cola de prioridad.
• Espacio Auxiliar: O(k). 
  Para almacenar k elementos en la cola de prioridad, se requiere espacio O(k).