довірою. Насправді ж, лише небагато методи досягають стабільності без використання додаткового часу або місця.
Наступна програма, для сортування трьох записів, призначена для ілюстрації основних угод, які ми будемо використовувати. Зокрема, головна програма цікава тим, що вона працює тільки для N = 3; сенс у тому, що будь-яка програма сортування може бути зведена до процедури sort3 цієї програми.
Три оператора присвоєння, кожен з яких супроводжується оператором if, на ділі реалізують операцію В«обмінуВ». Ми вставляємо її безпосередньо в програмний код замість використання виклику процедури, оскільки вони є основою багатьох алгоритмів і часто потрапляють всередину циклу.
Щоб сконцентруватися на алгоритмічних питаннях, ми будемо працювати з алгоритмами, які просто сортують масиви цілих в чисельному порядку. Загалом, дуже легко адаптувати такі алгоритми для практичного використання, що включає в себе роботу з великими ключами або записами. В основному програми сортування працюють із записами двома способами: або вони порівнюють і сортують тільки ключі, або пересувають записи цілком. Більшість алгоритмів, які ми вивчимо можна застосовувати, за допомогою їх переформулювання в термінах цих двох операцій, для довільних записів. Якщо сортовані записи досить великі, то зазвичай намагаються уникнути пересування їх за допомогою В«непрямої сортуванняВ»: при цьому самі записи не переупорядочівать, а замість цього переупорядочівать масив покажчиків (індексів), так, що перший покажчик вказує на найменший елемент і так далі. Ключі можуть зберігатися або з записами (якщо вони великі), або з покажчиками (якщо вони маленькі). Якщо необхідно, то після сортування запису можна впорядкувати. Це описано далі. p> Програма sort3 використовує навіть більш обмежений доступ до файлу: це три операції виду В«Порівняти два записи і обміняти їх, якщо потрібно, щоб помістити запис з меншим ключем на перше місце В». Програми, обмежені такими операціями цікаві, оскільки вони підходять для реалізації на апаратному рівні. Ми вивчимо їх більш докладно пізніше.
Всі приклади програм використовують для сортування глобальний масив. Це не означає, що такий підхід краще або гірше ніж передача масиву як параметра. Все залежить від точки зору і конкретного алгоритму. Масив зроблено глобальним тільки тому, що тоді приклади стають коротшими і зрозуміліше.
Сортування вибором
Один з найпростіших методів сортування працює наступним чином: знаходимо найменший елемент в масиві і обмінюємо його з елементом знаходяться на першому місці. Потім повторюємо процес з другої позиції у файлі і знайдений елемент обмінюємо зі другим елементному і так далі поки весь масив НЕ БУДЕ відсортований. Цей метод називається сортування вибором, оскільки він працює, циклічно вибираючи найменший з елементів, що залишилися, як показано на малюнку 1. При першому проході символ пропуску пішов на перше місце, обмінюючись з буквою 'П'. На другому проході елемент 'В' обмінюється з елементом 'Р' і так далі. p> Наступна програма дає повну реалізацію цього процесу. Для кожного i від 1 до N-1 , вона обмінює найменший елемент з a [ i .. N] з a [ i ]:
У міру просування покажчика i зліва направо через файл, елементи ліворуч від вказівника знаходяться вже у своїй кінцевій позиції (і їх більше вже не будуть чіпати), тому масив стає повністю відсортованим до того моменту, коли покажчик досягає правого краю.
Цей метод - один з найпростіших, і він працює дуже добре для невеликих файлів. Його В«внутрішній цикл В»складається з порівняння a [ i ] min ] (плюс код необхідний для збільшення j та перевірки на те, що він не перевищив N ), що навряд чи можна ще спростити.
Крім того, хоча сортування вибором є методом В«грубої силиВ», він має дуже важливе застосування: оскільки кожен елемент пересувається не більше ніж раз, то він дуже хороший для великих записів з маленькими ключами.
Сортування вставкою
Метод сортування вставкою, майже настільки ж простий, що і сортування вибором, але набагато більш гнучкий. Цей метод часто використовують при сортуванні карт: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже обробили (тим самим залишаючи їх отортірованнимі).
Розглянутий елемент вставляється в позицію допомогою пересування більшого елемента на одну позицію вправо і потім розміщенням меншого елемента в звільнилася позицію, як показано на малюнку 2. Так 'І' при третьому кроці менше всіх інших відсортованих елементів, тому ми В«топимоВ» його на початок масиву. 'М В»більше 'І' але менше за всіх інших, тому ми поміщаємо його між 'І' і 'П', і так далі.
Цей процес реалізований в наступній програмі. Для кожного i від 2 до N , підмасив a [1 .. i...
