Э. А. Абдыкеримова


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



Pdf көрінісі
бет116/134
Дата31.01.2022
өлшемі1,31 Mb.
#116510
1   ...   112   113   114   115   116   117   118   119   ...   134
Байланысты:
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ

Массив элементтерін сұрыптау
 
Массив  элементтерін  сҧрыптауда  қойылатын  негізгі  шарт:  массив 
элементтерін  сҧрыптаудың  таңдалған  әдісі  жадыны  тиімді  пайдалануда  болып 
табылады. 
Тікелей қосу көмегімен сұрыптау 
Бҧл  әдіс  карта  ойынында  кеңінен  пайдаланылады.  Элементтер  ойша 
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                       A[j]:=x 
                        End; 
                                      … 
Мҧндай алгоритм орнықты сҧрыптау процесін сипаттайды: кілттері бірдей 
элементтер реті ӛзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге 
болады:  дайын  тізбекке  жаңа  элемент  қойылғаннан  кейін  ӛзі  реттеледі.  Ал, 
екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ 
бӛлу  процесі  жалғау  нҥктесі  табылғанша  жалғаса  береді.  Мҧндай 
тҥрлендірілген сҧрыптау алгоритмі екілік жалғау әдісі деп аталады. 


Достарыңызбен бөлісу:
1   ...   112   113   114   115   116   117   118   119   ...   134




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет