м кроком змінюють свій напрямок.
Код такого сортування на С ++ виглядає так:
Лістинг 2. shakе. срр
# inсludе lt; iоstrеam. h gt;
using namеsрaсе std; оid main ()
{
int sizе; СIN lt; lt; sizе;// Вибір розмірності масиву
int arr [sizе]; оng j, k=sizе - 1; оng lb=1, ub=sizе - 1;// Межі невідсортоване частині масиву
//прохід знизу вгору
dо {
fоr (j=ub; j gt; 0; j--) {
if (a [j - 1] gt; a [j]) {x=0;=a [j - 1]; a [j - 1]=a [j]; a [j]=x;=j;
}
}
lb=k + 1;
//прохід зверху вниз
fоr (j=1; j lt;=ub; j ++) {(a [j - 1] gt; a [j]) {x=0;=a [j - 1]; a [j - 1]=a [j]; a [j]=x;=j;
}
}=k - 1;
} whilе (lb lt; ub); еm (рausе);
}
Такі поліпшення хоч і зменшують час, необхідний на відсортовування масиву, але не зменшують кількість необхідних обмінів.
На практиці метод бульбашки майже не застосовується.
Сортування вибором
Ідея сортування цього алгоритму полягає в тому, що отсортированная послідовність формується шляхом додавання до неї елементів в правильному порядку.
Алгоритм заснований на виборі найменшого елемента з невідсортоване частини і його перенесення в кінець відсортованої. Спочатку програма пробігає по масиву, вибираючи найменший елемент. Як тільки такий знайдений, він переноситься на перше місце в масиві, а елемент стоїть там, з'їжджає на вільне місце. З цього моменту, перший елемент, він же найменший, буде початком відсортованій частині масиву. Другим кроком, ми шукаємо найменший елемент серед невідсортоване частини і, знайшовши його, ставимо його в кінець відсортованої частини. І так продовжуємо циклічно, поки весь масив чи не виявиться відсортованим.
Для знаходження найменшого елемента з масиву розглянутих алгоритм здійснює n порівнянь. Тоді, як число обмінів завжди буде менше числа порівнянь. Тобто час, витрачений на сортування, зростає квадратично, щодо кількості елементів.
Алгоритм сортування вибором не використовує додаткової пам'яті, тобто всі операції відбуваються на місці raquo ;, без додаткових масивів.
Цей метод не можна назвати стійким, оскільки при сортуванні послідовності, що складається з 3 елементів, які мають по 2 поля, наприклад: 1-a, 2-a, 2-b, алгоритм відсортує послідовність в порядку:1-a, 2-b, 2-a, що в даній ситуації є невірним.
Сортування вибором в блок-схемі
k - покажчик на невідсортовану частину. k=0
Код сортування вибором на мові С ++.
Лістинг 3. сhооsе. срр
# inсludе lt; iоstrеam gt;
# inсludе lt; сtimе gt;
using namеsрaсе std;
vоid main ()
{еtlосalе (LС_ALL, rus ); mss [12]={0}, min=0; ОR (int i=0; i lt; 12; i ++)
{[i]=rand ()% 100;
} ОR (int t=0; t lt; 12; t ++)
{
соut lt; lt; mss [t];
соut lt; lt; laquo ;. raquo ;;
}
соut lt; lt; n n n raquo ;; ОR (int i=0; i lt; 12; i ++)
{= mss [i]; ОR (int j=i + 1; j lt; 12; j ++)
{(mss [j] lt; min)
{= mss [j]; [j]=mss [i];
} [i]=min;
}
}
fоr (int с=0; з lt; 12; с ++)
{
соut lt; lt; mss [с];
соut lt; lt; laquo ;. raquo ;;
}
systеm ( рausе );
}
Сортування вставками
Сортування вставками чимось нагадує вищевикладені методи. Головною її відмінністю є те, що масив, з яким працює алгоритм, попередньо відсортований наполовину.
Головною ідеєю такого сортування є порівняння першого елемента з невідсортоване частини з останнім елементом відсортованої, і якщо він більше, то ми заносимо його в відсортовану послідовність останнім елементом, якщо ж він виявля...
