Классическая сортировка вставкой алгоритм с массиваРеализация вставки сортировки в C++ с использованием стека или очереди?
void insertion_sort (int arr[], int length){
int j, temp;
for (int i = 0; i < length; i++){
j = i;
while (j > 0 && arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
}
Так она должна осуществляться с помощью стека или очереди?
Если вы используете вектор, вы получаете представление о том, что вся память, с которой вы работаете, соприкасается, но теряет производительность, потому что вам нужно скопировать. Если вы используете связанный список любого типа, вы получаете потому, что вам не нужно копировать, но вы проигрываете, потому что ваша память разбросана по всему месту.
Таким образом, это будет зависеть от количества отсортированных элементов, кеша процессора и, возможно, всего множества других вещей.
Учитывая, что этот алгоритм сортировки известен как медленный для любых чисел N, правильное решение состоит в том, чтобы не беспокоиться о производительности вообще и просто использовать std :: sort.
Мне было бы любопытно, как вы думаете, что сделаете это. – gnasher729
Невозможно сортировать один стек. Можно сортировать одну очередь с чем-то вроде сортировки пузырьков, используя O (1) пространство для хранения одного элемента. С двумя стеками может быть реализовано нечто вроде пузырьковой сортировки. С двумя очередями или тремя стеками может использоваться сортировка слияния снизу вверх. В случае 3 стеков, многофазное слияние вверх по объему происходит быстрее, но сложнее. Поскольку при перемещении данных из стека в стоп-код происходит обратное, программа должна отслеживать, должна ли она выполняться по возрастанию или нисходящей последовательности, добавляя к усложнению. – rcgldr