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

01.01.2020Heap, Массивы, Сортировка

Учитывая массив из 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