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

Сучасні процедури сортування використовують одну з модифікацій алгоритму швидкого сортування, до викладу якого ми переходимо

Розглянемо масив х:

25         37         12        33         48         57        92         86

У ньому число 48 характеризується тим, що, по-перше, всі розташовані лівіше нього числа менше 48 і, по-друге, числа, розташовані правіше нього, більше 48 Назвемо таке число роздільником масивуНеважко зрозуміти, що тепер ми можемо окремо вирішувати задачу сортування для чисел до роздільника і для чисел після нього Крім того, сам роздільник знаходиться в потрібній позиції, тобто в подальшій сортуванні він вже не розглядається

Розглянемо тепер масив, в якому немає роздільник:

37        25         57        48         12        92         86         33

Щоб скористатися тільки що наведеної ідеєю зменшення розмірності задачі сортування, нам треба навчитися виконувати такі перестановки в масиві, після яких один з його елементів стане роздільником Виберемо для майбутнього роздільник перший елемент масиву, тобто число 37 Роздільник опиниться в потрібній позиції, якщо розмістити числа 25, 12 і 33 зліва від 37 Виконаємо це так: будемо переглядати послідовно елементи масиву починаючи з його першої позиції до тих пір, поки не зустрінемо число, більше роздільник Привласнимо цієї позиції імя L1 Далі переглянемо елементи масиву починаючи з останньої позиції, зупиняючись при виявленні числа, меншого 37 Дамо такої позиції імя R1 У нашому випадку після виконання цих двох переглядів виникне наступна ситуація:

Неважко вгадати наступний крок алгоритму числа 57 і 33 повинні бути переставлені місцями, тоді вийде масив

Продовжимо тепер пошук елемента, більшого 37, переміщаючись вправо, починаючи з позиції L1, і елемента, меншого 37, переміщаючись вліво, починаючи з позиції R1 Такий пошук дасть наступний результат:

Виконаємо і перестановку:

37

25

33

12

48

92

86

57

L1

R1

Ще одна пара переміщень не змінить картини, але дасть нам підставу для пре

кращения лівих і правих переміщень уздовж масиву (критерій припинення переміщень істинність виразу L1> = R1) і перестановки роздільник (числа 37) у його остаточну позицію Після виконання переміщень, що передують перестановці роздільник, імена R1 і L1 розташуються так:

Сам же роздільник повинен бути розміщений у позиції R1, що виконується в результаті обміну елементів х[1] і x [R1], тобто чисел 12 і 37 Наведемо й результат:

12         25         33         37        48        92         86         57

Отже, масив розбитий на дві частини (до і після роздільник), які можна сортувати окремо, застосовуючи до кожної з частин щойно наведену схему Завершимо ж сортування, коли довжина кожної з отриманих в результаті розбиття частин буде дорівнює одиниці

Зауваження    Вибір в якості майбутнього роздільник першого елемента масиву (або подальшого фрагмента) необовязковий і в ряді випадків незадовільний Так, у разі майже відсортованого масиву майбутній роздільник краще вибирати ближче до середини розглянутого фрагмента

Обчислювальна складність швидкого сортування оцінюється як0(nlog2n)  Так, якщо сортується масив з 1024 елементів, то бульбашкова сортування буде в середньому виконуватися в

рази повільніше

Джерело: Бартеньев О В 1С: Підприємство: програмування для всіх Базові обєкти та розрахунки на одній дискеті М: Діалог-МІФІ, 2005 464 с

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*