Сортирање

Сортирање је било који систематични процес уређивања, и има 2 заједничка, а ипак различита значења:

Уређивање (сортирање): уређивање ставки једну за другом по неком критеријуму;
Категоризација: груписање ставки са сличним особинама;^[1]

Сортирање информација или података

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

Најчешће примене сортирања су у:

побољшању ефикасности алогоритама претраге;^[2]
побољшању ефикасности за спајање низова.

Главни циљ сортирања информација је да оптимиззје своју корисност за специфичне задатке. Уопштено, постоје два начина груписања информација: по категорији нпр. каталог за куповину где су ставке заједно груписане под називом као што је 'кућа', 'спорт и слободно време', 'женска одећа' итд. и по интензитету нечега, као што је цена , нпр. најјефтиније до најскупље ствари (уобичајена скала). Richard Saul Wurman, је у својој књизи Information Anxiety, предлаже да најчешћа сортирању су по имену, по локацији и по времену (ово су заправо посебни случајеви категорије и хијерархије). Они заједно дају скраћеницу ЛАВКХ (Локација, Алфабет, Време, Категорија, Хијерархија) и могу се користити да опишу сваки тип сортирања информација.

Често су информације сортиране различитим методама на различитим нивоима апстракције: нпр. телефони у Енглеском адресату који су сортирани по локацији, по категорији (пословни или стамбени) и затим по алфабету. Савремена медија и даље се слаже са овим основним методама сортирања: нпр. Гугл претрага враћа листу веб страница у хијерархијској листи заснованој по њиховом личном систему бодовања, тј колико су близу задатом услову (од најближег до најдаљег).

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

Сортирање н-торки (зависи од значење тј. евиденције са пољима) се може урадити на основу једне или више ствари (компоненте). Ствари могу бити сортиране на основу својих особина. Таква компонента-особина се зове кључ сортирања.

На пример, ставке су неке књиге, кључ сортирања су наслови, аутор, и уређење је по алфабету.

Нови кључ сортирања се може направити од два или више кључева по лексикографијском уређењу. Први се зове примарни кључ сортирања, а други секундарни кључ сортирања, итд.

На пример, адресе се могу сортирати према градовима као примарни кључ, и према улицама као секундарни кључ.

Ако је вредност кључа скроз уређена , кључ дефинише слабо уређење ставки: ствари са истим кључом сортирања су једнаке према сортирању. Ако различите ствари имају имају резличите вредности кључева онда то представља јединствено уређење свари.

Стандардно уређење се често назива растуће (одговара на чињеницу да је стандардни поредак бројева растући, односно од А до З-Ш, од 0 до 9), обрнутим редоследом опадајуће (Ш-З до А, 9 до 0). За датуме и времена, растући поредак значи да ранија вредност претходи каснијој, нпр 1.1.2000 ће бити испред 1/1/2001.

Неколико познатих алгоритама у информатици

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

Физички процеси сортирања

У индустријским процесим се знатно користи сортирање за различите процесе. На пример, приликом експлоатације злата из руда, машине користе гравитацију, вибрацију и имају канале којим се раздваја злато од осталих материја (сортирајући по величини и тежини). Сортирање је такође природни процес који доводи до концентрације руде или седимента. Резултати сортирања апликације, на основу неког услова, деле га на његове компоненате засноване на променљивом квалитету. Материјале који су различити, али веома мало, као што су изотопи уранијума, је веома тешко раздвојити.

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

Види још

Референце

^ Cohen, H., & Lefebvre, C. (Eds.). (2005).Handbook of Categorization in Cognitive Science. Elsevier.
^ M Programming: A Comprehensive Guide, Richard F. Walters, Digital Press, 1997

Спољашње везе

Demonstration of Sorting Algorithms (укључујући сортирање мехуром и квиксорт)
Animated video објашњење сортирања мехуром и квиксорта и разлике у перформансама.

[1] Cohen, H., & Lefebvre, C. (Eds.). (2005).Handbook of Categorization in Cognitive Science. Elsevier.

[2] M Programming: A Comprehensive Guide, Richard F. Walters, Digital Press, 1997

[1]

[2]