«Информатиканың теориялық негіздері»


Таңдау көмегімен сұрыптау



бет48/80
Дата07.01.2022
өлшемі0.6 Mb.
#20727
1   ...   44   45   46   47   48   49   50   51   ...   80
Таңдау көмегімен сұрыптау.

А массивінде мәліметтердің n элементі сақталған және бұл массив бойынша n-1 жүріс етеді. 0-ші жүрісте ең кіші элемент таңдалады. Ол кейіннен А0 элементпен айырбасталады. Келесі жүрісте тізімнің А1 элементінен бастап реттелмеген бөлігі қарастырылады. Мұнда ең кіші элемент тауып алынады да А1-де сақталады. Ары қарай А2 ... Аn-1 тізіміндегі ең кіші элемент ізделеді. Табылған мән А2-мен ауысады. Осылайша, n-1 жүріс өтеді. Соңында тізімнің реттелмеген аяғы 1 элементке дейін қысқарады. Сол элемент ең үлкен болып табылады.


Мысалға, 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-ші жүрісте (A… A)-ге дейінгі элементтердің салыстырулар саны (n-1-(i+1)+1)=n-i-1 тең болады.



Достарыңызбен бөлісу:
1   ...   44   45   46   47   48   49   50   51   ...   80




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет