13-Мавзу: Саралашнинг яхшиланган усуллари Шелл саралаши

• Режа:
• Шелл саралаши;
• Пирамидасимон саралаш;
• Тез саралаш (Quicksort).

• 13-Мавзу: Саралашнинг яхшиланган усуллари

Шелл саралаши (қисқариб борувчи қадамлар орқали саралаш)

• Алгоритм ғояси

• Изоҳ

• Шелл саралаш 1959 йилда Д.Шелл томонидан таклиф қилинган бўлиб, қўшиш орқали саралашнинг модификацияси ҳисобланади.

• Фараз қилайлик, a[0],a[1],a[2],…, a[n] бошланғич элементлар кетма-кетлиги бўлсин.
• 1-қадам. Бошланғич кетма-кетликнинг ҳар r1 ўринда жойлашган элементлари гуруҳланиб, ҳар бир гуруҳ алоҳида қўшиш усули орқали сараланади({a[0], a[r1], a[2*r1],…,}, {a[1], a[1+r1], a[1+2*r1],…,} в.ҳ.).
• 2-қадам. Ҳосил қилинган кетма-кетликда ҳар r2 ўринда жойлашган элементлар гуруҳланиб, ҳар бир гуруҳ алоҳида сараланади.
• ....................................................................................................................
• k-қадам. k-1 қадамда ҳосил бўлган кетма-кетлик оддий қўшиш усули орқали сараланади.

• Эслатма: r1>r2>…>rk-1>rk=1.

• Мисол:

• 1-қадам. r1=8, яъни (a[0], a[8]), (a[1], a[9]), ... , (a[7], a[15]).

12

8

14

6

4

9

1

8

13

5

11

3

18

3

10

9

12

8

14

6

4

9

1

8

13

5

11

3

18

3

10

9

• 2-қадам. r2=4, яъни (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).

12

5

11

3

4

3

1

8

13

8

14

6

18

9

10

9

• 3-қадам. r3=2, яъни (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]), (a[1], a[3], a[5], a[7], a[9], a[11], a[13], a[15]).

4

3

1

3

12

5

10

6

13

8

11

8

18

9

14

9

• 4-қадам. r4=1, яъни (a[0], a[2], … , a[15]).

1

3

4

3

11

5

11

6

12

8

13

8

14

9

18

9

1

3

3

4

5

6

8

8

9

9

10

11

12

13

14

18

• Изоҳ

• Гарчи таққослашлар сони бир мунча ортиб борсада, элементларни ўринлаштиришлар анча кам бўлади.
• Бу усул натижасида ҳар бир ўтишдан кейин саралашлар камайиб боради. Энг ёмон ҳолатда охирги ишни яккалик саралаш амалга оширади.

• Эслатма

• Шелл саралаш усулининг ягона тавсифи ҳар бир ўтишдан кейин қадамларни тўғри танлашдан иборат.

• Қадамларни танлаш:

• Р.Седжвик таклиф этган қадамлар:

• Усул самарадорлиги:

• Ўртача ҳолат - O(n7/6),
• Энг ёмон ҳолат - O(n4/3).

• Эслатма

• Седжвик усули орқали қадамлар танланаётганда, агар 3*inc[s]>n бўлса, у ҳолда энг катта қадам inc[s-1] бўлади.

Пирамидасимон саралаш

• Def.

• Пирамида деб баландлиги k бўлган шундай бинар дарахтга айтиладики, бунда
• k-1 дарахт идеал мувозанатланган;
• k-1 босқич тўла, k босқич эса чапдан ўнга томон тўлатилади.

• <а1,а2,…, аi ,…,an> пирамида  i учун (аi ≥ а2i ) (аi ≥ а2i +1 )

• Пирамидани массив кўринишида тасвирлаб олиш мақсадга мувофиқ бўлади.

• Алгоритм

• Бошланғич кетма-кетликдан пирамида шаклантирилади.
• Кириш ва тайёр кетма-кетлик битта массивда сақланади. Пирамида бошини оламиз ва тайёр кетма-кетликка жойлаштирамиз. Кейин қолган элементлар учун пирамидани тиклаймиз. Мазкур жараён барча элементлар тугагунча давом этилади.

• Пирамида қуришга мисол

• Қадам

• Қадам

• Қадам

• Қадам

• Қадам

• Чиқиш

• Пирамидани саралаш

• алмаштириш

• алмаштириш

• алмаштириш

• алмаштириш

• шакллантириш

• шакллантириш

• шакллантириш

• шакллантириш

• алмаштириш

• шакллантириш

• алмаштириш

• шакллантириш

• алмаштириш

• шакллантириш

• алмаштириш

• шакллантириш

• алмаштириш

• Самарадорлик: T(n)=O(nlogn)

• Тез саралаш (Quicksort)

• Алгоритм ғояси

• Бу усул алмаштириш усулидаги саралашга тегишли бўлиб унинг асосини калитларни танланган калитга нисбатан алмаштириш ташкил қилади.

• Мисол:

• Самарадорлик: T(n)=O(nlogn)

13-Мавзу бўйича назорат саволлари

• Shell саралаши
• Пирамида тушунчаси ва уни қуриш
• Пирамидасимон саралаш
• Тез саралаш тушунчаси