Сортирани низ

Сортирани низ
Тип	низ
Година изума	1945
Изумитељ	Џон фон Нојман
Временска комплексност у великој О нотацији
Алгоритам Просек Најгори случај Простор О(н) О(н) Претрага О(лог н) О(лог н) Уметање О(н) О(н) Брисање О(н) О(н)

Сортирани низ је низ у којем је сваки елемент сортиран у бројевном, словном или неком другом реду, и позициониран у прорачунатој меморији на рачунару. Најчешће се користе у рачунарима да се импементирају статичне табеле са различитим вредностима које имају исти тип. Сортирање низа је корисно за организовање података у одређеној форми и да им се брзо приступа.

Методе

Постоји много познатих метода помоћу којих низ мозе бити сортиран селекцијом, мехуром, уметањем, спајањем, пребројавањем, квиксортом и хипсортом. Ове технике сортирања имају различите алгоритме и такође постоје различите предности за коришћење неког од њих.

Преглед

Сортирани низови су просторно најштедљивија структура података.

Елементи који су сортирани, бинарном претрагом се претражују комплексношћу $O(logn)$; тако сортирани низову су погодни када елементи треба брзо да се нађу. Ова комплексност је иста као и код самобалансирајућих бинарних стабала претраге.

У неким структурама података користи се низ објеката. У таквим случајевима, исте методе сортирања могу да се користе за сортирање структура у односу на неки кључ, на пример, сортирање студената по бројевима, именима или оценама.

Ако је у питању динамичко сортирање, онда је могуће брисање и убацивање елемената. Брисање и убацивање елемената захтева $O(n)$ времена, зато што мора да се прође кроз све елементе, у поређењу са самобалансирајућим стаблом, где за брисање и убацивање елемената треба $O(logn)$ времена. У случају када се брише или убацује на крај низа, у сортираном низу се то извршава за $O(1)$, док код балансираног стабла треба $O(logn)$.

Елементи у сортираном низу могу да се претражују преко индекса у О(1) времену, за друге комплексније операције потребно је О(лог н) или О(н) времена.

Историја

Џон фон Нојман је написао први програм за сортирање (сортирање спајањем) 1945. године, за време прављења ЕДВАЦ рачунара.

Примена

Комерцијално рачунаство

Владине организације, приватне компаније и апликације базиране на вебу имају много података. Подацима се често приступа више пута. Чување података као сориран низ омогућује лак приступ подацима.

Дискретна математика

Соритани низови могу да се користе за имплементацију Дајкистриног алгоритма или Примовог алгоритма. Такође и за алгоритме као што је Крускалов за тражење минималних разапињућих стабала.

Приоритетна заказивања

Код оперативних система, многи процеси чекају на извршавање, јер процесор може да обрађује само један процес у одређеном тренутку. Процеси се шаљу процесору по приоритету заснованом на сортираном низу.

Распоређивање по времену извршавања

Ово је посебан случај приоритетног заказивања. Процеси се сортирају на основу времена трајања. Процес који захтева најмање времена ће се извршити први.

Процес	Време извршавања
П1	3
П2	4
П3	1
П4	8
П5	6

Види још

• Алгоритми сортирања
• Бинарна претрага