«Информатиканың теориялық негіздері»
Салыстырулардың жалпы саны
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Шейкер сұрыптауы
- Қою арқылы сұрыптау
| Салыстырулардың жалпы саны мына формуламен анықталады:
Алгоритмнің күрделілігі – О(n ) тең болады. Ауыстыру арқылы сұрыптау. Ауыстыру арқылы сұрыптау. N элементтен тұратын а массивін айырбастау арқылы сұрыптау үшін немесе көпіршік әдісімен сұрыптау үшін n-ші жүріс қажет. Әрбір жүрісте көршілес екі элемент салыстырылады және егер 1-сі үлкен болса немесе 2-не тең болса, онда бұл элементтер орындарымен ауысады. әрбір жүрістің аяғында ең кіші элемент ішкі тізімнің жоғарғы жағына көтеріліп отырады. Бұл қайнап жатқан судың ішіндегі ауаның көбікшесіне ұқсас. Сондықтан көпіршік әдісі деп аталады. Мысал. Массив: 50,20,40,75,35 0-жүріс. 50 мен 20салыстырылады. 20,50,40,75,35 1-жүріс. 50 мен 40 салыстырылады 20,40,50,75,35 2-жүріс. 50 мен 70 реттелген, сондықтан қалады. 20,40,50,70,35 3-жүріс.75 пен 35 салыстырылады. 20,40,50,35,75 4-жүріс. 50 мен 35 салыстырылады 20,40,35,50,75 5-жүріс. 40 пен 35 салыстырылады 20,35,40,50,75 20 мен 30 реттелген 20,35,40,50,75 болып реттеледі. Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады. Есептеу күрделілігі. Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n2) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді. Қою арқылы сұрыптау Қою арқылы сұрыптау – келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға: 50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек. 50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту. 40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту. 75-ті 3 позициясына қыстыру. 35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|