Сортування вибором

В чому ідея сортувань вибором?

  1. У несортованому підмасиві шукається локальний максимум (мінімум).
  2. Знайдений максимум (мінімум) міняється місцями з останнім (першим) елементом в підмасиви.
  3. Якщо у масиві залишилися несортовані підмасиви — дивись пункт 1.

Однак, зараз у тренді нелінійність, тому, не написавши ще всі публікації про сортування вставками, сьогодні почну паралельну гілку про сортування вибором. Те ж саме потім зроблю для інших алгоритмічних класів: сортувань злиттям, сортувань розподілом і т. п. Це в цілому дозволить писати публікації по одній темі, то з іншої. З таким тематичним чергуванням буде веселіше.

Сортування вибором :: Selection sort

Просто й невигадливо — проходимо по масиву в пошуках максимального елемента. Знайдений максимум міняємо місцями з останнім елементом. Несортована частина масиву зменшилася на один елемент (не включає останній елемент, куди ми переставили знайдений максимум). До цієї невідсортованої частини застосовуємо ті ж дії — знаходимо максимум і ставимо його на останнє місце в невідсортованих частині масиву. І так продовжуємо до тих пір, поки неотсортирована частина масиву не зменшиться до одного елемента.

def selection(data):
 for i, e in enumerate(data):
 mn = min(range(i, len(data)), key=data.__getitem__)
 data[i], data[mn] = data[mn], e
 return data

Сортування простим вибором представляє з себе грубий подвійний перебір. Чи можна її покращити? Розберемо кілька модифікацій.

Двостороннє сортування вибором :: Double selection sort

Схожа ідея використовується в шейкерному сортуванні, яке є варіантом бульбашкового сортування. Проходячи по невідсортованих частини масиву, ми крім максимуму також попутно знаходимо і мінімум. Мінімум ставимо на перше місце, максимум на останнє. Таким чином, несортовна частина при кожній ітерації зменшується відразу на два елемента.

На перший погляд здається, що це прискорює алгоритм в 2 рази — після кожного проходу несортований підмасив зменшується не з однієї, а відразу з двох сторін. Але при цьому в 2 рази збільшилася кількість порівнянь, а число свопів залишилося незмінним. Подвійний вибір лише незначно збільшує швидкість алгоритму, а на деяких мовах навіть чомусь працює повільніше.

Відмінність сортувань вибором від сортувань вставками
Може здатися, що сортування вибором і сортування вставками — це суть одне і те ж, загальний клас алгоритмів. Ну, або сортування вставками — різновид сортувань вибором. Або сортування вибором — приватний випадок сортувань вставками. І там і там ми по черзі з невідсортованих частині масиву витягаємо елементи і перенаправляємо їх в отсортированную область.

Читайте також  UHCI, або найперший USB

Головна відмінність: сортування вставками ми витягуємо з невідсортованих частин масиву будь який елемент і вставляємо його на своє місце у відсортованій частині. Сортування вибором ми цілеспрямовано шукаємо максимальний елемент (або мінімальний), яким доповнюємо отсортовану частина масиву. У вставках ми шукаємо куди вставити черговий елемент, а у виборі — ми заздалегідь вже знаємо в яке місце поставимо, але при цьому потрібно знайти елемент, цього місця відповідний.

Це робить обидва класи алгоритмів абсолютно відмінними один від одного по своїй суті і застосовуваним методам.

Бінго-сортування :: Bingo sort
Цікавою особливістю сортування вибором є незалежність швидкості від характеру відсортовані даних.

Наприклад, якщо майже відсортований масив, то, як відомо, сортування вставками його обробить набагато швидше (навіть швидше, ніж швидке сортування). А реверсно впорядкований масив для сортування вставками є виродженим випадком, вона буде його сортувати максимально довго.

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

Але в принципі, можна умудритись модифікувати алгоритм так, щоб при деяких наборах даних працювало швидше. Наприклад, бінго-сортування враховує, якщо масив складається з повторюваних елементів.

Тут фокус в тому, що в невпорядкованої частини запам’ятовується не тільки максимальний елемент, але і визначається максимум для наступної ітерації. Це дозволяє при повторюваних максимумах не шукати їх заново кожен раз, а ставити на своє місце відразу як тільки цей максимум в черговий раз зустріли в масиві.

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

# Бінго-сортування
def bingo(data):

 # Перший прохід. 

 max = len(data) - 1 
 nextValue = data[max] 
 for i in range(max - 1, -1, -1):
 if data[i] > nextValue:
 nextValue = data[i]

 while max and data[max] == nextValue:
 max -= 1

 # Наступні проходи.

 while max:
 value = nextValue
 nextValue = data[max]
 for i in range(max - 1, -1, -1):
 if data[i] == value:
 data[i], data[max] = data[max], data[i]
 max -= 1
 elif data[i] > nextValue:
 nextValue = data[i]
 while max and data[max] == nextValue:
 max -= 1

 return data

Циклічне сортування :: Cycle sort
Циклічне сортування цікава (і цінна з практичної точки зору) тим, що зміни серед елементів масиву відбуваються тоді і тільки тоді, коли елемент ставиться на своє кінцеве місце. Це може стати в нагоді, якщо перезапис в масиві — занадто дороге задоволення і для дбайливого ставлення до фізичної пам’яті потрібно звести до мінімуму кількість змін елементів масиву.

Читайте також  Стартап JITX використовує ШІ для автоматизації розробки складних друкованих плат

Працює це так. Перебираємо масив, назвемо X чергову комірку у цьому зовнішньому циклі. І дивимося на яке місце в масиві потрібно вставити черговий елемент з цієї комірки. На тому місці, куди потрібно вставити знаходиться якийсь інший елемент, відправляємо його в буфер обміну. Для цього елемента в буфері теж шукаємо його місце в масиві (і вставляємо на це місце, а в буфер відправляємо елемент, який опинився в цьому місці). І для нового числа в буфері виробляємо ті ж дії. До яких пір має тривати цей процес? Поки черговий елемент в буфері обміну виявиться тим елементом, який потрібно вставити саме в клітинку X (поточне місце в масиві в головному циклі алгоритму). Рано чи пізно цей момент відбудеться і тоді у зовнішньому циклі можна перейти до наступної клітинки і повторити для неї ту ж процедуру.

В інших сортуваннях вибором ми шукаємо максимум/мінімум, щоб поставити їх на останнє/перше місце. У cycle sort так виходить, що мінімум на перше місце в подмассиве як би знаходиться сам, в процесі того, як кілька інших елементів ставляться на свої законні місця десь в середині масиву.

І тут алгоритмічна складність так само залишається в межах O(n2). На практиці циклічне сортування працює навіть в кілька разів повільніше, ніж звичайна сортування вибором, так як доводиться більше бігати по масиву і частіше порівнювати. Це ціна за мінімально можливу кількість свопів.

# Циклічна сортування
def cycle data):

 # Проходимо по масиву в пошуку циклічних кругообігів
 for cycleStart in range(0, len(data) - 1):
 value = data[cycleStart]

 # Шукаємо, куди вставити елемент
 pos = cycleStart
 for i in range(cycleStart + 1, len(data)):
 if data[i] < value:
 pos += 1

 # Якщо елемент уже стоїть на місці, то відразу
 # переходимо до наступної ітерації циклу
 if pos == cycleStart:
continue

 # В іншому випадку, поміщаємо елемент на своє
 # місце або відразу після всіх його дублікатів
 while value == data[pos]:
 pos += 1
 data[pos], value = value, data[pos]

 # Циклічний круговорот продовжується до тих пір,
 # поки на поточній позиції не виявиться її елемент
 while pos != cycleStart:

 # Шукаємо, куди перемістити елемент
 pos = cycleStart
 for i in range(cycleStart + 1, len(data)):
 if data[i] < value:
 pos += 1

 # Поміщаємо елемент на своє місце
 # або відразу після його дублікатів
 while value == data[pos]:
 pos += 1
 data[pos], value = value, data[pos]

 return data

Млинна сортування
Алгоритм, який опанували всі рівні життя — від бактерій до Білла Гейтса.

Читайте також  UE4 | Інвентар для Multiplayer #3 | Структура взаємодії

У найпростішому варіанті ми несортованій частині масиву шукаємо максимальний елемент. Коли максимум знайдений — робимо два різких розвороти. Спочатку перевертаємо ланцюжок елементів так, щоб максимум опинився на протилежному кінці. Потім перевертаємо весь несортовнаний пвдмасив, в результаті чого максимум потрапляє на своє місце.

Подібні трюки, взагалі кажучи, призводять до алгоритмічної складності O(n3). Це дресировані інфузорії перекидаються одним махом (тому в їх виконанні складність O(n2)), а при програмуванні розворот частини масиву — це додатковий цикл.

Млинцеве сортування дуже цікаве з математичної точки зору (кращі уми роздумували над оцінкою мінімальної кількості переворотів, достатніх для сортування), є більш складні постановки завдання (з так званою підгорілою однією стороною). Тема млинців вкрай цікава, можливо, напишу більш грунтовну монографію з цих питань.

# Блинная сортування
def pancake(data):

 if len(data) > 1:

 for size in range(len(data), 1, -1):

 # Позиція максимуму в невідсортованих частини
 maxindex = max(range(size), key = data.__getitem__)

 if maxindex + 1 != size:

 # Якщо максимум не слова, то потрібно розгорнути
 if maxindex != 0:
 # Перевертаємо так, 
 # щоб максимум опинився зліва
 data[:maxindex+1] = reversed(data[:maxindex+1])

 # Перевертаємо неотсортированную частина масиву, 
 # максимум стає на своє місце
 data[:size] = reversed(data[:size])

 return data

Сортування вибором ефективне настільки, наскільки ефективний організований пошук мінімального/максимального елемента в невідсортованих частинах масиву. У всіх розібраних сьогодні алгоритмах пошук здійснюється у вигляді подвійного перебору. А в подвійного перебору, як не крути, алгоритмічна складність буде завжди краще, ніж O(n2). Чи означає це, що всі сортування вибором приречені на середньо-квадратичну складність? Зовсім ні, якщо процес пошуку організувати принципово по-іншому. Наприклад розглянути набір даних як купу і виробляти пошук саме в купі. Однак тема купи — це навіть не на статтю, а цілу сагу, про купи поговоримо обов’язково, але в інший раз.

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *