Методи внутрішнього сортування
Основні поняття і методи сортування
Сортування - це процес розстановки елементів «в деякому порядку». Елементи розміщуються так, щоб, по-перше, обчислення потребують певного порядку розташування даних, могли виконуватися ефективно, по-друге, результати мали осмислений вигляд, по-третє, подальші процеси б придатні вихідні дані.
Записи, поля і ключі. Одиниця даних, типово оброблювана інформаційними системами, називається записом. Запис - це сукупність елементів інформації про якусь подію або структурі. Кожен елемент інформації в записі, такий як номер службовця, ціна одиниці товару або валовий обсяг, називається полем запису. Сукупність полів ідентифікує і описує те, що представлено в записі. Із записів складаються файли чи набори даних. Сортування є процесом перестановки записів або їх індексів, при якому їх взаємне розташування у файлі приводитися в порядок, який визначається деяким відомим ключем. Ключем називається поле, що містить величину, яка використовується в правилах упорядкування файлу.
У припущенні, що результатом сортування є фізична упорядкування, сортування двох записів у своїй простій формі складається з порівняння їх ключових полів і визначень, яке з них «менше». Після цього запису переставляються так, що запис з «меншим» ключем ставитися перед записом з «великим» ключем.
Визначити, який ключ «менше», можна, використовуючи будь-яке правило. Очевидними правилами є: алфавітне упорядкування, числове і буквено-цифрове. (В останньому правилі ключі можуть містити суміш букв і цифр; угоди, прийняті в системі, визначають впорядкування букв і цифр.)
Ключем запису може бути одне поле або комбінація полів, розподілених по запису. Якщо ключ складається з кількох несоприкасающихся полів, то він називається складеним ключем.
Інколи бажано впорядкування всередині упорядкування. Наприклад, файл може бути впорядкований за номером місця роботи, а всередині цього впорядкування - за номером службовця. Поле, що містить номер місця роботи, називається старшим ключем, а поле, що містить номер службовця, - молодшим ключем. Так модно визначити кілька рівнів ключів, і всі рівні, відмінні від першого, називаються молодшими ключами. Старший і молодший ключі можна розглядати як один складений ключ в записі.
В інформаційній системі іноді зручно, щоб файли упорядковувалися не єдиним способом. Різні сортування в якості ключа можуть використовувати різні поля.
Запис може складатися тільки з поля ключа. В обробці наукових програм цей процес не є чимось винятковим. У даній роботі при розгляді методів сортування передбачатиметься, що записи складаються з одного поля. Це зроблено для того, щоб спростити початкове уявлення про методи сортування за рахунок усунення побічних проблем, що виникають під час переміщення даних. Оскільки ці методи однаково добре застосовні до записів, що містить як ключові, так і неключові поля, то це припущення не обмежує спільності.
Традиційно методи сортування ділять на внутрішні і зовнішні. Внутрішні методи - це такі методи, які можуть застосовуватися з прийнятною продуктивністю тільки до тих списками даних, які цілком вкладаються в основний (оперативної) пам'яті процесора. Зовнішні методи - це такі методи, які прийнятні для файлів даних, які занадто великі, щоб поміститься в основній пам'яті, і тому повинні протягом процесу сортування розташовуватися на пристроях зовнішньої пам'яті (стрічках, дисках, барабанах). Слово список часто позначає набір записів, розташованих в основній пам'яті.
Лінійний вибір з обміном: використання обмінів
Як приклад обміну в процесі сортування розглянемо тут мінімальну по пам'яті версію лінійного вибору. Обміном називається перестановка позицій двох записів в списку в залежності від результату перевірки їх відносної величини. Якщо в списку зустрічається запис з ключем, меншим, ніж у попередньої, то ці записи міняються місцями. Продуктивність методів обміну залежить від складності визначення послідовності порівнянь та обмінів. Часто кількість обмінів скорочують, відкладаючи обмін до кінця кожного перегляду. Це прийом, зокрема, використовується у методі, який буде описаний нижче.
Лінійний вибір з обміном. На початку першого перегляду передбачається, що перший елемент списку має найменший ключ. Цей ключ разом з адресою пересилається в робочу пам'ять, де порівнюється з усіма лінійними наступниками до тих пір, поки не зустрінеться менший ключ. Менший ключ і його адресу стають вмістом робочої області пам'яті.
Порівняння продовжуються при новому вмісті робочої пам'яті. Пересилання виконується завжди, коли в списку зустрічається ключ, який менше ключа в робочій пам'яті. Таким чином, в робочій пам'яті завжди розташований найменший з вже переглянутих ключів. Перегляд закінчується після досягнення кінця списку. До цього моменту процес ідентичний простому лінійному вибору. Сортування обміном відрізняється наступним кроком.
По закінченні першого перегляду запис, ключ якої розташований в робочій пам'яті, переставляється з записом з вершини списку. Тепер найменша величина в списку займає першу позицію. Другий перегляд ідентичний першому з тією лише різницею, що другим за величиною вважається другий ключ, так як першим стоїть найменший елемент. Перша позиція виключається з процесу. Після закінчення другого перегляду другий запис з найменшим ключем поміщається в другу позицію списку. Третій перегляд починається порівнянням ключа з третьої позиції і т.д. Ця процедура закінчується, коли своє місце займає (N - 1) - я запис.
алг Sort (арг цілий N, вещ таб A [1: N])
поч цілий i, j, k, Maxi
НЦ для i від N до 2 крок -1
Maxi: = i;
НЦ для j від 1 до i - 1
Якщо A [j]> A [Maxi]
то Maxi: = j;
всі
Якщо Maxi <> i
то k: = A [i];
A [i]: = A [Maxi];
A [Maxi]: = k;
всі
КЦ
кон
Оцінимо кількість порівнянь. При першому перегляді їх N - 1, при другому - N - 2, при останньому - 1. Загальна кількість C = N -1 + N - 2 + ... + 1 = C = N × (N - 1) / 2, тобто має порядок O (N 2).
Лінійний вибір з підрахунком
Метод сортування з підрахунком описується в літературі як процедура впорядкування внутрішнього списку чисел. Фактично, це не метод сортування, а технічний прийом, який можна використовувати в різних методах для скорочення кількості обмінів або повного їх усунення. Він є формою індексування, в якій лічильник відносної позиції кожного елемента коригується протягом процесу порівняння. Нижче буде описано цей технічний прийом стосовно до лінійного вибору.
Підрахунок як технічний прийом. Пам'ять, яка використовується лінійним вибором з підрахунком, буде включати область виводу (так само як і при лінійному виборі) для зберігання остаточно упорядкованого списку. Розмір області виведення відповідає тим же міркувань, що і при лінійному виборі. Додатково повинна бути забезпечена пам'ять під лічильник для кожного елемента списку. У результаті дій над значеннями цих лічильників утворюється безліч індексів позицій для елементів в упорядкованому списку. При кожному перегляді ключ порівнюється зі своїми лінійними наступниками. Кожного разу, коли знаходиться більший ключ, його лічильник збільшується на одиницю. Якщо знайдений ключ менше або дорівнює, то збільшується лічильник відповідний більшого з порівнюваних ключів. Отже, в будь-який момент часу лічильник елемента вказує кількість ключів, про які відомо, що вони менше ключа, що розглядається.
При першому перегляді перший ключ у списку порівнюється з усіма іншими ключами. У його лічильнику підраховується кількість менших ключів. У лічильниках великих ключів будуть 1. При другому перегляді перший ключ не розглядається. Другий ключ порівнюється з ключами всіх наступників. Підрахунки фіксуються. Цей процес триває N - 1 раз. На цьому етапі відомо відносна позиція кожного елемента. Помістивши ключі у вихідний список у відповідності зі значеннями їх лічильників, отримуємо упорядкований список.
алг Sort (арг цілий N, цілий таб A [1: N], рез цілий таб B [1: N]);
поч цілий i, j, цілий таб Count [1: N]
НЦ для i від N до 2 крок -1
НЦ для j від i - 1 до 1 крок -1
Якщо A [i] <A [j]
то Count [j]: = Count [j] + 1
інакше Count [i]: = Count [j] +1
всі
КЦ
КЦ
НЦ для i від 1 до N
B [Count [i] + 1]: = A [i]
КЦ
кон
Число порівнянь дорівнює N 2 / 2. Виконується (N-1) переглядів з N / 2 порівняннями в середньому на кожному перегляді. Значення лічильників змінюється стільки разів, скільки разів виконується порівняння.
Сортування обміном
Сортування обміном - це загальний термін, використовуваний для опису сімейства мінімальних по пам'яті методів сортування, які міняють місцями елементи списку, якщо попередній елемент більше наступного. Перегляд файлу може протікати зверху вниз або знизу вгору або змінюватися від перегляду до перегляду.
Існує ряд певних варіантів, які різняться послідовностями порівнянь елементів списку. У всіх елементарних методах обміну елемент порівнюється зі своїм найближчим сусідом, а можливими переміщеннями є переміщення елемента з великим ключем на одну позицію вниз і переміщення елемента з меншим ключем на одну позицію вгору. Парний обмін, стандартний обмін і просіювання є трьома простими формами сортування обміном.
Метод парного обміну (також званий «непарній-парна перестановка») складається з різного числа «непарних» і «парних» переглядів. При непарних переглядах кожен елемент з непарної позиції порівнюється зі своїм сусідом з парної позиції і більший з них займає велику позицію. Спадний перегляд списку продовжується до тих пір, поки останній непарний елемент (N - 1) у списку не порівнюється з останнім парних елементом N. Якщо в списку непарне число елементів, то останній елемент не буде брати участь в порівнянні. Протягом кожного перегляду ведеться підрахунок обмінів.
При парних переглядах парні позиції порівнюються з сусідніми непарними. Обміни виконуються тоді, коли треба, щоб більший з пари зайняв непарну позицію. Таким чином, ключі з великими значеннями переміщуються на дно списку. При цьому повинно бути стільки переглядів, скільки необхідно для того щоб перемістити в позицію число, найбільш віддалене від своєї кінцевої позиції. Потім виконується заключний перегляд, необхідний для того, щоб пізнати впорядкованість. Протягом цього перегляду лічильник обмінів дорівнює 0. Даний метод вимагає, принаймні, двох переглядів - одного непарного і одного парного.
Метод стандартного обміну (також званий «методом бульбашки») переміщує один елемент списку у відповідну позицію при кожному перегляді. Таким чином, при першому перегляді запис з найбільшим ключем поміщається в останню позицію, при другому перегляді запис із наступним за величиною ключем переміщається в передостанню позицію і т.д. Метод може бути перетворений так, що буде розміщувати елементи за спаданням.
При першому перегляді перший елемент списку порівнюється зі своїм безпосереднім наступником, і, якщо цей наступник менше, вони міняються місцями. Тепер більший елемент, розташований в другій позиції, порівнюється з елементом з третьої позиції. Обмін відбувається, якщо необхідно більший з них розмістити в третій позиції. Потім позиція 3 порівнюється з позицією 4, позиція 4 з позицією 5 і т.д. коли позиція N - 1 порівнюється з позицією N, перегляд закінчується.
Якщо в списку елемент k - 1 розташований раніше ніж k, то при кожному порівнянні (k - 1): k більший елемент потрапляє в позицію k. Елемент, переміщуваний вниз, вважається в даний момент найбільшим у списку. Коли при порівнянні виявляється, що k-й елемент більше, обмін не відбувається. Отже, кожен раз порівнюються елемент, який вважається найбільшим (k - 1), і його безпосередній наступник k.
Другий перегляд ідентичний першому з тією лише різницею, що вже встановлена позиція виключається з послідовності. Кожен наступний перегляд виключає чергову встановлену позицію, скорочуючи список.
Підрахунок обмінів ведеться для кожного перегляду. Перегляд, в результаті якого кількість обмінів не збільшилася, закінчує сортування.
алг Sort (арг цілий N, цілий таб A [1: N])
поч цілий k, i, w
НЦ для k від N до N - 1
НЦ для i від 1 до N - k
якщо A [i]> A [i + 1]
то w: = A [i]
A [i]: = A [i + 1]
A [i + 1]: = w
всі
КЦ
КЦ
кон
При сортуванні «методом бульбашки» виконується N - 1 перегляд, причому на i - му перегляді проводиться N - i порівнянь. Загальне колічесво порівнянь C = N × (N - 1) / 2, тобто має порядок O (N 2).
Метод просіювання (також званий «лінійної вставкою з обміном» чи «човникової сортуванням») є найкращим з цих методів. Він відрізняється від інших методів обміну тим, що не зберігає фіксованого послідовності порівнянь. Крім цього, зникає поділ на окремі перегляди як наслідок схеми послідовностей порівнянь. Метод просіювання працює точно так само, як стандартний обмін до тих пір, поки не треба виконувати перестановку. Порівнювана величина з меншим ключем піднімається наскільки це можливо вгору за списком. Вона порівнюється «у зворотному порядку» з усіма її лінійними попередниками у напрямку до вершини списку. Якщо її ключ менше, ніж у попередника, то виконується обмін і починається чергове порівняння. Коли елемент, пересувається угору, зустрічається з меншим ключем, цей процес припиняється і спадні порівняння поновлюються з тієї позиції, з якої виконувався перший обмін.
Будемо називати спадний порівняння первинним, а висхідний вторинним. Будь-яке первинне порівняння може збільшити число вторинних порівнянь. Якщо первинне порівняння охоплює позиції 6 і 7, то ланцюжок вторинних порівнянь може мати саме більший 5 порівнянь. Цей максимум досягається, якщо вихідний ключ з позиції 7 менше всіх ключів у списку, розташованих вище цієї позиції. Фактична довжина послідовності вторинних порівнянь залежить від величини рухається вгору елемента щодо величини кожного елемента з попередньої впорядкованої частині списку.
Сортування закінчується, коли первинне порівняння охопить (N + 1) - й елемент.
Сортування вставками
Сортування вставками є загальна назва групи методів сортування, заснованих на послідовній вставці «нових» елементів у збільшується впорядковуємо список. Серед них є три суттєво різні методи: лінійна вставка, центрована вставка і двійкова вставка. Ці методи сортування розрізняються методами пошуку відповідного місця для вставки елемента. Найпростішим методом є лінійна вставка. Як випливає з назви, в цьому методі вже існуючий список розглядається як простий лінійний список, що переглядається поелементно зверху вниз, поки не буде знайдена відповідна позиція для нового елемента.
Цей метод зазвичай використовується тоді, коли процес, зовнішній до даної сортування, динамічно вносить додавання до списку, всі елементи якого відомі і який повинен весь час підтримуватися в упорядкованому стані. Сортування виконується кожного разу при отриманні нового елемента, розміщуючи цей елемент у потрібне місце списку й полегшуючи контроль. Деякі характеристики систем реального часу роблять вставку корисним технічним прийомом.
Зв'язок між процесом, що породжує підлягають сортуванню числа, і сортуванням така, що сортування залучається багато разів. Таке повторне притягнення може бути пов'язане з деякими витратами, такими як передача параметрів, вхід і вихід з процедури. Ці витрати повинні бути виявлені і враховані при аналізі використання методу вставок таким способом. Сортування вставками можна організувати як один уніфікований процес.
Метод лінійної вставки. Під сортування виділяється кількість пам'яті, рівне передбачуваної довжині остаточного списку з усіх елементів. Лічильник довжини списку на самому початку встановлюється рівним нулю. За допомогою цього лічильника контролюється довжина області пошуку потрібної позиції для елемента, що вставляється в список. Сортування залучається для кожного елемента. Один «виклик» сортуючої підпрограми розміщує один елемент в списку і збільшує лічильник списку на одиницю.
Перший елемент міститься у верхню позицію області виведення. Наступний елемент, що приєднується до списку, порівнюється з першим. Якщо ключ нового елемента більше, він поміщається в позицію, наступну за позицією першого елемента. Якщо ключ нового елемента менше, то перший елемент переміщається в позицію 2, а новий елемент міститься в позицію 1.
Надалі всі нові елементи послідовно порівнюються з кожним елементом списку, починаючи з першого, до тих пір, поки не зустрітися більший. Цей більший елемент і всі наступні елементи списку пересуваються на одну позицію вниз. Таким чином звільняється місце, на яке вставляється новий елемент.
Метод сортування Шелла
Сортування Шелла є розширенням сортування просіюванням. Останній перегляд у сортуванні Шелла ідентичний методу просіювання, описаного вище. Попередні перегляди використовують той самий технічний прийом, але в них порівнюються і обмінюються не безпосередні сусіди, а елементи віддалені на задану відстань. Наприклад, позиція 1 порівнюється з позицією 5, позиція 5 з позицією 9, 9 з 13 і т.д. Коли виявлена інверсія, ланцюжок вторинних порівнянь охоплює ті елементи, які входили в послідовність первинних порівнянь. Наприклад, якщо виявлено інверсія між позиціями 9 і 13, то можлива вторинна послідовність складається з порівнянь 5: 9 і 1: 5.
На кожному перегляді крок між порівнюваними елементами визначається шляхом скорочення обчисленого вихідного кроку. На останньому перегляді він скорочується до 1. Мета методу на ранніх переглядах - скоротити число вторинних порівнянь і обмінів на більш пізніх переглядах. У цьому методі елементи можуть здійснювати великі стрибки до потрібних позиціях на ранніх переглядах, а не пересуватися на одну позицію за один раз. На останньому перегляді числа будуть прагнути розташовуватися близько до своїх позиціях і, отже, зажадають незначних переміщень при остаточному розміщенні.
Модифікації методу розрізняються способами обчислення початкового кроку між елементами і правилами скорочення цього кроку від перегляду до перегляду.
Варіант з відкладеними обмінами
При описі методу сортування Шелла передбачалося, що обмін слід за кожним порівнянням, яке виявляє елемент більший, ніж попередній елемент частини. В алгоритмі (опублікованому Хиббард) використаний метод, який скорочує число обмінів. Цей алгоритм відрізняється то раніше описаного тим, що він використовує тимчасову пам'ять для зберігання порівнюваних елементів протягом всієї послідовності порівнянь.
Кожне первинне порівняння Ключ i: ключ i + крок включає пересилку ключ i + крок в тимчасову пам'ять. Порівняння позиції 1 з позицією 4, наприклад, насправді включає пересилання з позиції 4 в тимчасову пам'ять і порівняння ключа з тимчасової пам'яті з ключем з позиції 1. Якщо ключ i більше, він переміщається в позицію ключ i + крок. Якщо ключ i + крок більше, то переміщення не потрібно. Пересилання в тимчасову пам'ять дозволяє ефективно звільняти позицію подальшого елемента цієї частини.
Коли ключ i більше, ніж ключ i + крок, то ключ i пересилається зі своєї позиції в «вільну» позицію, і метод починає послідовність вторинних порівнянь. Вміст тимчасової пам'яті (ключ i + крок) - це запис, що піднімається на верх цієї частини. Ключ кожного запису порівнюється з тимчасовою пам'яттю і, якщо виявлено, що він більше, пересилається вниз списку в поточну вільну позицію. Кожна пересилання звільняє позицію переміщеного елементу. Коли в списку виявлений елемент з ключем, меншим ключа тимчасової пам'яті, вміст тимчасової пам'яті поміщається в позицію списку звільненій самої останньої, тобто в потрібне місце.
Використання тимчасової пам'яті ефективно тоді, коли довжина послідовності вторинних порівнянь не менше 2. Оскільки, швидше за все це вірно для списків довільній кінцевої довжини з випадково впорядкованими даними, то варіант з відкладеними обмінами може, взагалі кажучи, бути кращим за інших сортувань Шелла.
Швидке сортування
Метод швидкого сортування був вперше описаний Ч.А.Р. Хоаром У 1962 році. Швидке сортування - це загальна назва ряду алгоритмів, які відображають різні підходи до одержання критичного параметра, що впливає на продуктивність методу.
Метод швидкого сортування. Деякий елемент списку вибирається як «основи». Всі елементи, менше основи, розміщуються в позиціях з початку списку »; всі елементи, більше основи, розміщуються в позиціях з кінця списку. Елементи порівнюються з основою і змінюють свою позицію, коли вони більше і розташовані в писку вище за неї, або коли менше і розташовані в списку нижче неї. Це упорядкування становить етап сортування. В кінці етапу для розміщення основи придатна деяка позиція в списку. Ця позиція відповідає місцю основи в остаточному списку, оскільки її відносний адреса в списку визначається кількістю елементів вище і нижче неї.
Етап визначає дві частини. Якщо значення основи добре апроксимує медіану списку, то ці дві частини будуть приблизно однакової довжини. Якщо основа є найгіршою можливою оцінкою медіани (найбільшим або найменшим елементом списку), то ці частини будуть довжиною 0 і К - 1, де К - це довжина вихідного списку.
Спосіб побудови частин, по суті, один і той же у всіх версіях алгоритму. Встановлюються два покажчики, один на початок, інший на кінець списку. Після вибору основи пошук меншої величини починається з покажчика кінця, що переміщається вгору до початку списку. Порівняння тривають до тих пір, поки не буде знайдений елемент, менший основи, або не буде вичерпаний список.
Коли елемент, меншою основи, знайдений, його необхідно перемістити в позицію, що містить елемент, більшою основи. Ця позиція знаходиться при порівняннях, що використовують покажчик початку. Порівняння виконуються зверху в низ по списку до тих пір, поки вказівник початку не вкаже на більший елемент. Таким чином, елементи, більший і менший основи, ідентифіковані, і тепер виконується обмін між ними.
Модифікації виникають тільки в методі пересилання елементів даних. Один спосіб полягає в тому, що основа пересилається в тимчасову пам'ять, а вміст початку списку переміщається в звільнилася позицію. При цьому звільняється початкова позиція, куди можна перемістити елемент. Після пересилки вільна позиція зсувається в клітинку, розташовану близько до кінця списку. При низхідному пошуку відшукується елемент для пересилки в цю вільну позицію. Вільна позиція чергується з верхньої та нижньої позиціями до тих пір, поки покажчики не сумісний.
Після обміну або подвійний пересилання відновлюється пошук іншого елемента, меншого основи. Коли він знайдений, починається пошук більшого елемента з використанням покажчика початку. Цей процес продовжується до тих пір, поки два покажчика не зустрінуться. Відносна довжина частин визначається позицією в списку, в якій сполучаться покажчики початку і кінця. У деяких версіях цього методу необхідно порівнювати відносні позиції покажчиків після кожного переміщення за списком вгору або вниз.
На першому етапі будуються дві частини. Одна з них використовується в якості вихідної на другому етапі, друга поміщається в стек LIFO. Загальне правило таке: першої обробляти меншу частину, а кордони більшою запам'ятовувати в стеці. Другий етап породжує дві частини. Менша обробляється на третьому етапі, а велика переміщається в стек над більшою частиною, побудованої на етапі 1. Процес породження частин, запам'ятовування більшій з них в стеку і поділу меншою продовжується до тих пір, поки всі частини не скоротяться до одного елемента. При виникненні одноелементної частини нова частина для стека не будується. Очікують частини вибираються з стека й обробляються. Сортування виконана, коли стек порожній.
Обробка меншою з двох частин гарантує, що очікують частин в стеку буде не більше log 2 N. Послідовність обробки частин абсолютно довільна і може змінюватися за бажанням програміста.
Швидке сортування може використовуватися в комбінованому алгоритмі, щоб скоротити частині до заздалегідь визначеного розміру, після чого вони упорядковуються іншим методом, більш ефективним для малих списків.
Алг QuickSort (арг цілий m, t)
поч цілий i, j, x, w
i: = m
j: = t
x: = div (A (m + t), 2)
НЦ
НЦ поки A [i] <x
i: = i +1
КЦ
НЦ поки A [j]> x
j: = j-1
КЦ
якщо i <= j
то
w: = A [i]
A [i]: = A [j]
A [j]: = w
i: = i +1
j: = j-1
всі
КЦ поки i> j;
якщо m <j
то QuickSort (m, j);
всі
якщо i <t
то QuickSort (i, t);
всі
кон
Оцінимо ефективність методу. Припустимо, що розмір масиву дорівнює числу, що є ступенем двійки, і при кожному поділі елемент X знаходиться точно в середині масиву. У цьому випадку при першому перегляді виконується N порівнянь і масив поділяється на дві частини розмірами »N / 2 порівнянь і т.д. отже,
C = N + 2 × (N / 2) + 4 × (N / 4) + ... + N × (N / N) = O (N × log 2 N).
Внутрішнє злиття
Основою процесу злиття є фундаментальна ідея впорядкування даних шляхом чергування елементів з двох або більше впорядкованих списків. Упорядкований об'єднання цих списків являє собою остаточний упорядкований список з десяти елементів. Порівнюються найменші елементи кожної частини і меншої з них просувається в список виведення. Процес порівняння елементів, просування меншого в список виведення і вибір наступника в «перемогла» частини продовжується до тих пір, поки не вичерпується одна з частин. Після того, як одна частина вичерпана, всі залишилися елементи інший пересилаються в список виведення.
Алг Sl (арг цілий k, m, q, цілий таб A [1: N])
поч цілий k, i, j, t, цілий таб A [1: N]
i: = k
j: = m +1
t: = 1
НЦ поки (i <= m) і (j <= q)
якщо A [i] <= A [j] то
D [t]: = A [i]
i: = i +1
інакше
D [t]: = A [j]
j: = j +1
t: = t +1
всі
КЦ
НЦ поки i = m
D [t]: = A [i]
i: = i +1
t: = t +1
НЦ поки j: = q
D [t]: = A [j]
j: = j +1
t: = t +1
КЦ
КЦ
НЦ для i від 1 до t - 1
A [k + i - 1]: = D [i]
КЦ
кон
Ефективність алгоритму складає C = O (N × log 2 N).
Основні поняття і методи сортування
Сортування - це процес розстановки елементів «в деякому порядку». Елементи розміщуються так, щоб, по-перше, обчислення потребують певного порядку розташування даних, могли виконуватися ефективно, по-друге, результати мали осмислений вигляд, по-третє, подальші процеси б придатні вихідні дані.
Записи, поля і ключі. Одиниця даних, типово оброблювана інформаційними системами, називається записом. Запис - це сукупність елементів інформації про якусь подію або структурі. Кожен елемент інформації в записі, такий як номер службовця, ціна одиниці товару або валовий обсяг, називається полем запису. Сукупність полів ідентифікує і описує те, що представлено в записі. Із записів складаються файли чи набори даних. Сортування є процесом перестановки записів або їх індексів, при якому їх взаємне розташування у файлі приводитися в порядок, який визначається деяким відомим ключем. Ключем називається поле, що містить величину, яка використовується в правилах упорядкування файлу.
У припущенні, що результатом сортування є фізична упорядкування, сортування двох записів у своїй простій формі складається з порівняння їх ключових полів і визначень, яке з них «менше». Після цього запису переставляються так, що запис з «меншим» ключем ставитися перед записом з «великим» ключем.
Визначити, який ключ «менше», можна, використовуючи будь-яке правило. Очевидними правилами є: алфавітне упорядкування, числове і буквено-цифрове. (В останньому правилі ключі можуть містити суміш букв і цифр; угоди, прийняті в системі, визначають впорядкування букв і цифр.)
Ключем запису може бути одне поле або комбінація полів, розподілених по запису. Якщо ключ складається з кількох несоприкасающихся полів, то він називається складеним ключем.
Інколи бажано впорядкування всередині упорядкування. Наприклад, файл може бути впорядкований за номером місця роботи, а всередині цього впорядкування - за номером службовця. Поле, що містить номер місця роботи, називається старшим ключем, а поле, що містить номер службовця, - молодшим ключем. Так модно визначити кілька рівнів ключів, і всі рівні, відмінні від першого, називаються молодшими ключами. Старший і молодший ключі можна розглядати як один складений ключ в записі.
В інформаційній системі іноді зручно, щоб файли упорядковувалися не єдиним способом. Різні сортування в якості ключа можуть використовувати різні поля.
Запис може складатися тільки з поля ключа. В обробці наукових програм цей процес не є чимось винятковим. У даній роботі при розгляді методів сортування передбачатиметься, що записи складаються з одного поля. Це зроблено для того, щоб спростити початкове уявлення про методи сортування за рахунок усунення побічних проблем, що виникають під час переміщення даних. Оскільки ці методи однаково добре застосовні до записів, що містить як ключові, так і неключові поля, то це припущення не обмежує спільності.
Традиційно методи сортування ділять на внутрішні і зовнішні. Внутрішні методи - це такі методи, які можуть застосовуватися з прийнятною продуктивністю тільки до тих списками даних, які цілком вкладаються в основний (оперативної) пам'яті процесора. Зовнішні методи - це такі методи, які прийнятні для файлів даних, які занадто великі, щоб поміститься в основній пам'яті, і тому повинні протягом процесу сортування розташовуватися на пристроях зовнішньої пам'яті (стрічках, дисках, барабанах). Слово список часто позначає набір записів, розташованих в основній пам'яті.
Лінійний вибір з обміном: використання обмінів
Як приклад обміну в процесі сортування розглянемо тут мінімальну по пам'яті версію лінійного вибору. Обміном називається перестановка позицій двох записів в списку в залежності від результату перевірки їх відносної величини. Якщо в списку зустрічається запис з ключем, меншим, ніж у попередньої, то ці записи міняються місцями. Продуктивність методів обміну залежить від складності визначення послідовності порівнянь та обмінів. Часто кількість обмінів скорочують, відкладаючи обмін до кінця кожного перегляду. Це прийом, зокрема, використовується у методі, який буде описаний нижче.
Лінійний вибір з обміном. На початку першого перегляду передбачається, що перший елемент списку має найменший ключ. Цей ключ разом з адресою пересилається в робочу пам'ять, де порівнюється з усіма лінійними наступниками до тих пір, поки не зустрінеться менший ключ. Менший ключ і його адресу стають вмістом робочої області пам'яті.
Порівняння продовжуються при новому вмісті робочої пам'яті. Пересилання виконується завжди, коли в списку зустрічається ключ, який менше ключа в робочій пам'яті. Таким чином, в робочій пам'яті завжди розташований найменший з вже переглянутих ключів. Перегляд закінчується після досягнення кінця списку. До цього моменту процес ідентичний простому лінійному вибору. Сортування обміном відрізняється наступним кроком.
По закінченні першого перегляду запис, ключ якої розташований в робочій пам'яті, переставляється з записом з вершини списку. Тепер найменша величина в списку займає першу позицію. Другий перегляд ідентичний першому з тією лише різницею, що другим за величиною вважається другий ключ, так як першим стоїть найменший елемент. Перша позиція виключається з процесу. Після закінчення другого перегляду другий запис з найменшим ключем поміщається в другу позицію списку. Третій перегляд починається порівнянням ключа з третьої позиції і т.д. Ця процедура закінчується, коли своє місце займає (N - 1) - я запис.
алг Sort (арг цілий N, вещ таб A [1: N])
поч цілий i, j, k, Maxi
НЦ для i від N до 2 крок -1
Maxi: = i;
НЦ для j від 1 до i - 1
Якщо A [j]> A [Maxi]
то Maxi: = j;
всі
Якщо Maxi <> i
то k: = A [i];
A [i]: = A [Maxi];
A [Maxi]: = k;
всі
КЦ
кон
Оцінимо кількість порівнянь. При першому перегляді їх N - 1, при другому - N - 2, при останньому - 1. Загальна кількість C = N -1 + N - 2 + ... + 1 = C = N × (N - 1) / 2, тобто має порядок O (N 2).
Лінійний вибір з підрахунком
Метод сортування з підрахунком описується в літературі як процедура впорядкування внутрішнього списку чисел. Фактично, це не метод сортування, а технічний прийом, який можна використовувати в різних методах для скорочення кількості обмінів або повного їх усунення. Він є формою індексування, в якій лічильник відносної позиції кожного елемента коригується протягом процесу порівняння. Нижче буде описано цей технічний прийом стосовно до лінійного вибору.
Підрахунок як технічний прийом. Пам'ять, яка використовується лінійним вибором з підрахунком, буде включати область виводу (так само як і при лінійному виборі) для зберігання остаточно упорядкованого списку. Розмір області виведення відповідає тим же міркувань, що і при лінійному виборі. Додатково повинна бути забезпечена пам'ять під лічильник для кожного елемента списку. У результаті дій над значеннями цих лічильників утворюється безліч індексів позицій для елементів в упорядкованому списку. При кожному перегляді ключ порівнюється зі своїми лінійними наступниками. Кожного разу, коли знаходиться більший ключ, його лічильник збільшується на одиницю. Якщо знайдений ключ менше або дорівнює, то збільшується лічильник відповідний більшого з порівнюваних ключів. Отже, в будь-який момент часу лічильник елемента вказує кількість ключів, про які відомо, що вони менше ключа, що розглядається.
При першому перегляді перший ключ у списку порівнюється з усіма іншими ключами. У його лічильнику підраховується кількість менших ключів. У лічильниках великих ключів будуть 1. При другому перегляді перший ключ не розглядається. Другий ключ порівнюється з ключами всіх наступників. Підрахунки фіксуються. Цей процес триває N - 1 раз. На цьому етапі відомо відносна позиція кожного елемента. Помістивши ключі у вихідний список у відповідності зі значеннями їх лічильників, отримуємо упорядкований список.
алг Sort (арг цілий N, цілий таб A [1: N], рез цілий таб B [1: N]);
поч цілий i, j, цілий таб Count [1: N]
НЦ для i від N до 2 крок -1
НЦ для j від i - 1 до 1 крок -1
Якщо A [i] <A [j]
то Count [j]: = Count [j] + 1
інакше Count [i]: = Count [j] +1
всі
КЦ
КЦ
НЦ для i від 1 до N
B [Count [i] + 1]: = A [i]
КЦ
кон
Число порівнянь дорівнює N 2 / 2. Виконується (N-1) переглядів з N / 2 порівняннями в середньому на кожному перегляді. Значення лічильників змінюється стільки разів, скільки разів виконується порівняння.
Сортування обміном
Сортування обміном - це загальний термін, використовуваний для опису сімейства мінімальних по пам'яті методів сортування, які міняють місцями елементи списку, якщо попередній елемент більше наступного. Перегляд файлу може протікати зверху вниз або знизу вгору або змінюватися від перегляду до перегляду.
Існує ряд певних варіантів, які різняться послідовностями порівнянь елементів списку. У всіх елементарних методах обміну елемент порівнюється зі своїм найближчим сусідом, а можливими переміщеннями є переміщення елемента з великим ключем на одну позицію вниз і переміщення елемента з меншим ключем на одну позицію вгору. Парний обмін, стандартний обмін і просіювання є трьома простими формами сортування обміном.
Метод парного обміну (також званий «непарній-парна перестановка») складається з різного числа «непарних» і «парних» переглядів. При непарних переглядах кожен елемент з непарної позиції порівнюється зі своїм сусідом з парної позиції і більший з них займає велику позицію. Спадний перегляд списку продовжується до тих пір, поки останній непарний елемент (N - 1) у списку не порівнюється з останнім парних елементом N. Якщо в списку непарне число елементів, то останній елемент не буде брати участь в порівнянні. Протягом кожного перегляду ведеться підрахунок обмінів.
При парних переглядах парні позиції порівнюються з сусідніми непарними. Обміни виконуються тоді, коли треба, щоб більший з пари зайняв непарну позицію. Таким чином, ключі з великими значеннями переміщуються на дно списку. При цьому повинно бути стільки переглядів, скільки необхідно для того щоб перемістити в позицію число, найбільш віддалене від своєї кінцевої позиції. Потім виконується заключний перегляд, необхідний для того, щоб пізнати впорядкованість. Протягом цього перегляду лічильник обмінів дорівнює 0. Даний метод вимагає, принаймні, двох переглядів - одного непарного і одного парного.
Метод стандартного обміну (також званий «методом бульбашки») переміщує один елемент списку у відповідну позицію при кожному перегляді. Таким чином, при першому перегляді запис з найбільшим ключем поміщається в останню позицію, при другому перегляді запис із наступним за величиною ключем переміщається в передостанню позицію і т.д. Метод може бути перетворений так, що буде розміщувати елементи за спаданням.
При першому перегляді перший елемент списку порівнюється зі своїм безпосереднім наступником, і, якщо цей наступник менше, вони міняються місцями. Тепер більший елемент, розташований в другій позиції, порівнюється з елементом з третьої позиції. Обмін відбувається, якщо необхідно більший з них розмістити в третій позиції. Потім позиція 3 порівнюється з позицією 4, позиція 4 з позицією 5 і т.д. коли позиція N - 1 порівнюється з позицією N, перегляд закінчується.
Якщо в списку елемент k - 1 розташований раніше ніж k, то при кожному порівнянні (k - 1): k більший елемент потрапляє в позицію k. Елемент, переміщуваний вниз, вважається в даний момент найбільшим у списку. Коли при порівнянні виявляється, що k-й елемент більше, обмін не відбувається. Отже, кожен раз порівнюються елемент, який вважається найбільшим (k - 1), і його безпосередній наступник k.
Другий перегляд ідентичний першому з тією лише різницею, що вже встановлена позиція виключається з послідовності. Кожен наступний перегляд виключає чергову встановлену позицію, скорочуючи список.
Підрахунок обмінів ведеться для кожного перегляду. Перегляд, в результаті якого кількість обмінів не збільшилася, закінчує сортування.
алг Sort (арг цілий N, цілий таб A [1: N])
поч цілий k, i, w
НЦ для k від N до N - 1
НЦ для i від 1 до N - k
якщо A [i]> A [i + 1]
то w: = A [i]
A [i]: = A [i + 1]
A [i + 1]: = w
всі
КЦ
КЦ
кон
При сортуванні «методом бульбашки» виконується N - 1 перегляд, причому на i - му перегляді проводиться N - i порівнянь. Загальне колічесво порівнянь C = N × (N - 1) / 2, тобто має порядок O (N 2).
Метод просіювання (також званий «лінійної вставкою з обміном» чи «човникової сортуванням») є найкращим з цих методів. Він відрізняється від інших методів обміну тим, що не зберігає фіксованого послідовності порівнянь. Крім цього, зникає поділ на окремі перегляди як наслідок схеми послідовностей порівнянь. Метод просіювання працює точно так само, як стандартний обмін до тих пір, поки не треба виконувати перестановку. Порівнювана величина з меншим ключем піднімається наскільки це можливо вгору за списком. Вона порівнюється «у зворотному порядку» з усіма її лінійними попередниками у напрямку до вершини списку. Якщо її ключ менше, ніж у попередника, то виконується обмін і починається чергове порівняння. Коли елемент, пересувається угору, зустрічається з меншим ключем, цей процес припиняється і спадні порівняння поновлюються з тієї позиції, з якої виконувався перший обмін.
Будемо називати спадний порівняння первинним, а висхідний вторинним. Будь-яке первинне порівняння може збільшити число вторинних порівнянь. Якщо первинне порівняння охоплює позиції 6 і 7, то ланцюжок вторинних порівнянь може мати саме більший 5 порівнянь. Цей максимум досягається, якщо вихідний ключ з позиції 7 менше всіх ключів у списку, розташованих вище цієї позиції. Фактична довжина послідовності вторинних порівнянь залежить від величини рухається вгору елемента щодо величини кожного елемента з попередньої впорядкованої частині списку.
Сортування закінчується, коли первинне порівняння охопить (N + 1) - й елемент.
Сортування вставками
Сортування вставками є загальна назва групи методів сортування, заснованих на послідовній вставці «нових» елементів у збільшується впорядковуємо список. Серед них є три суттєво різні методи: лінійна вставка, центрована вставка і двійкова вставка. Ці методи сортування розрізняються методами пошуку відповідного місця для вставки елемента. Найпростішим методом є лінійна вставка. Як випливає з назви, в цьому методі вже існуючий список розглядається як простий лінійний список, що переглядається поелементно зверху вниз, поки не буде знайдена відповідна позиція для нового елемента.
Цей метод зазвичай використовується тоді, коли процес, зовнішній до даної сортування, динамічно вносить додавання до списку, всі елементи якого відомі і який повинен весь час підтримуватися в упорядкованому стані. Сортування виконується кожного разу при отриманні нового елемента, розміщуючи цей елемент у потрібне місце списку й полегшуючи контроль. Деякі характеристики систем реального часу роблять вставку корисним технічним прийомом.
Зв'язок між процесом, що породжує підлягають сортуванню числа, і сортуванням така, що сортування залучається багато разів. Таке повторне притягнення може бути пов'язане з деякими витратами, такими як передача параметрів, вхід і вихід з процедури. Ці витрати повинні бути виявлені і враховані при аналізі використання методу вставок таким способом. Сортування вставками можна організувати як один уніфікований процес.
Метод лінійної вставки. Під сортування виділяється кількість пам'яті, рівне передбачуваної довжині остаточного списку з усіх елементів. Лічильник довжини списку на самому початку встановлюється рівним нулю. За допомогою цього лічильника контролюється довжина області пошуку потрібної позиції для елемента, що вставляється в список. Сортування залучається для кожного елемента. Один «виклик» сортуючої підпрограми розміщує один елемент в списку і збільшує лічильник списку на одиницю.
Перший елемент міститься у верхню позицію області виведення. Наступний елемент, що приєднується до списку, порівнюється з першим. Якщо ключ нового елемента більше, він поміщається в позицію, наступну за позицією першого елемента. Якщо ключ нового елемента менше, то перший елемент переміщається в позицію 2, а новий елемент міститься в позицію 1.
Надалі всі нові елементи послідовно порівнюються з кожним елементом списку, починаючи з першого, до тих пір, поки не зустрітися більший. Цей більший елемент і всі наступні елементи списку пересуваються на одну позицію вниз. Таким чином звільняється місце, на яке вставляється новий елемент.
Метод сортування Шелла
Сортування Шелла є розширенням сортування просіюванням. Останній перегляд у сортуванні Шелла ідентичний методу просіювання, описаного вище. Попередні перегляди використовують той самий технічний прийом, але в них порівнюються і обмінюються не безпосередні сусіди, а елементи віддалені на задану відстань. Наприклад, позиція 1 порівнюється з позицією 5, позиція 5 з позицією 9, 9 з 13 і т.д. Коли виявлена інверсія, ланцюжок вторинних порівнянь охоплює ті елементи, які входили в послідовність первинних порівнянь. Наприклад, якщо виявлено інверсія між позиціями 9 і 13, то можлива вторинна послідовність складається з порівнянь 5: 9 і 1: 5.
На кожному перегляді крок між порівнюваними елементами визначається шляхом скорочення обчисленого вихідного кроку. На останньому перегляді він скорочується до 1. Мета методу на ранніх переглядах - скоротити число вторинних порівнянь і обмінів на більш пізніх переглядах. У цьому методі елементи можуть здійснювати великі стрибки до потрібних позиціях на ранніх переглядах, а не пересуватися на одну позицію за один раз. На останньому перегляді числа будуть прагнути розташовуватися близько до своїх позиціях і, отже, зажадають незначних переміщень при остаточному розміщенні.
Модифікації методу розрізняються способами обчислення початкового кроку між елементами і правилами скорочення цього кроку від перегляду до перегляду.
Варіант з відкладеними обмінами
При описі методу сортування Шелла передбачалося, що обмін слід за кожним порівнянням, яке виявляє елемент більший, ніж попередній елемент частини. В алгоритмі (опублікованому Хиббард) використаний метод, який скорочує число обмінів. Цей алгоритм відрізняється то раніше описаного тим, що він використовує тимчасову пам'ять для зберігання порівнюваних елементів протягом всієї послідовності порівнянь.
Кожне первинне порівняння Ключ i: ключ i + крок включає пересилку ключ i + крок в тимчасову пам'ять. Порівняння позиції 1 з позицією 4, наприклад, насправді включає пересилання з позиції 4 в тимчасову пам'ять і порівняння ключа з тимчасової пам'яті з ключем з позиції 1. Якщо ключ i більше, він переміщається в позицію ключ i + крок. Якщо ключ i + крок більше, то переміщення не потрібно. Пересилання в тимчасову пам'ять дозволяє ефективно звільняти позицію подальшого елемента цієї частини.
Коли ключ i більше, ніж ключ i + крок, то ключ i пересилається зі своєї позиції в «вільну» позицію, і метод починає послідовність вторинних порівнянь. Вміст тимчасової пам'яті (ключ i + крок) - це запис, що піднімається на верх цієї частини. Ключ кожного запису порівнюється з тимчасовою пам'яттю і, якщо виявлено, що він більше, пересилається вниз списку в поточну вільну позицію. Кожна пересилання звільняє позицію переміщеного елементу. Коли в списку виявлений елемент з ключем, меншим ключа тимчасової пам'яті, вміст тимчасової пам'яті поміщається в позицію списку звільненій самої останньої, тобто в потрібне місце.
Використання тимчасової пам'яті ефективно тоді, коли довжина послідовності вторинних порівнянь не менше 2. Оскільки, швидше за все це вірно для списків довільній кінцевої довжини з випадково впорядкованими даними, то варіант з відкладеними обмінами може, взагалі кажучи, бути кращим за інших сортувань Шелла.
Швидке сортування
Метод швидкого сортування був вперше описаний Ч.А.Р. Хоаром У 1962 році. Швидке сортування - це загальна назва ряду алгоритмів, які відображають різні підходи до одержання критичного параметра, що впливає на продуктивність методу.
Метод швидкого сортування. Деякий елемент списку вибирається як «основи». Всі елементи, менше основи, розміщуються в позиціях з початку списку »; всі елементи, більше основи, розміщуються в позиціях з кінця списку. Елементи порівнюються з основою і змінюють свою позицію, коли вони більше і розташовані в писку вище за неї, або коли менше і розташовані в списку нижче неї. Це упорядкування становить етап сортування. В кінці етапу для розміщення основи придатна деяка позиція в списку. Ця позиція відповідає місцю основи в остаточному списку, оскільки її відносний адреса в списку визначається кількістю елементів вище і нижче неї.
Етап визначає дві частини. Якщо значення основи добре апроксимує медіану списку, то ці дві частини будуть приблизно однакової довжини. Якщо основа є найгіршою можливою оцінкою медіани (найбільшим або найменшим елементом списку), то ці частини будуть довжиною 0 і К - 1, де К - це довжина вихідного списку.
Спосіб побудови частин, по суті, один і той же у всіх версіях алгоритму. Встановлюються два покажчики, один на початок, інший на кінець списку. Після вибору основи пошук меншої величини починається з покажчика кінця, що переміщається вгору до початку списку. Порівняння тривають до тих пір, поки не буде знайдений елемент, менший основи, або не буде вичерпаний список.
Коли елемент, меншою основи, знайдений, його необхідно перемістити в позицію, що містить елемент, більшою основи. Ця позиція знаходиться при порівняннях, що використовують покажчик початку. Порівняння виконуються зверху в низ по списку до тих пір, поки вказівник початку не вкаже на більший елемент. Таким чином, елементи, більший і менший основи, ідентифіковані, і тепер виконується обмін між ними.
Модифікації виникають тільки в методі пересилання елементів даних. Один спосіб полягає в тому, що основа пересилається в тимчасову пам'ять, а вміст початку списку переміщається в звільнилася позицію. При цьому звільняється початкова позиція, куди можна перемістити елемент. Після пересилки вільна позиція зсувається в клітинку, розташовану близько до кінця списку. При низхідному пошуку відшукується елемент для пересилки в цю вільну позицію. Вільна позиція чергується з верхньої та нижньої позиціями до тих пір, поки покажчики не сумісний.
Після обміну або подвійний пересилання відновлюється пошук іншого елемента, меншого основи. Коли він знайдений, починається пошук більшого елемента з використанням покажчика початку. Цей процес продовжується до тих пір, поки два покажчика не зустрінуться. Відносна довжина частин визначається позицією в списку, в якій сполучаться покажчики початку і кінця. У деяких версіях цього методу необхідно порівнювати відносні позиції покажчиків після кожного переміщення за списком вгору або вниз.
На першому етапі будуються дві частини. Одна з них використовується в якості вихідної на другому етапі, друга поміщається в стек LIFO. Загальне правило таке: першої обробляти меншу частину, а кордони більшою запам'ятовувати в стеці. Другий етап породжує дві частини. Менша обробляється на третьому етапі, а велика переміщається в стек над більшою частиною, побудованої на етапі 1. Процес породження частин, запам'ятовування більшій з них в стеку і поділу меншою продовжується до тих пір, поки всі частини не скоротяться до одного елемента. При виникненні одноелементної частини нова частина для стека не будується. Очікують частини вибираються з стека й обробляються. Сортування виконана, коли стек порожній.
Обробка меншою з двох частин гарантує, що очікують частин в стеку буде не більше log 2 N. Послідовність обробки частин абсолютно довільна і може змінюватися за бажанням програміста.
Швидке сортування може використовуватися в комбінованому алгоритмі, щоб скоротити частині до заздалегідь визначеного розміру, після чого вони упорядковуються іншим методом, більш ефективним для малих списків.
Алг QuickSort (арг цілий m, t)
поч цілий i, j, x, w
i: = m
j: = t
x: = div (A (m + t), 2)
НЦ
НЦ поки A [i] <x
i: = i +1
КЦ
НЦ поки A [j]> x
j: = j-1
КЦ
якщо i <= j
то
w: = A [i]
A [i]: = A [j]
A [j]: = w
i: = i +1
j: = j-1
всі
КЦ поки i> j;
якщо m <j
то QuickSort (m, j);
всі
якщо i <t
то QuickSort (i, t);
всі
кон
Оцінимо ефективність методу. Припустимо, що розмір масиву дорівнює числу, що є ступенем двійки, і при кожному поділі елемент X знаходиться точно в середині масиву. У цьому випадку при першому перегляді виконується N порівнянь і масив поділяється на дві частини розмірами »N / 2 порівнянь і т.д. отже,
C = N + 2 × (N / 2) + 4 × (N / 4) + ... + N × (N / N) = O (N × log 2 N).
Внутрішнє злиття
Основою процесу злиття є фундаментальна ідея впорядкування даних шляхом чергування елементів з двох або більше впорядкованих списків. Упорядкований об'єднання цих списків являє собою остаточний упорядкований список з десяти елементів. Порівнюються найменші елементи кожної частини і меншої з них просувається в список виведення. Процес порівняння елементів, просування меншого в список виведення і вибір наступника в «перемогла» частини продовжується до тих пір, поки не вичерпується одна з частин. Після того, як одна частина вичерпана, всі залишилися елементи інший пересилаються в список виведення.
Алг Sl (арг цілий k, m, q, цілий таб A [1: N])
поч цілий k, i, j, t, цілий таб A [1: N]
i: = k
j: = m +1
t: = 1
НЦ поки (i <= m) і (j <= q)
якщо A [i] <= A [j] то
D [t]: = A [i]
i: = i +1
інакше
D [t]: = A [j]
j: = j +1
t: = t +1
всі
КЦ
НЦ поки i = m
D [t]: = A [i]
i: = i +1
t: = t +1
НЦ поки j: = q
D [t]: = A [j]
j: = j +1
t: = t +1
КЦ
КЦ
НЦ для i від 1 до t - 1
A [k + i - 1]: = D [i]
КЦ
кон
Ефективність алгоритму складає C = O (N × log 2 N).