Является ли алгоритм быстрой сортировки адаптивным или нет?
Предварительные условия: алгоритм быстрой сортировки
Адаптивность в алгоритме быстрой сортировки относится к решению о том, что если нам дан массив, который уже отсортирован, то операции должны быть выполнены или нет, т. е . если количество операций, выполняемых над отсортированным массивом, не равно количеству операций, выполняемых над несортированный массив, то алгоритм известен как адаптивный.
В этой статье мы увидим , является ли алгоритм быстрой сортировки адаптивным или нет .
Возьмем пример:
int arr[] = {1,2,3,4,5};
Итак, в приведенном выше примере мы видим, что массив отсортирован. Но когда массив не отсортирован , тогда должна быть выполнена операция, и, как мы знаем, временная сложность быстрой сортировки в худшем случае составляет O (N ^ 2) . Итак, если массив несортирован, то временная сложность массива для сортировки составляет O(N^2) ,
Причина : потому что для сортировки массива нужно сделать N-1 проходов и Ni-1 обменов.
Алгоритм быстрой сортировки не является адаптивным ,
Можем ли мы сделать алгоритм QuickSort адаптивным?
Да, мы можем сделать его адаптивным очень легко.
Например:
В приведенном ниже коде мы создали пустую функцию AdaptiveBubbleSort , которая принимает аргументы «arr[], n» , то есть массив, и его размер равен n .
Мы создали переменную isSorted Integer, которая Initialize с 0 , если она отсортирована IsSorted = 1 , то внутренний цикл for не будет выполняться, а если нет, то выполнится внутренний цикл for, и далее, если мы найдем элемент j+ На 1 меньше, чем текущий элемент j , затем поменяйте их местами после того, как они будут отсортированы.
Наконец, вызовите переменную isSorted и верните ее.
Следовательно, если массив уже отсортирован, то каждый элемент проходится почти один раз. Таким образом, временная сложность становится O(N) , а в противном случае требуется O(N*log(N)).
Во всех случаях вспомогательное пространство будет O (1).