Ќазаќ мемлекеттік ќыздар педагогика институты
Массив элементтерін сұрыптау
жүктеу/скачать 1,32 Mb.
|
аза стан Республикасыны Білім ж не ылым министрлігі аза мем
- Бұл бет үшін навигация:
- Тікелей қосу көмегімен сұрыптау
| Массив элементтерін сұрыптау
Массив элементтерін сұрыптауда қойылатын негізгі шарт: массив элементтерін сұрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып табылады. Бұл элементтерджі ретке келтіретін орын ауыстырулар сол орында орындалуы керек екенін көрсетеді. Жадыны үнемдеу критерийімен шектеле отырып, мүмкін болатын әдістердің арасынан қажеттісін таңдау қажет, ол үшін алдымен әдістерді олардың үнемділігі тұрғысынан, яғни олардың жұмыс істеу уақыты бойынша топтау қажет. Тиімділіктің өлшемі ретінде: С-қажетті салыстырулар кілтінің санын және М- элементтерді алмастырулар санын аламыз. Бұл сандар сұрыпталатын n – элементтер санының негізгі мәні болып табылады. Сұрыптаудың тиімді алгоритмдері n*log n салыстыру ретін талап етеді. Алдымен, ең қарапайым әдісті қарастырайық, тура әдіс деп атайды, мұнда салыстырулар кілті n2 ретпен орындалады. Тура әдісті талдаудан бастауға мынадай себептер бар: Тура әдіс көптеген сұрыптаулардың негізгі принциптерін түсіндіруге ерекше қолайлы. Бұл әдістің программаларын түсіну әлдеқайда жеңіл, әрі программасы қысқа. Программаның өзі де жадыдан орын алатынын білеміз. Күрделіленген әдістер көптеген операцияларды орындауды талап етеді, бұл операциялардың өздері де күрделі. Сондықтан тура әдіс кіші n үшін айтарлықтай жылдам болып табылады. «Сол орында» сұрыптау әдістерін оларды анықтайтын принциптеріне сәйкес үш категорияға бөлуге болады: Жалғау көмегімен сұрыптау. Ерекшелеу көмегімен сұрыптау. Алмастыру көмегімен сұрыптау. Тікелей қосу көмегімен сұрыптау Бұл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша a1,…,aі-1 «дайын» тізбек және aі,…,an алғашқы тізбек болып бөлінеді. Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып орналасады. Сөйтіп, ол жаңа орынға қойылады. Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау көмегімен сұрыптаудың мысалы төмендегідей: Алғашқы кілттер 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; Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды алмастыра отырып, електен өткізу болып табылады. Х кезекті aj элементімен салыстырылады, одан кейін х не бос орынға қойылады, не aj оңға қарай жылжиды, ал процесс солға қарай жүреді. Електен өткізу процесі төмендегі шарттардың бірі орындалғанда аяқталады: х-тің кілтінен кіші кілтті aj элементі табылған жағдайда; тізбектің сол жақ шетіне жеткен жағдайда. Сонымен, бұл алгоритм фрагменті төмендегідей: … For і:=2 to n do begіn X:=a[і];a[0]:=x; j:=І; Whіle x End; … Мұндай алгоритм орнықты сұрыптау процесін сипаттайды: кілттері бірдей элементтер реті өзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге болады: дайын тізбекке жаңа элемент қойылғаннан кейін өзі реттеледі. Ал, екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ бөлу процесі жалғау нүктесі табылғанша жалғаса береді. Мұндай түрлендірілген сұрыптау алгоритмі екілік жалғау әдісі деп аталады. жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|