Обмінне сортування методом «бульбашки»
Порівнюються між собою кожні сусідні елементи масиву і, у разі потреби, міняються місцями, тобто «найлегший» елемент, якби, спливає на поверхню. Потім цей рівень не розглядається, а оглядається рівень з другого до останнього, і знов найлегший із елементів, які залишились, спливає, і т.д.
Блок-схема алгоритму: Текст програми:
 |
Begin
введення масиву 
SL : = N;
repeat
t : = 0;
for j : = 1 to SL-1 do
if a[j] > a[j+1] then
begin
_ buf : = a[j+1];
|
|
|
+ a[j+1] : = a[j];
a[j] : = buf;
змінюємо місцями сусідні елементи
t : = j;
end;
номер впорядкованого рівня
SL : = t;
Until t = 0;
Вивід упорядкованого масиву
Сортування за допомогою вибору
|
|
|
Сортування за допомогою вибору зводиться до наступного:
1) Знайти найменший (або найбільший) елемент. Запам'ятати його порядковий номер і поміняти місцями з першим елементом.
2) Знов продивитись елементи, починаючи, з другого до n і повторити вибір найменшого (найбільшого) елемента і, відповідно, змінити їх місцями, і т.д., поки не будуть впорядковані всі n елементів.
Блок-схема алгоритму: Текст програми:
 |
Begin
ввід масиву
for i : =1 to n-1 do
begin
початкове значення min
min : = a[i] ;
k : = i ; for j : = i + 1 to n do if min > a[j] then
|
|
|
begin
min : = a[j] ;
k : = j ;
+ _ end;
a[k] : = a[i] ;
a[i] : = min ;
end ;
|
|
|
вивід впорядкованого масиву
end.
Сортування злиттям
Злиття означує об'єднання двох або більше послідовностей (масивів) в одну впорядковану послідовність.
Розглянемо більш детально алгоритм двохшляхового злиття.
Дано два впорядкованих масиви xi , i=1, n, yj , j=1, m. Отримати масив Zk, k=1, n+m.
- Визначаємо найменший елемент xi і yj .
- Порівнюємо найменші елементи і обраний найменший елемент записуємо в Z, виключаючи його з відповідного масиву (наприклад xi ).
- Відшукуємо новий min у масиві xi і порівнюємо його зmin yj .
- Записуємо обраний min в Z і виключаємо його з відповідного масиву, і т.д. поки всі елементи xi й yj не будуть записані в Z.
Методи роботи з структурами «дерево»
Структура „дерево” є узагальненням лінійного списку. В списку кожен вузол має показник на другий вузол. В дереві, кожен вузол містить декілька показників на декілька вузлів. Якщо показника два (правий і лівий), таке дерево називається бінарним. Один із показників може бути рівним Nil. Якщо правий і лівий показник рівний Nil , такій вузол називається лист. Початкова точка дерева називається кореневим вузлом.
У кореневого вузла немає гілок які в нього входять, є тільки ті, що виходять з нього. Вершина, до якої виходить показник із другої вершини, називається потомком цієї вершини. Вершина, із якої виходить показник до другої вершини, називається предком.
Приклад структури «дерево».
В бінарному дереві часто притримуються згоди про те, що у всіх лівих вершинах повинні знаходитися менші за значенням елементи , а в правих – більші.
Основні операції над елементами дерева :
1. Занесення елементів в дерево.
2. Видалення елементів з дерева.
3. Обхід дерева.
Приклад опису структури «дерево»:
type tree = ^elem ; { показник на елемент дерева }
elem = record
info : integer; { інформаційне поле елемента дерева }
left : tree; { адресне поле елемента дерева – показник на лівого потомка }
right : tree; { адресне поле елемента дерева – показник на правого потомка }
end;
var beg : tree ; { показник на кореневий елемент (вузол) дерева }
Далі розглянемо основні операції зі структурою «дерево».
Дата добавления: 2018-04-04; просмотров: 605; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!