Сұрыптау «көпіршіктің»: бағдарламалау сұрыптау әдістері

көпіршікті сұрыптау ғана Сонымен қатар, ол ұйымдастыру ең баяу жолдарын тізімін жабады, ең жылдам әдісі болып саналады емес. Алайда, ол өз артықшылықтары бар. көпіршігі сұрыптау Осылайша, әдісі - ең сіз белгілі ретпен элементтерді ұйымдастыруға келсе, проблеманы табиғи және логикалық шешім екенін де. қолмен қарапайым адам, мысалы, ол оларды пайдалануға болады - жай ғана түйсігі.

Осындай ерекше атауды қайда жасады?

Әдісі атауы суда ауа көпіршіктері теңеуді қолданып, келді. Бұл метафора ғой. Сонымен қатар аз, ауа көпіршіктері жоғары көтеріледі - олардың тығыздығы (бұл жағдайда - су) Сұйықтың артық, өйткені, және әрбір жиым элементі, ол соғұрлым аз мән, тізімі сандар жоғарғы көбірек біртіндеп жолы болып табылады.

Алгоритмнің сипаттамасы

төмендегідей көпіршікті сұрыптау жүзеге асырылады:

• Бірінші өтеді: алаптың сандардың элементтері екі жұп қабылдаған, сондай-ақ салыстырылады. екі адам командасы бірінші құнының кейбір элементтері екінші артық болса, бағдарлама олардың алмасу орындар етеді;
• Демек, ең көп саны түсірмеу алаптың соңы. барлық басқа элементтер, олар ретінде ретсіз түрде, қалады, және одан сұрыптау талап жатқанда;
• және, демек, екінші пас талап: ол (қазірдің өзінде сипатталған) алдыңғы ұқсас жасаған және салыстыру саны бар - минус бір;
• Бірінші қарағанда, бір секунд кем, және екі өту санының үш салыстырулар. Тағыда басқа;
• әрбір өту (алапта барлық мәндерді, атап айтқанда, бірқатар) минус (өту саны) салыстыру бар екенін қорытындылау.

бағдарламасы Тіпті қысқа алгоритмі ретінде жазуға болады:

• кез келген екі санының табылды сондай-ақ ұзақ, олардың екінші, бірінші артық болуы міндетті ретінде сандар массив тексеріледі;
• дұрыс Жиым бағдарламалық қамтамасыз своптар әрбір басқа элементтер қатысты орналасқан.

сипатталған алгоритм негізінде псевдокод

төмендегідей қарапайым іске асыру жүзеге асырылады:

Sortirovka_Puzirkom тәртібі;

басы

konechii_index үшін nachalnii_index жылғы J үшін цикл;

nachalnii_index Мен konechii_index-1 үшін цикл;

Массив егер [і]> [Мен Массив + , содан кейін 1] (екінші-ден артық бірінші элементі):

(Орын мәндерді өзгертіңіз);

соңы

Әрине, бұл қарапайымдылығы тек жағдайын нашарлататын: алгоритм қарапайым, көп, ол барлық кемшіліктерді көрінеді. уақыт Инвестициялық қатынасы (: тырысамыз үшін уақыт мөлшері шағын, бірақ шын мәнінде бағдарламашы әрбір екінші немесе тіпті миллисекунд санау көрінуі мүмкін, мұнда салыстырмалық жеткізіледі), тіпті шағын алаптың үшін тым үлкен болып табылады.

Ол жақсы іске асыру болды. Мысалы, назарға алап жерлерде құндылықтарды алмасу отырып:

Sortirovka_Puzirkom тәртібі;

басы

sortirovka = шынайы;

sortirovka = шынайы дейін цикл;

sortirovka = жалған;

nachalnii_index Мен konechii_index-1 үшін цикл;

Массив егер [і]> [Мен Массив + , содан кейін 1] (екінші-ден артық бірінші элементі):

(Элементтері орындарын өзгертуге);

sortirovka = шынайы; (Айырбастау жасалды деп анықталған).

Соңы.

шектеулер

Негізгі кемшілігі - процесінің ұзақтығы. Қанша уақыт адресінен жүзеге асырылады алгоритм сұрыптау көпіршік?

Орындау уақыты алапта шаршы сандардың санына есептеледі - оның түпкі нәтижесі пропорционалды.

ол элементтерді минус бір мәні бар ең нашар жағдайда алап ретінде бірнеше рет өтті, онда. соңында бір ғана салыстыруға ештеңе жоқ элементі, және жиым пайдасыз іс-қимыл болып арқылы соңғы пас бар, өйткені бұл орын.

Сонымен қатар, ол тек шағын мөлшерін массивтерді, атайды қарапайым айырбастау, сұрыптау тиімді әдісі. процесінің көмегімен үлкен мөлшерде деректердің жұмыс істемейді: нәтиже бағдарламасының қате немесе сәтсіздік, не болады.

абырой

көпіршікті сұрыптау түсіну өте оңай. бірінші кезекте, оның массив жүйелеу элементтерін зерттеу техникалық жоғары оқу орындарының оқу жоспарлары. әдісі дұрыс тәртіппен Delphi бағдарламалау тілінде (L (Delphi), және C / C ++ (C / C плюс плюс), орналасқан жері алгоритмі керемет қарапайым құндылықтар екі жүзеге асыру және оңай Паскаль (Паскаль). Bubble сұрыптау бастаушы үшін өте ыңғайлы болып табылады.

Байланысты алгоритм кемшіліктер үшін сабақтан тыс мақсаттарда пайдаланылмайды.

Visual сұрыптау принципі

Жиым 8 22 4 74 44 37 1 7 бастапқы көрінісі

1-қадам 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 және 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

2-қадам 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

3-қадам 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

4-қадам: 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

5-қадам: 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

6-қадам 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

7-қадам 1 4 7 8 22 37 44 74

Паскаль тілінде көпіршікті сұрыптау мысал

мысал:

Const kol_mas = 10;

Var Массив: массив [1..kol_mas] бүтін;

А, В, К: бүтін;

бастау

Арнайы жиһаз бен оргтехника ( «Енгізу», kol_mas, «массивінің элементтері ');

үшін: = kol_mas 1 readln (Массив [а істеу ]);

kol_mas-1 = 1 бастайды ма: а арналған

В: kol_mas үшін = а + 1 бастайды ма

Массив егер [а]> [Массив B], содан кейін басталады

K: = Массив [а]; Массив [а]: = Массив [ B]; Массив [B]: = K;

соңы;

соңы;

соңы;

( «Сортты кейін») Мысалы;

үшін: = kol_mas 1 WriteLn (Массив [а істеу ]);

соңы.

МЫСАЛ көпіршік C тілінде (C) сұрыптау

мысал:

#include

#include

(INT argc, Char * INT негізгі argv [])

{

INT Массив [8] = {36, 697, 73, 82, 68, 12, 183, 88}, Мен, FF;

{(;;) үшін

FF = 0;

{- (; і> 0 Мен = 7) үшін

([I] <Массив Массив егер [I- {1])

своп (Массив, [I] Массив [I- 1]);

FF ++;

}

}

егер (FF == 0) үзіліс;

}

getch (); // бейнебетте кешіктіріп

қайтару 0;

}.