= i + 1 to n - 1 doA [i]
Сортування Шелла:
Сортування Шелла - алгоритм сортування <# "157" src = "doc_zip10.jpg"/>
Рис. 2.5. Приклад сортування методом Шелла
Псевдокод даного алгоритму.
Алгоритм ShellSort (А [0 .. n - 1])
// Сортування масиву підрахунком Шелла
// Вхідні дані: Масив А [0 .. n - 1] упорядковуваних значень
// Вихідні дані: Масив А [0 .. n - 1] елементів відсортованих
// в неубутною порядку
d = n
while d> 1
d = d/2 = 0 (j = i + d) А [j]
обмін А [i] і А [j]
i + +
Виклик методу сортування бульбашкою або сортування вставками або сортування вибором.
Послідовний пошук:
Цей алгоритм просто по черзі порівнює елементи заданого списку з ключем пошуку доти, поки не буде знайдений елемент з вказаним значенням ключа (успішний пошук) або весь список буде перевірений, але необхідний елемент не знайдений (невдалий пошук). Найчастіше застосовується простий додатковий прийом: якщо додати ключ пошуку в кінець списку, то пошук обов'язково буде успішним, отже, можна прибрати перевірку завершення списку в кожній ітерації алгоритму. Далі наведено псевдокод такий поліпшеної версії; передбачається, що вхідні дані мають вигляд масиву. p align="justify"> Алгоритм SequentialSearch2 (А [0 .. n], К)
// Алгоритм реалізує послідовний пошук з використанням
// ключа пошуку в якості обмежувача
// Вхідні дані: Масив А з п елементів і ключ пошуку К
// Вихідні дані: Позиція першого елемента масиву A [0 .. n - 1],
// значення якого збігається з К; якщо елемент не знайдений,
// повертається значення -1
А [п] = К
i = 0
while А [i] K = i + 1i <Пi
return -1
Якщо вихідний список відсортований, можна скористатися ще одним удосконаленням: пошук в такому списку можна припиняти, як тільки зустрінеться елемент, не менший ключа пошуку.
Бінарний пошук:
Бінарний пошук являє собою найвищою мірою ефективний алгоритм для пошуку в відсортованому масиві. Він працює шляхом порівняння шуканого ключа К із середнім елементом масиву А [m]. Якщо вони рівні, алгоритм припиняє роботу. В іншому випадку та ж операція рекурсивно повторюється для першої половини масиву, якщо К <А [m], і для другої, якщо К> А [m]. p align="justify"> Як приклад знайдемо ключ К = 70, застосовуючи алгоритм бінарного пошуку до масиву. Приклад показаний на малюнку 2.6
алгоритм сортування програмування пошук
В
Рис. 2.6. Приклад бінарного пошуку
Хоча ясно, що бінарний пошук заснований н...
