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

Пошук в відсортованому масиві

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

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

94
           

for (int i = 1; i

for (int j = n-1; j> = i; j--)

if (a [j]

{

int r = a [j];

a [j] = a [j-1];

a [j-1] = r;}

}

У відсортованому масиві використовується дихотомический (бінарний) пошук. При послідовному пошуку потрібно в середньому n / 2 порівнянь, де n - кількість елементів в масиві. При дихотомічному пошуку потрібно не більше m порівнянь, якщо n- m-ий степінь 2, якщо n не є ступенем 2, то n m.

Масив ділиться навпіл S: = (L + R) / 2 + 1 і визначається в якій частині масиву знаходиться потрібний елемент Х. Так як масив впорядкований, то, якщо a [S]

L S R

int b;

cout << "\ nB =?"; cin >> b;

int l = 0, r = n-1, s;

do

{

s = (l + r) / 2; // Середній елемент

if (a [s]

else r = s;// Перенести праву кордон

} While (l! = R);

if (a [l] == b) return l;

else return -1;

...

Сортування за допомогою включення (сортування вставками) «-- попередня | наступна --» Тема 1. Поняття, предмет, метод і система трудового права
загрузка...
© om.net.ua