Сортування масиву методом вставки
Сортування масиву методом вибору
Нехай одновимірний масив складається з n елементів. Відсортуємо його за збільшенням значень елементів масиву. На першому проході (перегляді) в масиві на проміжку [1..n] знаходимо елемент з мінімальним значенням. Міняємо його місцями з першим елементом. На другому проході знаходимо мінімальний елемент на проміжку [2..n] та міняємо його місцями з другим елементом і продовжуємо до n-1 проходу. В результаті отримуємо відсортований (упорядкований) за зростанням масив.
Для сортування масиву за зменшенням значень його елементів необхідно на кожному кроці алгоритму знаходити елемент з максимальним значенням.
Приклад 1.Ввести з клавіатури одновимірний цілочисловий масив m, який складається з 10 елементів. Відсортувати його елементи за зростанням методом вибору. Вивести відсортований масив на екран.
Блок-схема програми:
Текст програми:
Program Sort_1;
Uses crt;
Const n=10;{кількість елементів масиву}
Var m: array[1..n] of integer;
min: integer;{мінімальний елемент}
nom: integer;{номер мінімального елемента}
i,j: integer;{параметри циклів}
Begin clrscr;
writeln('Введіть масив з ',n,' елементів:');
For i:=1 to n do read(m[i]); writeln;
For i:=1 to n-1 do{n-1переглядів масиву}
Begin{пошук мінімального елемента масиву на і-тому проході}
min:=m[i];
nom:=i;
For j:=i+1 to n do
If m[j]<min then
Begin min:=m[j];
nom:=j;
End;
m[nom]:=m[i];
m[i]:=min;
End;
writeln('Відсортований масив за зростанням:');
for i:=1 to n do
write(m[i],' ');
Readkey
End.
Результати виконання програми:
Введіть масив з 10 елементів:
2 5 4 8 7 9 5 6 4 3
Відсортований масив за зростанням:
2 3 4 4 5 5 6 7 8 9
2). Сортування масиву методом обміну
(метод пухирця)
Нехай одновимірний масив складається з n елементів. Зліва направо порівнюються два сусідні елементи, виявляється мінімальний і, якщо потрібно, елементи міняються місцями таким чином, щоб менший елемент стояв ліворуч. Потім беруться два наступні елементи і так до кінця масиву. Після одного проходу на останньому місці буде стояти максимальний елемент. Аналогічно виконується наступний прохід, але вже до n-1 елемента. Після n-1 проходу отримаємо відсортований масив за збільшенням значень його елементів.
Для сортування масиву за зменшенням значень його елементів необхідно на кожному кроці алгоритму знаходити елемент з максимальним значенням та переставляти його ліворуч.
Приклад 2.Ввести з клавіатури одновимірний цілочисловий масив m із 10-ти елементів. Відсортувати його елементи за збільшенням методом обміну. Вивести відсортований масив.
Блок-схема програми:
Текст програми:
Program Sort_3;
Uses crt;
Const n=10;{кількість елементів масиву}
Var m: array[1..n] of integer;
i,j: integer;{параметри циклів}
tmp: integer;{додаткова змінна}
Begin clrscr;
writeln('Введіть масив m[',n,']:');
for i:=1 to n do read(m[i]);{введення масиву}
for i:=1 to n-1 do{початок сортування}
for j:=i+1 to n do
if m[j]<m[i] then
begin{перестановка місцями елементів масиву}
tmp:=m[i];
m[i]:=m[j];
m[j]:=tmp
end; {кінець сортування}
writeln ('Відсортований масив:');
for i:=1 to n do write(m[i],' ');
Readkey
End.
Результати виконання програми:
Введіть масив m[10]:
7 5 2 1 6 8 4 3 9 11
Відсортований масив:
1 2 3 4 5 6 7 8 9 11
Сортування масиву методом вставки
Нехай одновимірний масив m складається з nелементів. Масив ділиться на дві частини: відсортовану і не відсортовану. Елементи з не відсортованої частини по черзі вибираються і вставляються у відсортовану частину таким чином, щоб не порушити в ній впорядкованість елементів. На початку алгоритму в якості відсортованої частини беруть перший елемент, а в якості не відсортованої – всі інші. Таким чином алгоритм буде складатись з n-1 кроків, на кожному з яких виконуються такі дії:
· збереження i-го не відсортованого елемента у додатковій змінній;
· пошук позиції j у відсортованій частині масиву, в якій присутність взятого елемента не порушить упорядкованості масиву;
· зсув елементів масиву від і-го до j-го праворуч, щоб звільнити знайдену позицію вставки;
· вставка взятого елемента в j-ту позицію.
Приклад 3.Ввести з клавіатури одновимірний цілочисловий масив m із 10 елементів. Відсортувати його елементи за збільшенням методом вставки. Вивести відсортований масив.
Блок-схема програми:
Текст програми:
Program Sort_5;
Uses crt;
Const n=10;{кількість елементів масиву}
Var m:array[1..n] of integer;
i,j,k:integer;{параметри циклів}
tmp: integer;{додаткова змінна}
Begin
Clrscr;
writeln('Введіть масив m[',n,']:');
for i:=1 to n do read(m[i]);
for i:=2 to n do
Begin
tmp:=m[i];
j:=1;
while tmp>m[j] do j:=j+1;
for k:=i-1 downto j do m[k+1]:=m[k];
m[j]:=tmp;
End;
writeln('Відсортований масив:');
for i:=1 to n do write(m[i],' '); writeln;
Readkey
End.
Результати виконання програми:
Введіть масив m[10]:
5 3 8 9 7 14 4 2 6 1
Відсортований масив:
1 2 3 4 5 6 7 8 9 14
Приклад 4.Ввести з клавіатури прямокутну матрицю. Відсортувати всі непарні рядки за збільшенням методом вставки. Вивести відсортовану матрицю.
Блок-схема програми:
Текст програми:
Program Sort_6;
Uses crt;
Const n = 4; {кількість рядків матриці}
m = 5; {кількість стовпців матриці}
Var a: array[1..n,1..m] of integer;
i,j,k: integer; {параметри циклів}
c,t: integer; {додаткові змінні}
Begin
clrscr;
writeln('Введiть матрицю ',n,’x’,m,’:’); writeln;
for i := 1 to n do
for j := 1 to m do
read(a[i,j]);
for i := 1 to n do
if odd(i) then
for j := 2 to m do
begin
t := a[i,j];
c := 1;
while t > a[i,c] do
c:=c+1;
for k := j-1 downto c do
a[i,k+1] := a[i,k];
a[i,c] := t;
end;
writeln('Вiдсортована матриця:');
for i := 1 to n do
begin
for j := 1 to m do
write(a[i,j],' ');
writeln;
end;
readkey
End.
Результати виконання програми:
Введіть матрицю 5х4
3 1 9 6 8
6 5 9 0 1
5 8 9 1 5
8 9 4 7 1
Відсортована матриця:
1 3 6 8 9
6 5 9 0 1
1 5 5 8 9
8 9 4 7 1
Питання для самоконтролю
1. Що таке масив?
2. Чим відрізняються поняття «розмір» та «розмірність» масиву?
3. Яку матрицю називають квадратною?
4. Що таке сортування масивів?
5. Які методи сортування масивів є найбільш поширеними у використанні?
6. Опишіть порядок виконання дій для сортування масивів методами вибору, обміну та вставки.