Әдістемелік құрал
жүктеу/скачать 1,24 Mb. Pdf көрінісі
|
Алгоритм және оның мүмкіндіктері
- Бұл бет үшін навигация:
- Салыстырулардың жалпы саны
|
Мысалға, 50,20,40,75,35 массив берілген. 0-жүріс. 20-ны таңдаймыз. Оны А 0 -мен ауыстырамыз (А 0 =50). 20,50,40,75,35. 1-жүріс. 35 таңдаймыз. Оны А 1 -мен орын ауыстырамыз. 20,35,40,75,50. 2-жүріс. 40 таңдаймыз. Оны А 2 -мен орын ауыстырамыз. 20,35,40,75,50. 3-жүріс. 50 таңдаймыз. Оны А 3 -пен орын ауыстырамыз. 20,35,40,50,75. Соңғы қалған 75 саны ең үлкен элемент сұрыпталып шыққанда: 20,35,40,50,75. Сұрыптау – массив өлшеміне ғана тәуелді салыстырулардың белгіленген санына ие болуы керек. i n -ші жүрісте (A 1 + i … A 1 − n )-ге дейінгі элементтердің салыстырулар саны (n-1-(i+1)+1)=n-i-1 тең болады. Салыстырулардың жалпы саны мына формуламен анықталады: ) 1 ( 2 1 2 ) 2 )( 1 ( ) 1 ( ) 1 ( 1 ) 1 ( 2 0 2 0 2 2 − = − − − − = − − = − − − = − = n n n n n i n n n i n i Алгоритмнің күрделілігі – О(n 2 ) тең болады. Ауыстыру арқылы сұрыптау Ауыстыру арқылы сұрыптау. 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 салыстырылады 66 20,40,35,50,75 5-жүріс. 40 пен 35 салыстырылады 20,35,40,50,75 20 мен 30 реттелген 20,35,40,50,75 болып реттеледі. Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер жүктеу/скачать 1,24 Mb. Достарыңызбен бөлісу:
|