Сортування масиву методом вставки

Сортування масиву методом вибору

Нехай одновимірний масив складається з 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. Опишіть порядок виконання дій для сортування масивів методами вибору, обміну та вставки.