• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

При сортуванні масиву а[1], а[2], ..., a[n] методом простого вибору серед всіх елементів знаходиться елемент з якнайменшим значенням а[і], і а[1] і а[і] обмінюються значеннями. Потім цей процес повторюється для одержуваних підмасивів а[2], а[3], ..., а[n] ... a[j], a[j+1], ..., а[n] до тих пір, поки ми не дійдемо до підмасиву а[n], що містить до цього моменту найбільше значення. Робота алгоритму ілюструється прикладом в таблиці 5.

Для методу сортування простим вибором необхідна кількість порівнянь – n[n-1)/2. Порядок необхідної кількості посилань (включаючи ті, які потрібні для вибору мінімального елемента) у гіршому разі складає Θ (n²). Проте порядок середньої кількості пересилань є (n ln n), що у ряді випадків робить цей метод одним із найкращих.

Таблиця 5 – Приклад сортування простим вибором.

Функція сортування вибором виглядає так:

void sort_vyb()

{

Int i,j a[10],t;

for (i=0; i<10-1; i++

for (j=i+1;j<10;j++)

if(a[i]<a[j]);

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

6 Сортування поділом (Хоара)

Метод сортування поділом був запропонований Чарльзом Хоаром 1962 року. Цей метод є розвитком методу простого обміну і настільки ефективний, що його почали називати ≪методом швидкого сортування - Quicksort≫.

Основна ідея алгоритму полягає в тому, що випадковим чином вибирається деякий елемент масиву х, після чого масив є видимим зліва, поки не зустрінеться елемент а[і] такий, що а[і]>х, а потім масив є видимим справа, поки не зустрінеться елемент a[j] такий, що a[j]<x. Ці два елементи міняються місцями, і процес перегляду, порівняння і обміну продовжується, поки ми не дійдемо до елемента х. У результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть менші від х, і праву із значеннями ключів, більшими від х. Далі процес рекурсивно продовжується для лівої і правої частин масиву до тих пір, поки кожна частина не міститиме лише один елемент (рисунок 17). Зрозуміло, що, як завжди, рекурсію можна замінити ітераціями, якщо запам'ятовувати відповідні індекси масиву. Прослідкуємо цей процес на прикладі нашого стандартного масиву (таблиця 6).

Таблиця 6 – Приклад швидкого сортування.

Рисунок 17 – Блок-схема рекурсивного методу Хоара

Алгоритм недаремно називається швидким сортуванням, оскільки для нього оцінкою кількості порівнянь і обмінів є Θ (n log n). Насправді, в більшості утиліт, що виконують сортування масивів, використовується саме цей алгоритм.

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

1. Багатофазне сортування
2. Багатофазне сортування
3. Завдання за вибором однієї правильної відповіді
4. Контроль-сортування (дефектація).
5. Медичне сортування та медична евакуація при НС
6. МЕДИЧНЕ СОРТУВАННЯ.
7. Методи управління вибором інноваційних стратегій підприємства
8. На підприємствах ресторанного господарства з вільним вибором страв оперативне планування починається зі складання плану-меню на один день відповідно до товарообігу.
9. Порозрядне сортування для списків.
10. Слухання. Мікалоюс Константінас Чюрльоніс, сонати (за вибором).
11. Сортування
12. Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.

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