время — Что означает перемещение и сравнение клавиш в c ++?

Question

время — Что означает перемещение и сравнение клавиш в c ++?

Следующие написаны в ppt о вставке сортировки в моем классе:

void insertionSort(DataType theArray[], int n) {
for (int unsorted = 1; unsorted < n; ++unsorted) {

DataType nextItem = theArray[unsorted];
int loc = unsorted;

for (;(loc > 0) && (theArray[loc-1] > nextItem); --loc)
theArray[loc] = theArray[loc-1];

theArray[loc] = nextItem;
}
}

—

Running time depends on not only the size of the array but also the contents of the array.
Best-case:       O(n)
Array is already sorted in ascending order.
Inner loop will not be executed.
>>>> The number of moves: 2*(n-1)        O(n)
>>>> The number of key comparisons: (n-1)    O(n)
Worst-case:      O(n2)
Array is in reverse order:
Inner loop is executed p-1 times, for p = 2,3, …, n
The number of moves: 2*(n-1)+(1+2+...+n-1)= 2*(n-1)+ n*(n-1)/2   O(n2)
The number of key comparisons: (1+2+...+n-1)= n*(n-1)/2          O(n2)
Average-case:    O(n2)
We have to look at all possible initial data organizations.
So, Insertion Sort is O(n2)

Что такое движение и сравнение ключей? Я не смог найти объяснения в Google.

0

c++complexity-theory time

Решение

Другие решения

Перемещение — это количество свопов, которое необходимо выполнить для сортировки данных, а ключи — это данные, которые конкурируют.

0

Источник

Accepted Answer

Позвольте мне сначала сформулировать алгоритм.

Предположим, в данный момент есть две части массива. индекс 0 индексировать loc - 1 сортируется по возрастанию и индексу loc в n - 1 не отсортировано
Начать с элемента в locНайдите правильное место в отсортированной части массива и вставьте его туда.

Итак, теперь есть две петли:

Первый внешний цикл начинается с loc = 1 в loc = n, в основном разбивает массив на отсортированные и несортированные части.
Второй внутренний цикл находит положение элемента в loc в отсортированной части массива ( 0 в loc - 1).

Для внутреннего цикла, чтобы найти правильное местоположение, вы должны сравнить элемент в loc со, в худшем случае, всеми элементами в отсортированной части массива. Это ключевое сравнение.

Чтобы вставить, вы должны создать пустую область в отсортированной части массива для элемента в loc, Это делается путем замены каждого элемента в отсортированной части на следующий элемент. Это движение.

0