Самописная функция sort
Мне нужно отсортировать массив не используя функцию sort. Как будет выглядеть самописный аналог этой функции?
Ответы (2 шт):
что значит аналог? алгоритмов сортировки море с разной средней, минимальной и максимальной производительностью
самое примитивное - O(n^2) сложность - цикл в цикле - сначала проходите по циклу и находите минимальное значение меняете его местами с 1 значением, потом проходите по циклу уже со второго значения до последнего, ищите минимального и заменяете его местами со 2 значением и т.д.
всего вам понадобится n * n / 2 этапов цикла
но это мягко говоря не самый оптимальный алгоритм сортировки :)
merge sort особенно легко написать на C++ с использованием функции std::merge. Вся реализация укладывается в 10 строк. Работает за оптимальное время NlogN.
quicksort также реализуется очень легко благодаря std::partition. Реализация займёт строк семь. Среднее время NlogN, худшее N^2.
Если совсем нельзя использовать высокоуровневые процедуры, то bubble sort займёт пять строк (std::swap подразумевается). Время N^2.