Будет ли это определяться как форма HeapSort? - PullRequest
Новая
       13

Будет ли это определяться как форма HeapSort?

1 голос
/ 31 января 2020

Так что я возился с реализациями сортировки и решил, что не помешает попробовать базовую c реализацию с использованием ArrayLists и простого двоичного поиска, например: 

public static ArrayList<Integer> binarySort(ArrayList<Integer> list) {
    ArrayList<Integer> sortedList = new ArrayList<>();
    for(Integer value : list) {
        int index = binarySearchPosition(sortedList, value);
        sortedList.add(index, value);
    }
    return sortedList;
}

public static int binarySearchPosition(ArrayList<Integer> list, Integer value) {
    int min = 0;
    int max = list.size();

    while(max - min > 1) {
        int mid = (int) Math.floor((max + min) / 2);
        if(list.get(mid) < value) {
            min = mid;
        } else {
            max = mid;
        }
    }

    if(max == 0) {
        return 0;
    }
    if(list.get(min) < value) {
        return max;
    } else {
        return min;
    }
}

Он ведет себя по существу такой же, как HeapSort, но на самом деле не создает кучу данных. Будет ли что-то подобное определяться как форма HeapSort или как-то еще?

1 Ответ

1 голос
/ 31 января 2020

Кроме того, исправьте меня, если я ошибаюсь, так как мои навыки анализа алгоритма немного ржавые, но я думаю, что эта реализация будет иметь O (log2 (n!)), Не так ли? log2 (a) + log2 (b) = log2 (ab), и эта реализация будет делать log2 (1) + log2 (2) + ... + log2 (n-1) + log2 (n) примерно

К счастью, вы не правы, это было бы примерно O (n ^ 2).

Видите ли, list.add(index, value) - это O (n) само по себе, и вы должны сделать это N раз. То, как вы находите индекс, это просто накладные расходы, и O (log2 (n)) будет скрыто O (n ^ 2). Вот почему (для отсортированных списков массивов) часто проще искать в списке, копируя элементы. Поиск по-прежнему равен 0 (n), копирование не увеличивает его, и вы делаете это для каждого из N элементов, которые нужно вставить.

Вы выполняете O (log2 (n)) N раз. Это было бы O (nlog2 (n)). Однако list.add(index, value) сама по себе является операцией O (n). Статистически, можно было бы ожидать, что он переместит 1/2 из N элементов, а нотация big-O отбросит 1 / 2.

Таким образом, в итоге ваша операция - это O (n ^ 2 * log2 (n)), который медленнее, чем O (n ^ 2).

Рассуждая без математики, он примерно разбивается на:

  1. N элементов, добавляемых по одному за раз O ( n).
  2. Перемещение 1/2 из N элементов O (n).
  3. Двоичный поиск для поиска индекса вставки O (log2 (n)).

Обратите внимание, что если вы знаете, что уже нажали O (n ^ 2), вы можете избежать дополнительных усилий по поиску индекса с помощью очень простого алгоритма: 

Create a new array one element bigger.
for each element in the original array {
  if the element is smaller than the added item, copy it at the same index.
  if the element is same / larger than the added item, copy in the added item, and copy the rest of the elements from index to index+1.
}

Как вы можете видеть, это один полный l oop через массив, который должен был бы повторяться N раз, или O (n ^ 2).

Ваша структура данных на самом деле не куча, а отсортированный список. Это очень хорошая оптимизация для поиска отсортированных списков с использованием бинарного поиска. Это просто не уменьшит необходимость проходить большую часть списка по типу вставки; потому что вы собираетесь завершить копирование 1/2 элементов (если массив достаточно велик для размещения новых элементов) или копирование всего списка (если размер массива соответствовал входным данным). Оба этих сценария ios означают, что этот подход к поддержке вставки будет O (n ^ 2) независимо от того, как вы найдете индекс вставки.

Теперь, если у вас был связанный список, вставка становится O (1). Тем не менее, поиск индекса становится переходом от узла root, который сам по себе равен O (n) (опять же в среднем будет проходить половина узлов).

Теперь кучи - это другое предмет; но вы знаете это, потому что они не создают отсортированные списки.

...