• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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.

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

1. VII. Нахождение общего решения методом характеристик
2. Аналіз причин виникнення проблеми та обґрунтування її розв’язання програмним методом
3. Аналіз фінансової звітності методом коефіцієнтів
4. Банку за методом кумулятивного гепу, (тис. грн.)
5. Введення проводок методом копіювання
6. Виділення чистих культур за методом Коха
7. Визначення вмісту загального та білкового азоту за методом Кьєльдаля
8. Визначення загального вмісту органічних та мінеральних фосфатів ґрунту методом прокалювання Сендерса -Вільямса
9. Визначення конкурентоспроможності методом, заснованим на теорії ефективної конкуренції
10. Визначення мінеральних форм фосфору за методом Чанга-Джексона
11. Визначення нормативу обігових коштів економічним методом
12. Визначення показників механічних властивостей гірських порід методом статичного втискування штампа

Переглядів: 566