Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Цей алгоритм одержав широке поширення в багатьох прикладних програмах. Однак ефективність його використання істотно залежить від числа елементів сортуемого масиву, а також характеру розподілу цих даних. Отже:
— вибирається який–небудь елемент (x) (звичайно знаходиться в середині послідовності). Будемо переглядати масив ліворуч доти, поки не знайдемо елемент аi>x, потім будемо переглядати масив праворуч, поки не зустрінеться аj<x. Тепер поміняємо місцями ці два елементи і продовжимо наш процес перегляду й обміну, поки обидва перегляди не зустрінуться десь у середині масиву (значення i та j рівні). У результаті виявиться, що масив розбито на дві половини із ключами, меншими або рівними x, і більшими або рівними x, а сам елемент x буде знаходитися в необхідному місці;
— ітераційно повторюємо процес 1 для кожної з отриманих половин (у перший раз одержимо чотири піддіапазону вихідної послідовності) доти, поки значення індексів для кожного вкладеного діапазону чи будуть рівні, чи змінять відношення. У результаті ми одержимо упорядковану послідовність.
Дата публикования: 2015-04-07; Прочитано: 253 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!