Массив элементтерін сұрыптау

105 
Алғашқы кілттер 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 
і=7 06 12 18 42 44 55 94 67 
і=8 06 12 18 42 44 55 67 94 
Бҧл сҧрыптаудың алгоритмі тӛмендегідей: 
For і:=2 To n Do 
X:=a[і]; {x-ті a[1],…,a[і] арасындағы сәйкес орынға қою} 
End; 
Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды 
алмастыра отырып, електен ӛткізу болып табылады. Х кезекті a
j
элементімен 
салыстырылады, одан кейін х не бос орынға қойылады, не a
j
оңға қарай 
жылжиды, ал процесс солға қарай жҥреді. Електен ӛткізу процесі тӛмендегі 
шарттардың бірі орындалғанда аяқталады: 
1. х-тің кілтінен кіші кілтті a
j
элементі табылған жағдайда; 
2. тізбектің сол жақ шетіне жеткен жағдайда. 
Сонымен, бҧл алгоритм фрагменті тӛмендегідей: 
… 
For і:=2 to n do
begіn 
X:=a[і];a[0]:=x; j:=І; 
Whіle xA[j]:=x 
End; 
… 
Мҧндай алгоритм орнықты сҧрыптау процесін сипаттайды: кілттері бірдей 
элементтер реті ӛзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге 
болады: дайын тізбекке жаңа элемент қойылғаннан кейін ӛзі реттеледі. Ал, 
екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ 
бӛлу процесі жалғау нҥктесі табылғанша жалғаса береді. Мҧндай 
тҥрлендірілген сҧрыптау алгоритмі екілік жалғау әдісі деп аталады. 

жүктеу/скачать 1,31 Mb.

Достарыңызбен бөлісу: