Негізгі бет
Компьютерлік ғылымдар
Course: Компьютерлік ғылымдар > Unit 1
Lesson 4: Таңдау арқылы сұрыптауТаңдау арқылы сұрыптау псевдокоді
Карточкаларды сұрыптаудың көптеген әдістері бар. Мұнда таңдау бойынша сұрыптау деп аталатын қарапайым нұсқа бар, жоғарыдағы карталарды сіздің сұрыптағаныңызға ұқсас болуы мүмкін:
- Ең кішкентай картаны табыңыз. Оны бірінші картамен ауыстырыңыз.
- Екінші үлкен картаны табыңыз. Оны екінші картамен ауыстырыңыз.
- Үшінші үлкен картаны табыңыз. Оны үшінші картамен ауыстырыңыз.
- Келесі үлкен картаны іздеуді қайталаңыз және массив сұрыпталғанша осы алгоритмді қайталай бересіз осылай дұрыс күйге келтіріңіз.
Бұл алгоритм таңдап сұрыптау деп аталады, өйткені ол келесі үлкен элементті бірнеше рет таңдайды және оның орнын өзгертеді.
Төмендегі алгоритммен өзіңіз таныса аласыз. Алгоритмнің әр қадамын көру үшін "қадамды" қолданудан бастаңыз, содан кейін барлық қадамдарды соңына дейін көріп оны түсінгеннен кейін "автоматты түрде" дегенді көріңіз.
Мұны өз көзіңізбен көргенде, сіз осы алгоритм туралы не ойлайсыз? Бұның қай бөліктері көп уақытты алады? Бұл үлкен массивтермен қалай жұмыс істейді деп ойлайсыз? Осы алгоритмді өткізіп, іске асырған кезде осы сұрақтарды есіңізде сақтаңыз.
Ішкі массивтегі ең кіші элементінің индексін іздеу
Таңдап сұрыптаудағы қадамдардың бірі - келесі үлкен картаны табу үшін кіші картаны дұрыс орынға қою керек . Мысалы, егер массив бастапқыда осындай мәндерді қамтыса[13, 19, 18, 4, 10], алдымен массивтегі ең аз мән индексін табу керек. 4 ең кіші мән болғандықтан, ең кіші мән индексі 3-ке тең болады.
Таңдап сұрыптау 3 индексінің мәнін 0 индексінің мәніне өзгертеді[4, 19, 18, 13, 10]. Енді оны 1индексіне ауыстыру үшін екінші кіші санның индексін табу керек.
Массивте екінші кіші санның индексін табатын кодты жазу қиын болуы мүмкін. Сіз мұны жасай алатындығыңызға сенімдімін, бірақ одан да жақсы әдіс бар. Ең кіші мән 0 индексімен ауыстырылғандықтан, біз массивтің 1индексінен басталатын бөлігінде ең кіші мәнді тапқымыз келетінін ескеріңіз. Біз массив бөлімін ішкі массив деп атаймыз, сондықтан бұл жағдайда бізге 1индексінен басталатын кіші массив ішіндегі ең кіші индекс қажет. Біздің мысал үшін, егер толық массив болса [4, 19, 18, 13, 10], содан кейін 1-индекстен басталатын ішкі массивтегі ең кіші мән 10-ға тең, ал бастапқы массивте 4 индексі бар. Сонымен, 4 индексі - толық массивтің екінші үлкен элементінің орналасуы.
Келесі стратегияда осы стратегияны қолданып көріңіз, содан кейін сіз толықтай таңдап сұрыптау алгоритмін жүзеге асыра аласыз .
Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.
Талқылауға қосылғыңыз келе ме?
Әзірге посттар жоқ.