Частичная вставка сортировки

Question

Можно ли отсортировать только первые k элементы из массива, используя принципы сортировки вставками?

Поскольку алгоритм работает над массивом, он будет соответствующим образом сортироваться.

Поскольку необходимо проверить все элементы (чтобы определить, кто самый маленький), он в конечном итоге отсортируетвсе дело.

Пример:

Исходный массив: {5, 3, 8, 1, 6, 2, 8, 3, 10}

Ожидаемый результат для k = 3: {1, 2, 3, 5, 8, 6, 8, 3, 10} (отсортированы только первые k элементов, а остальные нет)

Answer 1

Да, это возможно.Это будет выполняться во время O(k n), где n - размер вашего массива.

Вам лучше использовать heapsort.Вместо этого он будет работать во времени O(n + k log(n)).Шаг кучи - O(n), затем каждый извлеченный элемент - O(log(n)).

Техническое примечание.Если вы умны, вы создадите кучу задом наперед до конца вашего массива.Поэтому, когда вы думаете о нем как о дереве, поместите n-2i, n-2i-1 th элементы ниже n-i th.Итак, возьмите ваш массив:

{5, 3, 8, 1, 6, 2, 8, 3, 10}

Это дерево примерно так:

 10
     3
         2
             3
             5
         6
     8
         1
         8

Когда мы кучи, мы получаем дерево:

 1
     2
         3
             3
             5
         6
     8
         10
         8

Что означаетскажем массив:

{5, 3, 8, 10, 6, 3, 8, 2, 1}

И теперь для извлечения каждого элемента требуется переместить последний элемент в конечное местоположение, а затем позволить большому элементу "упасть на дерево".Например:

# swap
{1*, 3, 8, 10, 6, 3, 8, 2, 5*}
# the 5 compares with 8, 2 and swaps with the 2:
{1, 3, 8, 10, 6, 3, 8?, 5*, 2*}
# the 5 compares with 3, 6 and swaps with the 3:
{1, 3, 8, 10, 6?, 5*, 8, 3*, 2}
# The 5 compares with the 3 and swaps, note that 1 is now outside of the tree:
{1, 5*, 8, 10, 6, 3*, 8, 3, 2}

Что в представлении массива:

{1}
2
    3
        3
             5
        6
    8
       10
        8

Повторите еще раз, и мы получим:

# Swap
{1, 2, 8, 10, 6, 3, 8, 3, 5}
# Fall
{1, 2, 8, 10, 6, 5, 8, 3, 3}

aka:

{1, 2}
3
    3
        5
        6
    8
       10
        8

И снова:

# swap
{1, 2, 3, 10, 6, 5, 8, 3, 8}
# fall
{1, 2, 3, 10, 6, 8, 8, 5, 3}

или

{1, 2, 3}
3
    5
        8
        6
    8
       10

И т. Д.

Answer 2

На всякий случай, если кому-то понадобится это в будущем, я предложил «чистое» решение, которое не было бы гибридом между исходной сортировкой вставки и некоторым другим алгоритмом сортировки.

void partialInsertionSort(int A[], int n, int k){
    int i, j, aux, start;
    int count = 0;
    for(i = 1; i < n; i++){
        aux = A[i];

        if (i > k-1){
            start = k - 1;
            //This next part is needed only to maintain
            //the original element order
            if(A[i] < A[k])
                A[i] = A[k];
        }
        else start = i - 1;

        for(j = start; j >= 0 && A[j] > aux; j--)
                A[j+1] = A[j];

        A[j+1] = aux;
    }
}

По сути, этот алгоритм сортирует первые k элементов.Затем k-й элемент действует как сводка: только когда остальные элементы массива меньше этого стержня, он вставляется в исправленную позицию между отсортированными k элементами, как в исходном алгоритме.

Наилучший сценарий: массив уже упорядочен

Учитывая, что сравнение является базовой операцией, тогда число сравнений равно 2n-k-1 → Θ (n)

В худшем случае: массив упорядочен в обратном порядке

Если сравнение является базовой операцией, то число сравнений будет (2kn - k² - 3k + 2n)/2 → Θ (kn)

(оба принимаютс учетом сравнения, сделанного для поддержания порядка в массиве)

Answer 3

Такая частичная сортировка возможна, в то время как результирующий метод выглядит как гибрид сортировки выбора - в части поиска наименьшего элемента в хвосте массива, а сортировка вставки - в части перемещающихся элементов (но без сравнений).Сортировка сохраняет порядок хвостовых элементов (хотя это не было задано явно)

1002 * Ideone 1006 *