Рубрики

Сортировать почти отсортированный (или отсортированный по K) массив

Учитывая массив из n элементов, где каждый элемент находится на расстоянии не более k от своей целевой позиции, разработайте алгоритм, который сортирует по времени O (n log k). Например, давайте рассмотрим k = 2, элемент с индексом 7 в отсортированном массиве, может быть с индексами 5, 6, 7, 8, 9 в данном массиве.

Примеры:

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}

Мы можем использовать сортировку вставками для эффективной сортировки элементов. Ниже приведен код C для стандартной сортировки вставок.

С

/ * Функция для сортировки массива с использованием вставки sort * /

void insertionSort(int A[], int size)

{

   int i, key, j;

   for (i = 1; i < size; i++)

   {

       key = A[i];

       j = i-1;

  

       / * Переместить элементы A [0..i-1], которые больше ключа, в один

          положение впереди своей текущей позиции.

          Этот цикл будет выполняться не более k раз * /

       while (j >= 0 && A[j] > key)

       {

           A[j+1] = A[j];

           j = j-1;

       }

       A[j+1] = key;

   }

}

Джава

/ * Функция для сортировки массива с использованием вставки sort * /

static void insertionSort(int A[], int size) 

int i, key, j; 

for (i = 1; i < size; i++) 

    key = A[i]; 

    j = i-1

  

    / * Переместить элементы A [0..i-1], которые больше ключа, в один

        положение впереди своей текущей позиции.

        Этот цикл будет выполняться не более k раз * /

    while (j >= 0 && A[j] > key) 

    

        A[j+1] = A[j]; 

        j = j-1

    

    A[j+1] = key; 


python3

# Функция для сортировки массива с помощью
# вставка сортировки

def insertionSort(A, size):

i, key, j = 0, 0, 0

for i in range(size):

    key = A[i] 

    j = i-1

  

    # Переместить элементы A [0..i-1], которые

    # больше ключа, на одну позицию

    # опередил свою текущую позицию.

    # Этот цикл будет выполняться не более k раз

    while j >= 0 and A[j] > key:

        A[j + 1] = A[j] 

        j = j - 1

    A[j + 1] = key

C #

/ * C # Функция для сортировки массива с использованием вставки сортировки * /

static void insertionSort(int A[], int size) 

    int i, key, j; 

        for (i = 1; i < size; i++) 

        

            key = A[i]; 

            j = i-1; 

  

    / * Переместить элементы A [0..i-1], которые больше ключа, в один

        положение впереди своей текущей позиции.

        Этот цикл будет выполняться не более k раз * /

    while (j >= 0 && A[j] > key) 

    

        A[j+1] = A[j]; 

        j = j-1; 

    

    A[j+1] = key; 



Внутренний цикл будет выполняться не более k раз. Чтобы переместить каждый элемент на правильное место, нужно переместить не более k элементов. Таким образом, общая сложность будет O (нк)

Мы можем сортировать такие массивы более эффективно с помощью структуры данных Heap . Ниже приводится подробный процесс, который использует кучу.
1) Создайте Min Heap размера k + 1 с первыми k + 1 элементами. Это займет O (K) время (см. Этот GFact )
2) Один за другим удалите элемент min из кучи, поместите его в массив результатов и добавьте новый элемент в кучу из оставшихся элементов.

Удаление элемента и добавление нового элемента в min heap займет время Logk. Таким образом, общая сложность будет O (k) + O ((nk) * logK)

C ++

// Программа на С ++, основанная на STL, для сортировки почти отсортированного массива.
#include <bits/stdc++.h>

using namespace std;

   
// Задан массив размером n, где каждый элемент
// находится на расстоянии от своей целевой позиции, сортирует
// массив за O (nLogk) время.

int sortK(int arr[], int n, int k)

{

    // Вставляем первые k + 1 элементов в приоритетную очередь (или мин кучу)

    // (AO (k) операция). Предположим, k <n.

    priority_queue<int, vector<int>, greater<int> > pq(arr, arr + k + 1);

   

    // я индекс для оставшихся элементов в arr [] и индекс

    // целевой индекс для текущего минимального элемента в

    // 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();

    }

}

   
// Утилита для печати элементов массива

void printArray(int arr[], int size)

{

    for (int i = 0; i < size; i++)

        cout << arr[i] << " ";

    cout << endl;

}

   
// Программа драйвера для проверки вышеуказанных функций

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;

}

Джава

// Java-программа для сортировки почти отсортированного массива

import java.util.Iterator;

import java.util.PriorityQueue;

  

class GFG 

{

    private static void kSort(int[] arr, int n, int k) 

    {

  

        // мин куча

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

  

        // добавляем первые k + 1 элементов в минимальную кучу

        for(int i = 0; i < k + 1; 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();

        }

  

    }

  

    // Утилита для печати массива

    private static void printArray(int[] arr, int n) 

    {

        for(int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

  

    // Код драйвера

    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);

    }

}

  
// Этот код предоставлен
// Manpreet Singh (manpreetsngh294)

python3

# Программа Python3 для сортировки
# почти отсортированный массив.

  

from heapq import heappop, heappush, heapify

  

  
# Утилита для печати
# элементы массива

def print_array(arr: list):

    for elem in arr:

        print(elem, end = ' ')

  
# Учитывая массив размером n, где каждый
# элемент находится на расстоянии k от цели
# position, сортирует массив по времени O (nLogk).

def sort_k(arr: list, n: int, k: int):

    «»»

    : param arr: входной массив

    : param n: длина массива

    : параметр k: максимальное расстояние, которое каждый

     Элемент удален от своей целевой позиции.

    : return: нет

    «»»

    # Список первых k + 1 предметов

    heap = arr[:k + 1]

  

    # используя heapify для преобразования списка

    # в кучу (или мин куча)

    heapify(heap)

  

    # "rem_elmnts_index" - индекс для оставшихся

    # элементы в arr и "target_index" это

    # целевой индекс для текущего минимального элемента

    # в Min 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

  
Код водителя

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)

  
# Этот код предоставлен
# Veerat Beri (Виратбери)


Выход:

Following is sorted array
2 3 6 8 12 56

Метод на основе Min Heap занимает время O (nLogk) и использует O (k) вспомогательное пространство.

Мы также можем использовать сбалансированное бинарное дерево поиска вместо кучи для хранения элементов K + 1. Операции вставки и удаления в Balanced BST также занимают время O (Logk). Таким образом, метод на основе сбалансированного BST также займет время O (nLogk), но метод на основе Heap кажется более эффективным, так как минимальный элемент всегда будет в корне. Кроме того, Heap не требует дополнительного места для левого и правого указателей.

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Сортировать почти отсортированный (или отсортированный по K) массив

0.00 (0%) 0 votes