Сортування даних

Завдання обчислення порядкових статистик полягає в знаходженні к-го найменшого елемента в послідовності з n елементів. Це завдання іноді називають завданням знаходження к-ой порядкової статистики. При к = 1 задача зводиться до знаходження найменшого елемента послідовності, а при к = n найбільшого елемента і вирішується не більше ніж за О (n) кроків. Одне з очевидних рішень задачі обчислення порядкових s статистик полягає в наступному: впорядкувати вихідну послідовність в порядку не спадання елементів і взяти до-й елемент. При цьому, однак, необхідно враховувати вимоги реального завдання, в інтересах якої обчислюються порядкові статистики.

По-перше, може виявитися, що в упорядкованій послідовності ключі кількох елементів (к-й, (до + 1) -й.) ...] мають одне і те ж значення. Тоді необхідно враховувати, чи повинні такі елементи слідувати один за одним у тому ж порядку, як і у вихідній послідовності, або це необов'язково. У першому випадку впорядкування вихідної послідовності необхідно виконати одним з методів стійкою сортування, в другому випадку можна використовувати будь-який метод сортування.
По-друге. відшукується чи одна або кілька порядкових статистик. Залежно від цього може стати вигідним застосування того чи іншого алгоритму.
По-третє. на вибір алгоритму впливає число елементів n вихідної послідовності.

Нарешті, якщо вихідна послідовність повинна бути збережена без зміни, то для відшукання порядкових статистик доведеться створити копію вихідної послідовності або масив ключів з елементів вихідної послідовності. Використання масиву ключів може виявитися вигідним і в тому випадку, коли елементи вихідної послідовності мають складну структуру і їх перестановки в процесі обчислення порядкових структур вимагають значного часу. Якщо вимога стійкою сортування не обов'язково, то можна застосувати рекурсивну процедуру, засновану на швидкої сортування Хоара (Quicksort), яка забезпечує найшвидшу в середньому сортування.

Відмінність рекурсивної процедури знаходження к-й порядкової статистики від процедури швидкого сортування Хоара полягає в тому, що, по-перше, після розбиття на дві групи вибирається та група, в ко¬торой знаходиться до-й елемент, і, по-друге, в надалі обробляється тільки ця група, а не обидві групи, як це робиться в швидкої сортування Хоара.

Час, що витрачається на знаходження к-й порядкової статистики як по одному методу так і по іншому, залежить від вдалого вибору опорного елемента при розбитті на групи. Час буде мінімально, якщо при кожному проході групи містять приблизно однакову кількість елементів. Доведено, що в тому випадку, якщо кожен прохід здійснюється навіть на безлічі, що становить 9/10 попереднього, то час виконання буде порядку О (n), а в гіршому випадку - не більше О (n 2). Лінійний метод знаходження порядкових статистик, забезпечує в найгіршому випадку час виконання порядку О (n). Цей метод заснований на пошуку «хорошого» опорного елемента і застосовується для послідовностей з великим числом елементів.

Схожі статті