Зертханалық жұмыс №10

Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері: таңдау арқылы сұрыптау, жылдам және таратпалы сұрыптау.

Жалпы мәлімет

Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:

5. Таңдау арқылы сұрыптау.

6. Ауыстыру арқылы сұрыптау (көпіршік әдіісі).

7. Қою арқылы арқылы сұрыптау.

8. Тез сұрыптау.

Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R₁, R₂, .. , R_n жазулары кілттік мәндері K₁, K₂,…,K_n орналасуы керек. Ki₁<Ki₂<….<Ki_n.

Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 2 категорияға бөлінеді:

- массивтерді сұрыптау (ішкі сұрыптау)

- тізбектелген файлдарды сұрыптау (сыртқы сұрыптау).

Массивтер ішкі оперативті жадыда орналасады. Оған кез келген уақытта тез кіруге болады. Ал сыртқы сұрыптау реттеуге тиісті мәліметтер көлемі өте үлкен болғанда мәліметтердің оперативті жадыға симай қалғанда қолданылады.

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

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

Мысалға, 50,20,40,75,35 массив берілген.

0-жүріс. 20-ны таңдаймыз. Оны А₀-мен ауыстырамыз (А₀=50).

20,50,40,75,35.

1-жүріс. 35 таңдаймыз. Оны А₁-мен орын ауыстырамыз.

20,35,40,75,50.

2-жүріс. 40 таңдаймыз. Оны А₂-мен орын ауыстырамыз.

20,35,40,75,50.

3-жүріс. 50 таңдаймыз. Оны А₃-пен орын ауыстырамыз.

20,35,40,50,75.

Соңғы қалған 75 саны ең үлкен элемент сұрыпталып шыққанда:

20,35,40,50,75.

Сұрыптау – массив өлшеміне ғана тәуелді салыстырулардың белгіленген санына ие болуы керек. i -ші жүрісте (A … A )-ге дейінгі элементтердің салыстырулар саны (n-1-(i+1)+1)=n-i-1 тең болады.

Салыстырулардың жалпы саны мына формуламен анықталады:

Алгоритмнің күрделілігі – О(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 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n²) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.

Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Өткен әдістерді есептерге қолданып көр:

1. Егер соңғы ауыстыру факты ғана емес оның орыны да белгілі болса, онда осы орыннан оңғы қарай орналасқан барлық көршілес элементтер жұптары керекті ретпен тұрғанын байқау қиын емес. Сондықтан, қарауды аяғына дейін жалғастырмай, осы индексте бітіруге болады.

2. Кему реті бойынша «көпіршік» сұрыптау процедурасын жазу керек.

3. Берілген қатардағы ең кіші элементтен үлкен екінші элементті табу керек.