Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






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

Сортування.

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

Інверсія.

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

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

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

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

Таблицею інверсій перестановкиа1, а2, ..., аnназивають послідовність чиселb1, b2, ..., bnде 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}?" можна відповісти "Кількість перестановок дорівнює кількості можливих таблиць інверсій". Кількість таблиць інверсій легко перелічити: b1 ) можна вибрати n способами, b2 можна вибрати n-1 способами, ..., bn можна вибрати 1 способом. Отримуємо

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

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

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

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

 

n
а1 а2 а3 аn

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

 

а1 а2 а3 аn
n

 

n
а1' а2' а3' аn'

Отримана перестановкаа1', а2',..., аn' називається оберненою перестановкою.

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

 

 

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

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

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

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

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

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

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


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

  1. L2.T4. Транспортування рідких, твердих та газоподібних речовин.
  2. RLC-фільтр четвертого порядку
  3. X Впровадження Зростання Зрілість Спад Час
  4. Аналіз використання прибутку та резервів його зростання
  5. Аналіз паралельного інтерейсу з DSP-процесорами: запис даних в ЦАП, що під’єднаний до адресного простору пам’яті
  6. Аналіз паралельного інтерфейсу з DSP-процесорами: читання даних з АЦП, що під’єднаний до адресного простору пам’яті
  7. Аналіз статистичних даних про склад та плинність кадрів, які обіймали керівні
  8. Аналіз та інтерпретація одержаних даних
  9. Архіватори даних.
  10. Архітектура баз даних
  11. Аспекти організаційного порядку
  12. Аудит розрахунків за відшкодуванням завданих збитків




Переглядів: 1286

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

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

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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