Сортировка почти отсортированного (или K-отсортированного) массива | Набор 2 (метод пробела — сортировка ракушкой)

Опубликовано: 22 Сентября, 2022

Учитывая массив arr[] из N элементов, где каждый элемент находится не более чем на K от своей целевой позиции, задача состоит в том, чтобы разработать алгоритм, который сортирует за время O(N*log(K)) .

Примеры:

Input: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, K = 4
Output: 4 7 8 9 10 50 60 70
Explanation:
Follow the steps below to sort the array:

  1. Start with Gap = K(i.e. 4)
    • 10 9 8 7 4 70 60 50, swap the elements at indices 0 and 4. Then the array modifies to {4, 9, 8, 7, 10, 70, 60, 50}.
      4 9 8 7 10 70 60 50, Do not swap the elements at indices 1 and 5.
      4 9 8 7 10 70 60 50, Do not swap the elements at indices 2 and 6.
      4 9 8 7 10 70 60 50, Do not swap the elements at indices 3 and 7.
  2. Gap = ceiling of 4/2 = 2
    • 4 9 8 7 10 70 60 50, Do not swap the elements at indices 0 and 2.
      4 9 8 7 10 70 60 50, swap the elements at indices 1 and 3. Then the array modifies to {4, 7, 8, 9, 10, 70, 60, 50}.
      4 7 8 9 10 70 60 50, Do not swap the elements at indices 2 and 4.
      4 7 8 9 10 70 60 50, Do not swap the elements at indices 3 and 5.
      4 7 8 9 10 70 60 50, Do not swap the elements at indices 4 and 6.
      4 7 8 9 10 70 60 50, swap the elements at indices 5 and 7. Then the array modifies to {4, 7, 8, 9, 10, 70, 60, 50}.
      4 7 8 9 10 50 60 70
  3. Gap = ceiling of 2/2 = 1
    • 4 7 8 9 10 50 60 70, Do not swap the elements at indices 0 and 1.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 1 and 2.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 2 and 3.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 3 and 4.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 4 and 5.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 5 and 6.
      4 7 8 9 10 50 60 70, Do not swap the elements at indices 6 and 7.

Input: arr[] = {6, 5, 3, 2, 8, 10, 9}, K = 3  
Output: 2 3 5 6 8 9 10

Подход: Данная задача Сортировка почти отсортированного (или К отсортированного) массива уже решена. Здесь идея состоит в том, чтобы использовать сортировку оболочки для сортировки массива. Идея, используемая здесь, аналогична шагу слияния сортировки слиянием на месте. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем, Gap со значением K , чтобы отсортировать каждый Gap th . элемент каждого подсписка.
  • Повторяйте до тех пор, пока Gap не станет больше 0 , и выполните следующие шаги:
    • Перебрать диапазон [0, N-Gap], используя переменную i , и на каждой итерации, если arr[i] больше, чем arr[i+Gap], то поменять местами элементы массива.
    • Обновите Gap как Gap = ceil(Gap/2).
  • Наконец, после выполнения вышеуказанного шага выведите элементы массива arr[] .

Временная сложность: O (N * log K)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ