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

Цей алгоритм одержав широке поширення в багатьох прикладних програмах. Однак ефективність його використання істотно залежить від числа елементів сортуемого масиву, а також характеру розподілу цих даних. Отже:

— вибирається який–небудь елемент (x) (звичайно знаходиться в середині послідовності). Будемо переглядати масив ліворуч доти, поки не знайдемо елемент аi>x, потім будемо переглядати масив праворуч, поки не зустрінеться аj<x. Тепер поміняємо місцями ці два елементи і продовжимо наш процес перегляду й обміну, поки обидва перегляди не зустрінуться десь у середині масиву (значення i та j рівні). У результаті виявиться, що масив розбито на дві половини із ключами, меншими або рівними x, і більшими або рівними x, а сам елемент x буде знаходитися в необхідному місці;

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