Э. А. Абдыкеримова
Тура қосулар кӛмегімен сҧрыптау
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- 13.10 Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс)
|
13.9 Тура қосулар кӛмегімен сҧрыптау Тура қосулар кӛмегімен сҧрыптаудың негізгі идеясы - жаңа элементті реттелген тізімге қажетті әсеріне қосу болып табылады. Мҧндай сҧрыптауда кез келген тізімнің бірінші элементі сҧрыпталған деп есептеледі. Екінші элементті бірінші элементтен тҧратын тізімнің керек жеріне қосады. Енді берілген тізімнің ҥшінші элементін реттелген екі элементтен тҧратын қажет жеріне қосады. Бҧл процесті берілген тізім элементінің барлығы тізімнің сҧрыпталған бӛлігіне қосылғанша жалғасады. Қажетті орынды іздеу процесін былай жҥргізуге болады: х- ті кезектегі а элементімен салыстырамыз. Одан кейін немесе х бос орынға қосылады немесе а оңға жылжиды және процес солға кетеді. Бҧл процес келесі екі шарттың бірі орындалған кезде аяқталады. 1) кілті x-тің кілтінен кіші элемент табылды; 2) дайын тізбектің сол жағына жетті ; Мҧнда бӛгет әдісін қолданған дҧрыс, яғни х мәні бар а(о) бӛгетін енгіземіз. Толық алгоритмді келтіреміз: Procedure SORT 1; VAR E, j : іndex ; x: іtem ; BEGІN FOR і: =2 TO n 20 X: = a [І]; a[o]:=x; j=І; 99 Whіle x END; Тура қосулар кӛмегімен сҧрыптау мысалы: Бастапқы кілттер 44 55 12 42 94 18 06 67 І=2 44 55 12 42 94 18 06 67 І=3 12 44 55 42 94 18 06 67 І=4 12 42 44 55 94 18 06 67 І=5 12 42 44 55 94 18 06 67 І=6 12 18 42 44 55 94 06 67 13.10 Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс) Тура алмастыру алгоритмі кӛршілес элементтердің пар жҧбын салыстыру және орнын алмастыруға негізделген, мҧндай салыстыру мен алмастырулар барлық элементтер реттелгенше жалғастырылады. Егер массивтерді горизонталь емес вертикаль тҥрде қарастырсақ ондағы элементтерді судың кӛпіршіктері деп алуға болады. Оның әрбіреуінің салмағы оның кілтіне сәйкес келеді. Бҧл жағдайда әрбір жҥрісте бір кӛпіршік оның салмағына қарай деңгейге кӛтеріледі. Мысалы. Бҧл әдіс бойынша кӛрші тҧрған екі элемент салыстырылып, одан кейін сҧрыптау шартына тәуелді орындары алмасады. I = 1 2 3 4 5 6 7 8 44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 55 44 42 42 42 42 94 42 18 55 44 44 44 44 18 94 42 42 55 55 55 55 06 18 94 67 67 67 67 67 67 67 67 94 94 94 94 94 PROCEDURE BybbleSort; VAR i,j, x: integer; BEGIN FOR i: =2 TO n DO FOR j: = n TO i DO If a[j-1]> a[j] THEN begin x: = a[j - 1]; a[j-1]:=a[j]; a[j]: = x end END; - + - + басы n, a 1 …a n енгізу i:=2 j:=n a j-1 >a j x:= a j-1 a j-1 := a j a j :=x j:=j-1 j i i:=i+1 i n a 1 …a n шығару соңы + - |