Методом вставки

Принцип сортування: масив розподіляється на відсортовану та невідсортовану частини. На першому кроці за відсортовану частину (послідовність) приймається перший елемент масиву. Кожний наступний елемент з невідсортованої частини вставляємо в заздалегідь відсортовану послідовність так, щоб ця послідовність залишалась відсортованою. При цьому треба:

1. Знайти місце, куди потрібно вставити цей елемент.

2. Зсунути елементи, що стоять справа у відсортованій частині, на одну позицію вправо.

3. На звільнене місце поставити елемент, що аналізується (вставляється).

Два способи виконання цих дій: 1) кожний наступний елемент порівнюється з елементами у відсортованій частині, знаходиться місце вставки, всі наступні елементи зсуваються на одну позицію вправо і після цього вставляється елемент;
2) елемент, що вставляється, послідовно, зліва направо, порівнюється з кожним із елементів у відсортованій частині. Якщо потрібно, елемент у відсортованій частині одразу зсувається на одну позицію вправо. Як тільки знайдено потрібне місце вставки, елемент, що аналізується, вставляється на потрібну позицїю.

Метод вибору.

Ідея методу полягає в тому, що знаходиться максимальний елемент масиву і міняється місцями із останнім елементом (із номером N). Потім, максимум шукається серед елементів з першого до передостаннього і ставиться на N-1 місце, і так далі. Необхідно знайти N-1 максимум. Можна шукати не максимум, а мінімум і ставити його на перше, друге і так далі місце. Також застосовують модифікацію цього методу із одночасним пошуком максимуму і мінімуму. В цьому випадку кількість кроків зовнішнього циклу N div 2.

Обчислювальна складність сортування вибором - величина порядку N*N, що звичайно записують як О(N*N). Це пояснюється тим, що кількість порівнянь при пошуку першого максимуму становить N-1. Потім N-2, N-3, і так далі до 1, разом: N*(N-1)/2.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Приклад	\|	Шейкерне сортування.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.