Является ли алгоритм быстрой сортировки адаптивным или нет?

Предварительные условия: алгоритм быстрой сортировки

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

В этой статье мы увидим , является ли алгоритм быстрой сортировки адаптивным или нет .

Возьмем пример:

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).