Вдосконалені алгоритми сортування

1. 3. Швидке сортування

1.1. вдосконалений бульбашковий

1.2. перестановки далеко розташованих елементів

1.2.1. приклад - масив, відсортований у зворотному порядку

1.2.1.1. n/2 кроків

1.3. обирають деякий елемент m

1.3.1. всі менші елементи - ліворуч від m

1.3.2. всі більші елементи - праворуч m

1.4. повторюють попередню процедуру для лівої і правої частин масиву

1.5. рекурсія

1.5.1. медіана

1.5.1.1. ймовірність =1/n

1.5.1.2. центральний елемент

1.6. приклад - в електронному підручнику

2. 4. Пірамідальне сортування

2.1. вдосконалення прямого вибору

2.1.1. ітеративний пошук найменшого

2.1.1.1. на перше місце

2.1.1.2. повторення для 2..n, 3..n, ...

2.1.1.2.1. n-1, n-2, n-3, ...

2.1.1.2.2. (n^2-n)/2

2.2. розбиваємо масив на пари

2.2.1. попарне порівняння

2.2.1.1. n/2 порівнянь

2.3. в кожній парі беремо найменші елементи і порівнюємо

2.3.1. n/4 порівняння

2.4. за n порівнянь

2.4.1. знайдемо найменший елемент

2.4.2. побудуємо дерево елементів

2.4.2.1. піраміда

2.4.2.2. елементи пронумеровані від 1 до R

2.4.2.3. x(i) <= x(i*2)

2.4.2.4. x(i) <= x(i*2+1)

2.4.3. забираємо верхній (найменший) елемент

2.4.3.1. міняємо його на найменший з нижніх елементів

2.4.4. після n повторень піраміда буде пустою

2.5. приклад - в електронному підручнику

3. 5. Типові завдання з теми

3.1. реалізація алгоритмів будь-якою мовою

3.2. сортування матриць

3.3. сортування текстових файлів

3.4. задача про два верстати

4. Повторення

4.1. Масиви

4.1.1. впорядкований набір однотипних елементів

4.1.1.1. базовий тип

4.1.1.2. кількість вимірів

4.1.1.3. кількість елементів

4.1.1.4. спосіб опису

4.1.2. операції

4.1.2.1. розбивка

4.1.2.2. злиття

4.1.2.3. перетворення

4.1.2.4. сортування

4.1.2.4.1. характеристики

4.1.2.5. пошук

4.1.3. ключ сортування

4.1.3.1. обчислюваний

4.1.3.1.1. F(x)

4.1.3.2. необчислюваний

4.2. Сортування

4.2.1. бульбашкове

4.2.1.1. ~n^2

4.2.1.2. порівняння сусідніх елементів

4.2.1.2.1. перестановка

4.2.1.3. вкладені цикли

4.2.2. прямого включення

4.2.2.1. масив розбивається на дві частини

4.2.2.1.1. відсортована

4.2.2.1.2. невідсортована

4.2.2.2. на кожному кроці беремо з невідсортованої один елемент

4.2.2.2.1. починаємо з i=2

4.2.2.2.2. переміщуємо у відсортовану

4.2.2.3. вкладені цикли

4.2.2.4. ~ln(n)

4.2.3. прямого вибору

4.2.3.1. найменший елемент міняється місцями з першим

4.2.3.1.1. повторюємо, доки не дійдемо до кінця

4.2.4. шейкерна

4.2.4.1. вдосконалення бульбашкового

4.2.4.2. крок вперед - крок назад

4.2.5. злиттям

4.2.5.1. є 2 масиви, відсортовані в порядку зростання

4.2.5.2. треба об'єднати їх, не порушивши порядку

4.2.5.3. порівнюємо перші, потім другі елементи і т.д.

4.3. Пошук елементів

4.3.1. критерії

4.3.1.1. пошук позиції

4.3.1.2. пошук елемента, який задовольняє певну умову

4.3.1.2.1. min

4.3.1.2.2. max

4.3.1.2.3. медіана

4.3.1.2.4. n-те найменше значення

4.3.2. простий перебір

4.3.2.1. ~n

4.3.3. пошук у відсортованому масиві

4.3.3.1. бінарний пошук

4.3.3.1.1. метод дихотомії

4.3.3.1.2. рекурсія

4.3.3.1.3. ітеративний процес

4.3.4. еврістичні методи

4.3.4.1. товари у супермаркеті

4.3.4.2. індекси

4.3.4.3. історія запитів користувачів

4.4. Першоджерело

5. 1. Особливості

5.1. швидкість ~ln(n)

5.1.1. спочатку швидко росте

5.1.2. потім стабілізується

5.1.3. Логарифм

5.2. для великих масивів

5.2.1. для малих - прості методи

5.2.1.1. пряма вставка

5.2.1.2. шейкерний

5.2.1.3. простого вибору

5.3. Основні вдосконалені методи сортування

5.3.1. Шелла

5.3.2. швидке сортування

5.3.3. пірамідальне

6. 2. Сортування Шелла

6.1. вдосконалена проста вставка

6.1.1. кожен елемент переміщується на половину відсортованого масива

6.2. переміщення на більші відстані

6.2.1. змінна довжина кроку

6.2.1.1. 4 - 2 - 1

6.2.1.1.1. на останньому кроці масив вже впорядковано

6.3. час виконання ~x^1.2

6.3.1. x^2 для простої вставки

6.4. приклад - в електронному підручнику