Рубрики

Вопрос сложности времени вставки сортировки

Сортировка

Вопрос: Сколько времени занимает сортировка вставкой для сортировки массива размера n в приведенной ниже форме?

arr [] = 2, 1, 4, 3, 6, 5,… .i, i-1,… ..n, n-1

Ответ: На первый взгляд кажется, что сортировка вставкой займет время O (n 2 ), но на самом деле это время O (n)

Как? Давайте внимательнее посмотрим на приведенный ниже код.

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   for (int i = 1; i = 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

Если мы тщательно проанализируем входные данные, то увидим, что каждый элемент находится всего в одной позиции от его позиции в отсортированном массиве. Внешний цикл for будет работать до 'n', а внутренний цикл while будет выполнять «постоянные» шаги: 1 обмен и 2 сравнения. Поскольку, хотя цикл занимает постоянное время и цикл выполняется для элемента 'n', общая сложность составляет O (n)

Альтернативный ответ: Другой способ посмотреть на это — время, затрачиваемое сортировкой вставок, пропорционально количеству инверсий в массиве . В приведенном выше примере типа число инверсий равно n / 2, поэтому общая сложность по времени равна O (n)

Эта статья предоставлена Уддалаком Бхадури . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вопрос сложности времени вставки сортировки

0.00 (0%) 0 votes