Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.

Сортування.

Обернені перестановки.

Інверсія.

Нехай а₁, а₂, ..., а_n - перестановка множини {1, 2,..., n}. Якщо i<j, a a_i>a_j, то (a_i, a_j) називають інверсією перестановки.

Наприклад, для перестановки

існують три інверсії: (3,1), (3,2), (4, 2).

Тільки одна перестановка не має інверсій - впорядкована позростанню.

Таблицею інверсій перестановкиа₁, а₂, ..., а_nназивають послідовність чиселb₁, b₂, ..., b_nде bj - кількість елементів, більших за jта розташованих лівіше j (кількість інверсій для j).

Маршал Холл (1956) довів наступне: "Таблиця інверсій однозначно визначає відповідну перестановку". Розглянемо приклад. Нехай задана перестановка:

j
перестановка
таблиця інверсій

Таблиця інверсій визначається дуже просто. В перестановці знаходимо 1 та підраховуємо, скільки чисел, більших за 1 стоїть попереду в цій перестановці. Це два елементи - 5 та 9. ставимо на перше місце 2. Для двійки таких чисел 3 - 5,9 та 8. Ставимо на друге місце 3.1 так до кінця.

А тепер на основі таблиці інверсій отримаємо задану перестановку.

j
таблиця інверсій

Всього елементів 9. Тому записуємо 9 для початку.

Для j=8 bj =1, то запишемо 9,8. Адже перед 8 стоїть одне більніе число.

Для j=7 bj=2, то запишемо 9,8,7.

Для j=6 bj=2, то запишемо 9,8,6,7.

Дляі j=5 bj=0, то запишемо 5,9,8,6,7.

Для j=4 bj=4, то запишемо 5,9,8,6,4,7.

Для j=3 bj=6, то запишемо 5,9,8,6,4,7,3.

Для j=2 bj=3, то запишемо 5,9,8,2,6,4,7,3.

Для j=1bj=2, то запишемо 5,9,1,8,2,6,4,7,3.

В результаті отримали задану перестановку.

Таким чином задачу, яка була сформульована в термінах перестановок, можна замінити аналогічною задачею в термінах інверсій. Так наприклад, запитання "Скільки існує перестановок множини {1,2, ...,n}?" можна відповісти "Кількість перестановок дорівнює кількості можливих таблиць інверсій". Кількість таблиць інверсій легко перелічити: b₁ ) можна вибрати n способами, b₂ можна вибрати n-1 способами, ..., b_n можна вибрати 1 способом. Отримуємо

n*(n-l)*(n-2)*...*2*l=n!

Таблиці інверсій обчислити легше, тому що b незалежні, а а повинні бути всі різними.

Якщо поміняти місцями два сусідніх елементи перестановки, то кількість інверсій збільшиться або зменшиться на одиницю

Перестановку можна записати у вигляді таблиці з двома рядками:

			…	n
а₁	а₂	а₃	…	а_n

Далі поміняємо місцями рядки та впорядкуємо стовпчики в порядку зростання по верхнім елементам:

а₁	а₂	а₃	…	а_n
			…	n

			…	n
а₁'	а₂'	а₃'	…	а_n'

Отримана перестановкаа₁', а₂',..., а_n' називається оберненою перестановкою.

Для перестановки 5 9 1 8 2 6 4 73 отримаємо обернену перестановку:


					■

Обернена перестановка -3 5 9 7 1 6 8 4 2.

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

Кожен алгоритм сортуванні можна розбити на три частини:

• порівняння, що визначає впорядкованість пари елементів;

• перестановку, яка змінює місцями пару елементів;

• власне алгоритм сортування, який виконує порівняння та перестановку елементів до тих пір, поки всі елементи множини не будуть впорядковані.

Алгоритми методами бульбашки, вибору та включення ми розглянули раніше при вивченні масивів. Звернемо свою увагу на інші методи.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Алгоритм 1.	\|	Метод Шелла.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.013 сек.