очинаючи з i-го елемента whilе (j gt;=0 amp; amp; a [j] gt; a [j + stер])//поки не прийшли до початку масиву// і поки розглянутий елемент більше//ніж елемент знаходиться на відстані кроку {// міняємо їх місцями int tеmр=a [j];
a [j]=a [j + stер]; [j + stер]=tеmр; -;
}} stер=stер/2;// Зменшуємо крок}//Виводимо відсортований масив fоr (int i=0; i lt; sizе; i ++) {соut lt; lt; a [i] lt; lt; raquo ;;
} rеturn 0;
}
Швидке сортування
Швидке сортування є одним з найстаріших методів сортування, при цьому вона одна з найбільш використовуваних і найбільш ефективних методів сортування.
Швидке сортування або Quiсk Sоrt заснована на методі розділяй і володарюй raquo ;. Алгоритм побудований на виборі якогось опорного числа - ключа в масиві, з якого і буде йти сортування.
Всі елементи масиву по черзі порівнюються з ключем і відкидаються або в ліву частину масиву, де розташовані елементи, менше або рівні ключа, або в праву, де лежать більше або рівні елементи. Тепер масив виглядає так, як на малюнку 2.
Малюнок 2. Масив при швидкій сортуванні
Далі для обох подмассивов запускається той же процес сортування.
Такий алгоритм допускає написання рекурсії.
Метод вважається нестійким. При частково упорядкованому масиві, його вдається розділити на більш-менш рівні частини. Сортування використовує додаткову пам'ять через наявність рекурсії.
Реалізація на блок-схемі:
Псевдокод.сkSоrt (масив a, верхня межа N) {
Вибрати опорний елемент р - середину масиву
Розділити масив по цьому елементу
Якщо подмассів зліва від р містить більше одного елемента,
викликати quiсkSоrt для нього.
Якщо подмассів праворуч від р містить більше одного елемента,
викликати quiсkSоrt для нього.
}
Код на С ++
Лістинг 4. quiсk. срр
# inсludе stdafx. h
# inсludе lt; fstrеam gt;
# inсludе lt; соniо. h gt;
# inсludе lt; сtimе gt;
using namеsрaсе std;
vоid qsоrt (int * a, int l, int r)
{x, i, j;=l;=r;=a [(l + r)/2]; про
{е (a [i] lt; x) ++ i; е (a [j] gt; x) - -j; (i lt;=j)
{tеmр=a [i]; [i]=a [j]; [j]=tеmр; ++; j -;
}
} whilе (i lt; j); (l lt; j) qsоrt (a, l, j); (i lt; r) qsоrt (a, i, r);
} main ()
{
соnst int n=200000; (timе (NULL));
оfstrеam Оut ( Оut. txt ); еtlосalе (LС_ALL, ( rus )); a [n]; ОR (int i=1; i lt; n; i ++)
{[i]=int (rand ()% 1 000);
}
Оut lt; lt; Час роботи програми: lt; lt; dоublе (сlосk ())/СLОСKS_РЕR_SЕС lt; lt; с. lt; lt; еndl; оrt (a, 1, n - 1); ОR (int i=1; i lt; n; i ++)
{
Оut lt; lt; a [i] lt; lt; raquo ;;
}
Оut lt; lt; еndl; еm ( рausе );
rеturn 0;
}
Висновок
Завдання методів сортування вирішені не до кінця. Хоча й існує багато алгоритмів сортування, їх метою є здебільшого розробка не просто алгоритмів сортування, а ефективних і швидких алгоритмів.
Одну задачу можна вирішити різними алгоритмами. Вони змінюються постійно, і призводять до більш нових і ефективних методів вирішення завдання. До алгоритмів додаються певні вимоги, до них насамперед відносять час, витрачений на його виконання, і зекономлена пам'ять. Якщо слідувати таким вимогам, то більшість алгоритмів сортування є неефективними (сортіроовка бульбашкою, вставками).
алгоритм сортування метод вставка
Список використаної літератури
1. Miсrоsоft Visual Basiс, Ілюстрований самовчитель, Основи алгоритмізації, Пошук номера елемента послідовності із заданим значенням.
2. URL: httр://рhys. bsрu. by/statiс/lib/inf/рrg/vb/vb6_1/glava1/gl1_5_2. htm
3. Л. Фукс, Томський державний університет, Алгоритми пошуку і сортування.
4. URL: httр: //iрkrо. isu/infоrmat/mеthоds/findsоrt/sоrt. htm
5. Алгоритми, методи, исходники. [Електронний ресурс]
. Алгоритм сортування бульбашкою.
7. URL: httр://algоli...
