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

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

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 рази збільшилася кількість порівнянь, а число свопів залишилося незмінним. Подвійний вибір лише незначно збільшує швидкість алгоритму, а на деяких мовах навіть чомусь працює повільніше.

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

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

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

Бінго-сортування :: 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
Циклічне сортування цікава (і цінна з практичної точки зору) тим, що зміни серед елементів масиву відбуваються тоді і тільки тоді, коли елемент ставиться на своє кінцеве місце. Це може стати в нагоді, якщо перезапис в масиві — занадто дороге задоволення і для дбайливого ставлення до фізичної пам’яті потрібно звести до мінімуму кількість змін елементів масиву.

Працює це так. Перебираємо масив, назвемо 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

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

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

Подібні трюки, взагалі кажучи, призводять до алгоритмічної складності 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). Чи означає це, що всі сортування вибором приречені на середньо-квадратичну складність? Зовсім ні, якщо процес пошуку організувати принципово по-іншому. Наприклад розглянути набір даних як купу і виробляти пошук саме в купі. Однак тема купи — це навіть не на статтю, а цілу сагу, про купи поговоримо обов’язково, але в інший раз.