Припустимо, що у нас є масив, який необхідно відсортувати в порядку зростання чи спадання. Назвемо його Array. Окрім того, нам, для його сортування, необхідні змінні ітератори iter і jter, змінна для тимчасового зберігання елементу масиву x, змінна, яка буде містити індекс найменшого елементу масиву - kter і змінна, яка зберігає розмір масиву - N. В такому випадку, наш сортуючий код буде виглядати наступним чином:
for (iter=0; iter<N-1; iter++) /* зовнішній цикл */
{
kter = iter ; /* ініціалізовуємо kter в позицію iter */
x = Array [iter] ; /* і зберігаємо значення елементу
** оскільки ми повинні ініціалізувати ці значення */
for (jter=iter+1; jter<N; jter++) /* внурішній цикл */
{
if (Array[jter] < x) /* перевіряємо, чи значення елементу менше */
{/* якщо так, */
kter = jter ; /* зберігаємо індекс найменшого елементу */
x = Array[kter] ; /* зберігаємо його значення */
}
}
/* обмінюємо значення найменшоо елементу масиву з поточним */
/* поточний елемент (з позиції зовнішнього циклу)
** в позицію найменшого */
Array [kter] = Array [iter] ;
/* найменший елемент в позицію поточного */
Array [iter] = x ;
}
Знову ж таки, у нас два цикли - один вбудований у інший. Зовнішній цикл призначений для перебірки усіх елементів крім останнього, а внутрішній цикл - модифікований алгоритм лінійного пошуку з інваріантою, який призначений для визначення позиції вставки елементу. Останній елемент в масиві, автоматично залишається найбільшим. Виграш даного алгоритму від алгоритму сортування вставками, полягає у тому, що він не зсуває елементи, поки не знайде необхідне місце вставки, а просто обмінює значення в масиві, після знаходження відповідної позиції.
Проста програма, з використанням даного алгоритму може виглядати наступним чином:
#include <iostream>
using namespace std;
int main (int argc, char** argv)
{
/* масив даних */
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter, jter, kter ; /* бігунки-ітератори для перебору масиву */
/* змінна, в якій тимччасово зберігається значення елементу масива */
int x ;
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
for (iter=0; iter<N-1; iter++) /* зовнішній цикл */
{
kter = iter ; /* ініціалізовуємо kter в позицію iter */
x = Array [iter] ; /* і зберігаємо значення елементу
** оскільки ми повинні ініціалізувати ці значення */
for (jter=iter+1; jter<N; jter++) /* внурішній цикл */
{
if (Array[jter] < x) /* перевіряємо, чи значення елементу менше */
{/* якщо так */
kter = jter ; /* зберігаємо індекс найменшого елементу */
x = Array[kter] ; /* зберігаємо його значення */
}
}
/* обмінюємо значення найменшоо елементу масиву з поточним */
/* поточний елемент (з позиції зовнішнього циклу)
** в позицію найменшого */
Array [kter] = Array [iter] ;
/* найменший елемент в позицію поточного */
Array [iter] = x ;
}
/* виводимо масив на екран */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ;
}
Після виконання програми, ми отримаємо відсортований масив даних:
Для того, щоб відсортувати масив у порядку спадання нам необхідно всього-лиш вставити оператор '>' у позицію оператора '<', який знаходиться у тілі внутрішнього циклу оператора if (тобто вставити "(Array[jter] < x)" замість "(Array[jter] > x)")
#include <iostream>
using namespace std;
int main (int argc, char** argv)
{
/* масив даних */
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter, jter, kter ; /* бігунки-ітератори для перебору масиву */
/* змінна, в якій тимччасово зберігається значення елементу масива */
int x ;
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
for (iter=0; iter<N-1; iter++) /* зовнішній цикл */
{
kter = iter ; /* ініціалізовуємо kter в позицію iter */
x = Array [iter] ; /* і зберігаємо значення елементу
** оскільки ми повинні ініціалізувати ці значення */
for (jter=iter+1; jter<N; jter++) /* внурішній цикл */
{
if (Array[jter] > x) /* перевіряємо, чи значення елементу більше */
{/* якщо так */
kter = jter ; /* зберігаємо індекс найбільшого елементу */
x = Array[kter] ; /* зберігаємо його значення */
}
}
/* обмінюємо значення поточного елементу масиву з найбільшим */
/* поточний елемент (з позиції зовнішнього циклу)
** в позицію найбільшого */
Array [kter] = Array [iter] ;
/* найбільший елемент в позицію поточного */
Array [iter] = x ;
}
/* виводимо масив на екран */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ;
}
Результат виконання програми:
