II.Сортування за допомогою прямого вибору

Тема: сортування масивів

 

Питання, що розглядаються в лекції:

а) сортування за допомогою вставки;

б) сортування за допомогою прямого вибору;

в) сортування за допомогою обміну.

 

Сортування масивів

 

Методи сортування повинні економно використовувати доступну пам'ять. Це означає, що пересування, що приводять елементи в порядок, повинні, якщо можливо, виконуватись на тому ж місці, тобто без використаня додаткових масивів.

Як міру ефективності для алгоритмів сортування візьмемо кількість необхідних порівнянь елементів і кількість присвоювань елементів у процесі виконання алгоритму. Точна оцінка деяких алгоритмів сортування - складна математична задача, тому будуть надані тільки кінцеві результати оцінки.

Кількість порівнянь K_c=C

присвоєнь K_п=R.

 

Методи сортування "на тому ж місці" можна розбити у відповідності до визначаючих їх принципів на три основні групи:

1. Сортування за допомогою вставки (by Insertion) або за допомогою включення.

2. Сортування за допомогою вибору (by Selection) або за допомогою виділення.

3. Сортування за допомогою обміну (by Exchange) або бульбашкове.

Кожна група має прямий метод (самий простий) і покращені(ускладнені) методи сортування. Прямі методи працюють значно повільніше, ніж покращені і в практичних задачах майже не застосовуються. Але вони мають свої переваги:

1. Вони зручні для пояснення характерних рис, основних принципів методу.

2. Алгоритми цих методів легко зрозуміти і вони невеликі за розміром.

Покращені методи складніші і тому при достатньо малих розмірах масивів і в деяких особливих ситуаціях прямі методи працюють швидше.

 

Прямі методи сортування.

 

I.Сортування за допомогою вставки.

Принцип сортування: масив розподіляється на відсортовану та невідсортовану частини. На першому кроці за відсортовану частину(послідовність) приймається перший елемент масиву. Кожний наступний елемент з невідсортованої частини вставляємо в заздалегідь відсортовану послідовність так, щоб ця послідовність залишалась відсортованою.

При цьому треба:

1. Знайти місце, куди потрібно вставити цей елемент.

2. Зсунути елементи,що стоять справа у відсортованій частині, на одну позицію вправо.

3. На звільнене місце поставити елементБ що аналізується(вставляється).

 

Два способи виконання цих дій:

 

1) кожний наступний елемент порівнюється з елементами у відсортованій частині, знаходиться місце вставки, всі наступні елементи зсуваються на одну позицію вправо і після цього вставляється елемент;

 

2) елемент, що вставляється, послідовно, зліва направо, порівнюється з кожним із елементів у відсортованій частині. Якщо потрібно, елемент у відсортованій частині одразу зміщується на одну позицію вправо. Як тільки знайдено потрібне місце вставки, елемент, що аналізується, вставляється на потрібну позицїю.

 

Загальна схема.

відсортована

частина

2 9 7 3 5 8...

I=2

Крок 1

 

 

2 9 7 3 5 8...

i=3

Крок 2

 

вставка

i=4

2 9 7 3 5 8...

Крок 3

 

Зсув

 

вставка i=5

Крок 4

 

зсув

 

i т.д. і=2,n

 

Ідея алгоритму:

а) запам'ятати елемент, що аналізується B:=A[i] (з індексом i);

б) знайти місце вставки, B>A[j]- по зростанню (позиція з індексом j);

в) зсунути елементи у відсортованій частині, починаючи з позиції вставки.

 

 

відсортована

частина

 

 

а

B

в

б

 

 

а) вставка зліва, пошук зліва (реалізація способу (1))

 

|inserton_1

1 n

A є R

B є R

i,j,k,n є N

введення n,A

(i=2,n)

B:=A[i]

j:=1

(B³A[j])U(i>j) - пошук місця вставки

j:=j+1 - починаючи з першого елементу

-1

(k=i-1,j)

A[k+1]:=A[k] - зсув елементів

A[j]:=B -власно вставка

виведення A

|end

 

б)вставка зліва, пошук справа, без бар'єру (реалізація способу 2)

 

Елемент,що вставляється, порівнюється з кожним наступним елементом у відсортованій частині, починаючи справа від її межі. При невиконанні умови вставки кожний черговий елемент відразу ж пересувається. Крім того, необхідно забезпечити перевірку на межу(початок) масиву при русі справа наліво, тобто j>1. Метод називається методом вставки "без бар'єру".

 

Відсортована частина i=3

 

 

(5>3)(7>3)

 

B

 

|inserton_2

1 n

A є R

B є R

i,j,n є N

введення n,A

(i=2,n)

B:=A[і]

j:=і

(j>1)∩(A[j-1]>B)

A[j]:=A[j-1]

j:=j-1

 

A[j]:=B

 

Виведення: A

|end

в) вставка "з бар'єром" (реалізація способу(2))

 

Елемент, що вставляється, ставиться у 0-ву позицію, тобто перед відсортованою частиною, пошук місця вставки здійснюється зліва направо. Межу масиву відслідковувати не треба, але слід передбачити додатковий(нульовий) елемент масиву.

|inserton_3

0 n

A є R

i,j,n є N

введення n,A

(i=2,n)

A[0]:=A[і]

j:=і

A[0]<A[j-1]

A[j]:=A[j-1]

j:=j-1

 

A[j]:=A[0]

виведення A

|end

Зауважимо, що сам нульовий елемент не пересувається, він тільки заноситься на передчасно звільнене місце вставки.

 

II.Сортування за допомогою прямого вибору

 

Принцип сортування: масив також поділяється на відсортовану та невідсортовану частини. На першому кроці весь масив - невідсортований. У невідсортованій частині знаходиться мінімальний (або максимальний) елемент та міняється місцями з першим елементом невідсортованої частини. Межа відсортованої частини зсувається вправо на 1. Процедура виконується ціклчно, n-1 раз (останній елемент пересувати не треба).

 

2 7 5 1 8 3 10

Крок 1

 

 

1 7 5 2 8 3 10

Крок 2

 

 

1 2 5 7 8 3 10

Крок 3

 

 

1 2 3 7 8 5 10

Крок 4

 

 

1 2 3 5 8 7 10

Крок 5

 

 

1 2 3 5 7 8 10

Крок 6

 

А) основний варіант.

 

|selection

1 n

A є R

min є R

s,i,j,n є N

введення n,A

(s=1,n-1)

min:=A[s]

j:=s

(i=s+1,n)

(A[i]<min)

min:=A[i] пошук мінімального елементу,

j:=i запам’ятовуванняйого індексу.

 

 

A[j]:=A[s]

A[s]:=min

виведення A

|end

 

б) Як вариант можна запропонувати наступний алгоритм, який на вигляд є простішим, але мізтить значно більшу кількість пересуваннь.

 

 

|selection

1 n

A є R

min є R

s,i,j,n є N

введення n,A

(s=1,n-1)

(i=s+1,n)

(A[i]<min)

min:=A[i]

A[i]:=A[s]

A[s}:=min

 

 

виведення A

|end

 

 

III. Сортування за допомогою прямого обміну(бульбашкове)

 

Принцип сортування: зліва направо почергово іде порівняння двох сусідніх елементів. Якщо вони не впорядковані між собою, то міняються місцями. В базовому алгоритмі проходження масиву та чергове впорядкування повторюються n-1 раз.

 

1.

Максимальний елемент одразу ж опиняється в кінці масиву,тобто на наступному

5 3 4 9 1 7 6

кроці ми можемо анализувати на один елемент менше;

f=true фіксація наявності пересувань;

k=6- місце останнього пересування;

3,5

4,5

9,1

7,9

6,9

 

2.

3 4 5 1 7 6 9

f=true

k=5

1,5

6,7

3.

3 4 1 5 6 7 9

f=true

k=2

1,4

4.

3 1 4 5 6 7 9

f=true

k=1

1,3

5.

1 3 4 5 6 7 9

f=false

 

3 1 4 5 6 7 9

6.

f=false

 

а) алгоритм базового методу

 

|exchenge_1

1 n

A є R

B є R

k,i,n є N

введення n,A

-1

(k=n-1,1)

 

(i=1,k)

(A[i]>A[i+1])

B:=A[i]

A[i]:=A[i+1]

A[i+1]:=B

 

 

виведення A

|end

б) модіфікований алгоритм бульбашкового сортування

Процес пересування повторюється циклічно по всьому масиву(за вийнятком останніх елементів), поки всі елементи не будуть впорядковані. Таким чином, на кожному кроці слід фіксувати наявність пересувань. Їх відсутність є оизнакою кінця сортування (тобто обов'язкова наявність "холостого проходження" - коли ні жодне пересування не буде виконано). Для фіксації наявності пересувань використовують логічну змінну f, що, наприклад, приймає значення true якщо є пересування і false - в іншому випадку.

|exchenge_2

 

A є R

F є R

B є B

k,i,n є N

введення n,A

F:=true

k:=n-1

 

(F=true)

F:=false

(i=1,k)

(A[i]>A[i+1])

B:=A[i]

A[i]:=A[i+1]

A[i+1]:=B

F:=true

k:=k-1

виведення A

|end

в) Якщо фіксувати не тільки наявність пересувань, але і місце останього пересування, можна істотньо покращати алгоритм. Кінець сортування досягається тоді, коли останнє пересування було виконане у першій позиції (k=1 - місце останнього пересування), тобто мінімальний елемент потрапив на своє місце (зникає одне холосте проходження).

|exchenge_3

1 n

A є R

B є R

k,i,n,r є N

введення n,A

r:=n-1

(r>1)

k:=1

(i=1,r)

(A[i]>A[i+1])

B:=A[i]

A[i]:=A[i+1]

A[i+1]:=B

k:=і

r:=k-1

виведення A

|end

г) шейкерне пересування

 

Почергово виконується сортування зліва направо (при цьому правий елемент чи група елементів займає своє місце) і справа наліво (своє місце займає лівий елемент чи їх група). Місця(індекси елементів) останніх пересувань в обох випадках фіксуються і використовуються як межі зліва і справа для подальшого сортування (невідсортованої частини) масиву. Сортування продовжується до тих пір, поки ліва і права межі не співпадуть.

 

 

L=1 сортування зліва направо R=n L,R – відповідно ліва та права

1. межа невідсортованої частини

 

 

3,9

2,9

5,9

1,9

6,9

	R=k

k- номер останнього переміщення, k=6 =6

 

L=1 R=6

2. сортування справа наліво

 

1,5

1,2

1,3

1,4

	L=k+1

k=1 =2

 

 

L=2 R=6

1 4 3 2 5 6 9

3.

 

 

3,4

2,4

	R=k

k=3 =3

 

 

L=2 R=3

1 3 2 4 5 6 9

4.

 

 

2,3

 

	L=k+1

k=2 =3 L=R- кінець сортування

 

 

|exchenge_4

 

A є R

B є R

k,i,n,L,R є N

введення A,n

L:=1; R:=n; k:=1

(R>L)

(i=L,R-1)

(A[i]>A[i+1])

B:=A[i] сортування зліва

A[i]:=A[i+1] зміщення правої межі

A[i+1]:=B

k:=i

R:=k

-1

(i=R-1,L)

(A[i]>A[i+1])

B:=A[i] сортування справа

A[i]:=A[i+1] зміщення лівої межі

A[i+1]:=B

k:=i

L:=k+1

виведення A

|end