загрузка...
загрузка...
На головну

Сортування за допомогою включення (сортування вставками)

Класи задач по обробці масивів

Перебір елементів масиву

1) Елементи масиву можна обробляти між окремими елементами рухаючись від початку масиву до його кінця (або в зворотному напрямку):
 for (int i = 0; i

2) Елементи масиву можна обробляти по два елементи, рухаючись по обидва боки масиву до його середини:
 int i = 0, j = n-1;
 while (i  <Обробка a [I] і a [j]>;
 i ++; j ++;}

3) Елементи масиву можна обробляти по два елементи, рухаючись від початку до кінця з кроком 1 (т. Е. Обробляються пари елементів a [0] і a [1], a [1] і a [2] і т. Д. )
 for (i = 0; i  <Обробка a [i] і a [i + 1]>

4) Елементи масиву можна обробляти по два елементи, рухаючись від початку до кінця з кроком 2 (т. Е. Обробляються пари елементів a [0] і a [1], a [2] і a [3] і т. Д. )
 i = 1;
 while (i  <Обробка a [i] і a [i + 1]>
 i: = i + 2;}

1) До завдань 1 класу відносяться завдання, в яких виконується однотипна обробка всіх або зазначених елементів масиву. Рішення таких завдань зводиться до встановлення того, як обробляється кожен елемент масиву або зазначені елементи, потім підбирається підходяща схема перебору, в яку вставляються оператори обробки елементів масиву. Прикладом такого завдання є знаходження середнього арифметичного елементів масиву.

2) До завдань 2 класу відносяться завдання, в яких змінюється порядок проходження елементів масиву. Обмін елементів всередині масиву виконується з використанням допоміжної змінної:

R = a [I]; a [I] = a [J]; a [J] = R; // обмін a [I] і a [J] елементів масиву.

3) До завдань 3 класу відносяться завдання, в яких виконується обробка декількох масивів або подмассивов одного масиву. Масиви можуть оброблятися за однією схемою - синхронна обробка або за різними схемами - асинхронна обробка масивів.

4) До завдань 4 класу відносяться завдання, в яких потрібно відшукати перший елемент масиву, що співпадає із заданим значенням - пошукові завдання в масиві.

3. Сортування масивів (Додатково: Іванова, с. 97-106).

Сортування - це процес перегрупування заданої множини об'єктів в деякому встановленому порядку.

Елементи масиву діляться на вже готову послідовність і вихідну. При кожному кроці, починаючи з I = 2, з вихідної послідовності витягується i-ий елемент і вставляється на потрібне місце готової послідовності, потім i збільшується на 1 і т. Д.

 готова  вихідна

У процесі пошуку потрібного місця здійснюються пересилання елементів більше обраного на одну позицію вправо, т. Е. Вибраний елемент порівнюють з черговим елементом відсортованої частини, починаючи з j: = i-1. Якщо обраний для більше a [i], то його включають в відсортовану частину, в іншому випадку a [j] зрушують на одну позицію, а обраний елемент порівнюють з наступним елементом відсортованої послідовності. Процес пошуку відповідного місця закінчується при двох різних умовах:

- Якщо знайдений елемент a [j]> a [i];

- Досягнутий лівий кінець готової послідовності.

int i, j, x;

for (i = 1; i

{

x = a [i];// Елемент, який будемо вставляти

j = i-1;

while (x = 0)// Пошук відповідного місця

{

a [j + 1] = a [j]; // Зрушення вправо

j--;

}

a [j + 1] = x; // Вставка елемента

}

3.2. Сортування методом простого вибору

Вибирається мінімальний елемент масиву і міняється місцями з першим елементом масиву. Потім процес повторюється з рештою елементами і т. Д.

   хв      

int i, min, n_min, j;

for (i = 0; i

{

min = a [i]; n_min = i;// Пошук хв-го

for (j = i + 1; j

if (a [j]

{

min = a [j];

n_min = j;

}

a [n_min] = a [i];// обмін

a [i] = min;

}

Наука адміністративного права «-- попередня | наступна --» Пошук в відсортованому масиві
загрузка...
© om.net.ua