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