Читать реферат по авиации и космонавтике: "Пошук сортування та поняття складності у програмуванні" Страница 1

(Назад) (Cкачать работу)

ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

1. Пошук за ключем у масиві

1.1. Лінійний пошук

Читачеві колись доводилося шукати своє прізвище в списках, надрукованих не в алфавітному порядку? Або уявіть собі словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом. Потрібне слово шукати там доведеться довго. Дуже довго. Звичайно, якщо воно випадково не потрапило в самісінький початок. А якщо в кінець чи середину? А пошук слова в "нормальному" словнику займає чомусь кілька секунд незалежно від його розташування там.

У цьому параграфі ми наведемо два алгоритми. Перший описує пошук "підряд" у невпорядкованій послідовності, другий – той пошук, до якого ми звикли, шукаючи слова в словниках. Замість слів розглянемо цілі значення елементів масиву. Тип значень може бути й іншим – головне, щоб їх можна було порівнювати.

Нехай елементи масиву A[1], A[2], … , A[n] та змінна key ("ключ") мають той самий тип T. Пошук за ключем полягає в пошуку номера i такого, що A[i]= key. За відсутності такого номера результатом будемо вважати 0. Нехай діють означення

const maxn = 1000;

type T = integer;

Indx = 1 .. maxn; (17.1)

ArT = array [Indx] of T;

Подамо розв'язання задачі функцією

function srcseq ( var A : ArT; n : Indx; key : T) : integer;

var i : integer;

begin

i := 0;

while ( i A[2], то поміняємо їхні значення місцями. Потім порівняємо A[2] і A[3] та за необхідності обміняємо їхні значення. В результаті A[3] має найбільше значення серед A[1], A[2], A[3]. Продовжимо такі порівняння та обміни до кінця масиву:

для всіх i від 1 до n-1 виконати

якщо A[i]>A[i+1], то

значення A[i] та A[i+1] обмінюються.

Якщо значення елементів розглядати як розміри бульбашок, то ці порівняння та обміни схожі на те, як більші бульбашки відтісняють менших униз і спливають нагору. Тому цей метод називається бульбашковим сортуванням. У результаті найбільша бульбашка стає верхньою, тобто останній елемент A[n] має найбільше значення. Наприклад, послідовність значень перетвориться на .

Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, на . Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1] A[i+1]

then swap (A[i], A[i+1])

end

Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n (n-1)/2 порівнянь. Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n елементів у такий спосіб прямо пропорційний n (n-1).

Задачі

2.* Якщо при черговому виконанні циклу із заголовком for i:=1 to k-1 do процедури Bubbles1 не було жодного обміну, то масив уже відсортовано. Тому подальші проходи масивом зайві. Переробити процедуру сортування так, щоб її виконання закінчувалося за відсортованого масиву.

3. Сортування вибором здійснюється так. Проглянемо елементи масиву від першого до останнього, визначимо елемент із найменшим значенням, та обміняємо це значення з першим. Потім так само виберемо найменше значення серед A[2]...A[n] і обміняємо його зі значенням A[2], потім виберемо наступне найменше та обміняємо з A[3] тощо. Написати процедуру сортування вибором.

4. Сортування

Похожие работы