Унутрашње сортирање

Из Википедије, слободне енциклопедије

Унутрашње сортирање је било који процес сортирања који се одвија потпуно унутар главне меморије рачунара. Ово је могуће докле год су подаци довољно мали тако да сви могу стати у главну меморију рачунара. За сортирање већих група података можда би било неопходно само један део података држати у меморији, јер не би могли сви стати одједном. Остатак податак се наравно налази у већој, али споријој меморији, као што је хард-диск. Било које читање или уписивање података са и у ову спору меморију може знатно успорити процес сортирања. Овај проблем је повезан и са другим алгоритмима за сортирање.

Постоји 7-типова алгоритама са унутрашњим сортирањем :- Bubble Sort, Insertion Sort, Quick Sort, Heap Sort, merge Sort, Radix Sort,Selection sort. Узмимо на пример Bubblesort, где суседни подаци мењају позиције како би их сместили у прави поредак, тако да подаци изгледају као да "испливавају" на врх екрана. Ako би ово морало да буде изведено из више мањих група података, онда када би сортирали све податке у групи 1, наставили би у групу 2, али би видели да неки од података из групе 1 морају да "испливају" до групе 2, и обрнуто (постоје подаци у групи 2 који припадају групи 1, и подаци у групи 1 који припадају групи 2 или некој од следећих група). Због овога ће се групе читати и уписивати назад на диск много пута док подаци прелазе границе између њих, што ће утицати на знатно опадање ефикасности алгоритма. Ако би подаци могли да се задрже у меморији као једна група, онда би се овај утицај на учинак самог алгоритма могао избећи.

Са друге стране, неки алгоритми подносе спољашње сортирање много боље. Merge sort раздваја податке у групе, сортира групе помоћу неког другог алгоритма (можда bubblesort или quick sort) и затим преспоји поново групе две по две тако да све буду у правом поретку. Овај поступак смањује број уписивања и читања група података на и са диска, а и популаран је метод спољашњег сортирања.