Салыстырулардың жалпы саны мына формуламен анықталады:
Алгоритмнің күрделілігі – О(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 болып реттеледі.
Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады.
Достарыңызбен бөлісу: |
