Э. А. Абдыкеримова
Массив элементтерін сұрыптау
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- Тікелей қосу көмегімен сұрыптау
| Массив элементтерін сұрыптау
Массив элементтерін сҧрыптауда қойылатын негізгі шарт: массив элементтерін сҧрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып табылады. Тікелей қосу көмегімен сұрыптау Бҧл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша a 1 ,…,a і-1 «дайын» тізбек және a і ,…,a n алғашқы тізбек болып бӛлінеді. Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып орналасады. Сӛйтіп, ол жаңа орынға қойылады. Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау кӛмегімен сҧрыптаудың мысалы тӛмендегідей: 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 x End; … Мҧндай алгоритм орнықты сҧрыптау процесін сипаттайды: кілттері бірдей элементтер реті ӛзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге болады: дайын тізбекке жаңа элемент қойылғаннан кейін ӛзі реттеледі. Ал, екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ бӛлу процесі жалғау нҥктесі табылғанша жалғаса береді. Мҧндай тҥрлендірілген сҧрыптау алгоритмі екілік жалғау әдісі деп аталады. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|