Массивтерді сұрыптау алгоритмдері.

Сұрыптау дегеніміз – жиын объектілерін белгілі бір тәртіппен ауыстырып қою процесі. Сұрыптаудың мақсаты - элементтерді сұрыпталған жиында іздеуді жеңілдету. Массивтерді сұрыптау әдістеріне қойылатын негізгі талап – жадыны тиімді пайдалану.

Тиімді алгоритмі - in site (орнында). Мынадай параметрлерді қамтиды: С (compare) – кілттерді алыстыруға қажетті сан. M (move) – элементтердің қажетті сілтемесі. С~N∙logN (салыстыру), мұндағы N – сұрыпталатын массив элементтерінің саны. C~N*N салыстыруды талап етеді. «Орнында» әдісін үш негізгі класқа бөлуге болады:

- таңдау арқылы сұрыптау;

- қою арқылы сұрыптау;

- алмастыру арқылы сұрыптау.

Таңдау арқылы сұрыптау – кілтінің мәні үлкен элемент таңдалады және соңғымен орын ауыстырылады. s-1 элемент үшін қайталанады. Табылған элемент соңғының алдындағы элементпен орын ауыстырады және т.б.

Қою арқылы сұрыптау – элементтер дайын реттелген және реттелмеген тізбекке бөлінеді. Реттелген бөлік басында бір ғана элементті сақтайды. Реттелмеген бөліктегі кезекті элемент реттелген бөліктегі жөні келетін орынға қойылады. Осылайша процесс реттелмеген бөлік босап қалғанға дейін жүреді. Оны былай көрсетуге болады:

for(i=2; i<size1; i++)

{

copy=arr[i];

/* arr[0], . . . ,arr[i-1]массивінің сұрыпталған элементтерінің арасында қажетті жерге copy қою; */

}

Алмастыру арқылы сұрыптау – екі көршілес элементтердің орындарын алмастырып қою, алдымен көрші екі элемент салыстырылады.

Негізгі әдебиет: 6 [104-107], 7 [55-88]

Қосымша әдебиет: 18 [128-130], 19 [25-27]