Сортирање¶

Сортирање низова позивом уграђене функције¶

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

Уграђена функција sort сортира низ и позива се овако:

Видимо да су елементи поређани од мањих ка већим вредностима. Ако желимо да поређамо елементе низа L од већих ка мањим вредностима, то можемо да урадимо овако:

Опција reverse=True каже функцији sort да желимо да сортирамо елементе низа у „обрнутом“ поретку: од већих ка мањим вредностима.

Дакле, лако је сортирати низова бројева. И низове стрингова је лако сортирати. На пример, списак имена ученика једног разреда. Он се такође може сортирати позивом уграђене функције sort:

Пошто су имена у примеру написана латиницом, низ ће бити сортиран абецедно. Ако су имена написана ћирилицом низ ће бити сортиран азбучно, како показује следећи пример:

Пример.¶

Написати програм који од корисника учитава природан број \(n\) који представља број запослених у некој компанији, и природан број \(k\), потом учитава \(n\) реалних бројева који представљају зараде запослених и штампа \(k\) највећих зарада у компанији.

Решење. Потребно је зараде сортирати од већих ка мањим вредностима и онда исписати првих \(k\) елемената тако сортираног низа.

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм K_najvecih.py.

Ево и кратке видео-демонстрације:

Пример.¶

Написати програм који од корисника учитава паран природан број \(n\), потом \(n\) различитих реалних бројева и онда одређује и штампа реалан број \(m\) такав да је тачно половина од учитаних бројева мања од \(m\), а друга половина већа од \(m\). Зна се да је \(n\) паран број и то не треба проверавати. Такође се зна да ће сви учитани реални бројеви бити различити и то не треба проверавати.

На пример, за \(n = 10\) и бројеве

1.5 3.7 2.25 9.81 3.1415 -0.26 2.9 8.11 10.12 -5.41

једна могућност за \(m\) је \(m = 3.02075\) зато што је тачно пет од десет наведених бројева мање од 3.02, док су осталих пет бројева већи.

Решење.

Идеја решења се састоји у томе да се учитани низ сортира, па да се нађе број који је између два „средња броја“. На пример, за бројеве

1.5 3.7 2.25 9.81 3.1415 -0.26 2.9 8.11 10.12 -5.41

након сортирања добијамо

-5.41 -0.26 1.5 2.25 2.9 3.1415 3.7 8.11 9.81 10.12

Два броја „на средини“ сортираног низа су 2.9 и 3.1415, па за број \(m\) можемо узети њихову аритметичку средину. Овако израчуната вредност на средини низа сортираних бројева назива се медијана.

\[\frac{2.9 + 3.1415}{2} = 3.02075\]

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм Broj_na_sredini.py.

Како раде алгоритми за сортирање¶

Погледајмо следећи пример у коме нам је за групу ученика дато неколико података о њима (име, пол, старост, маса и висина):

razred = [["Ana",     "ž", 13, 46, 160],
          ["Bojan",   "m", 14, 52, 165],
          ["Vlada",   "m", 13, 47, 157],
          ["Gordana", "ž", 15, 54, 165],
          ["Dejan",   "m", 15, 56, 163],
          ["Đorđe",   "m", 13, 45, 159],
          ["Elena",   "ž", 14, 49, 161],
          ["Žaklina", "ž", 15, 52, 164],
          ["Zoran",   "m", 15, 57, 167],
          ["Ivana",   "ž", 13, 45, 158],
          ["Jasna",   "ž", 14, 51, 162]]

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

У наставку показујемо како раде два стандардна алгоритма за сортирање:

• Сортирање бирањем најмањег елемента (selection sort), и

• Бабл-сорт алгоритам (bubble sort)

Сортирање бирањем најмањег елемента (selection sort)¶

Сортирање бирањем најмањег елемента (од енглеског selection sort) је један од стандардних алгоритама за сортирање. Основна идеја овог алгоритма је веома једноставна:

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

2. Потом нађемо најмањи елемент у остатку низа (дакле у низу који чине елементи од другог до последњег) и њега ставимо на друго место; елемент који се затекао на другом месту ставимо негде да нам не смета, рецимо на место елемента који смо преместили на друго место.

3. Потом нађемо најмањи елемент у остатку низа (дакле у низу који чине елементи од трећег до последњег) и њега ставимо на треће место

и тако до краја низа. На пример пођимо од низа:

3, 1, 2, 5, 0, -1, 4

Најмањи елемент у том низу је -1 и ми ћемо га практично заменити са првим елементом:

-1; 1, 2, 5, 0, 3, 4
#-#            #-#

За потребе овог примера иза елемента -1 смо ставили ознаку тачка-запета ; како бисмо означили да је тај део низа сортиран и да га не треба даље разматрати. Најмањи број у остатку низа (дакле, иза знака ;) је 0, па ћемо тај елемент заменити са другим елементом низа:

-1, 0; 2, 5, 1, 3, 4

Тако смо сортирани део низа продужили за једно место. Најмањи број у остатку низа (дакле, иза знака ;) сада је 1, па ћемо га заменити са трећим елементом низа:

-1, 0, 1; 5, 2, 3, 4
      #-#   #-#

Најмањи број у остатку низа (дакле, иза знака ;) је 2, и њега ћемо заменити са четвртим елементом низа:

-1, 0, 1, 2; 5, 3, 4
         #-##-#

Најмањи број у остатку низа је 3, и њега ћемо заменити са петим елементом низа:

-1, 0, 1, 2, 3; 5, 4
            #-##-#

Коначно, најмањи број у остатку низа је 4, и њега ћемо заменити са шестим елементом низа:

-1, 0, 1, 2, 3, 4; 5
               #-##-#

Алгоритам се завршава када у несортираном делу низа остане само један елемент, јер је он сигурно најмањи у несортираном делу низа, и нема потребе да га замењујемо са њим самим.

Ево Пајтон функције која тачно тако сортира низ:

Неколико коментара:

1. за празне низове и низове дужине 1 не треба ништа радити (нпр. низ [3] је већ сортиран);

2. у спољашњем for циклусу индекс i иде до претпоследњег места зато што ће постављањем праве вредности на претпоследње местo уједно и на последње место бити постављена одговарајућа вредност, како смо видели у претходном примеру;

3. променљива m садржи индекс најмањег елемента у остатку низа; зато унутрашњи for циклус креће од i+1;

4. наредба a, b = b, a размењује вредност променљивих a и b; зато наредба L[i], L[m] = L[m], L[i] размењује вредност првог елемента несортираног дела низа (што је L[i]) са најмањим елементом у несортираном делу низа (што је L[m]).

Следећи видео демонстрира рад функције selection_sort на још једном примеру:

Пример.¶

Написати програм који од корисника учитава природан број \(n\) који представља број запослених у некој компанији, потом учитава \(n\) реалних бројева који представљају зараде запослених и штампа те зараде по величини, од највеће до најмање.

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм Od_najvece_do_najmanje.py.

Пример.¶

Решићемо поново следећи задатак. Написати програм који од корисника учитава природан број \(n\) који представља број запослених у некој компанији, и природан број \(k\), потом учитава \(n\) реалних бројева који представљају зараде запослених и штампа \(k\) највећих зарада у компанији.

Решење. Потребно је зараде сортирати од већих ка мањим вредностима и онда исписати првих \(k\) елемената тако сортираног низа. Зато што се у задатку од нас тражи да испишемо само првих \(k\) највећих зарада у компанији применићемо наш алгоритам за сортирање:

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм Samo_K_najvecih.py.

Пример.¶

У следећем низу је за групу ученика дато неколико података о њима (име, пол, старост, маса и висина):

razred = [["Ana",     "ž", 13, 46, 160],
          ["Bojan",   "m", 14, 52, 165],
          ["Vlada",   "m", 13, 47, 157],
          ["Gordana", "ž", 15, 54, 165],
          ["Dejan",   "m", 15, 56, 163],
          ["Đorđe",   "m", 13, 45, 159],
          ["Elena",   "ž", 14, 49, 161],
          ["Žaklina", "ž", 15, 52, 164],
          ["Zoran",   "m", 15, 57, 167],
          ["Ivana",   "ž", 13, 45, 158],
          ["Jasna",   "ž", 14, 51, 162]]

Написати Пајтон функцију selection_sort_by(k, L) која овако структуриране податке у низу L сортира по садржају колоне k. На пример, selection_sort_by(0, razred) ће сортирати низ razred по колони 0, дакле, по имену.

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм SelSort_po_kriterijumu.py.

Бабл-сорт алгоритам (bubble sort)¶

Бабл-сорт (од енглеског bubble sort, што би могло да се преведе као „сортирање помоћу мехура“) је један од стандардних алгоритама за сортирање низова. Он није најбржи, али је погодан када низ који сортирамо није превише „чупав“. Тада ради брже од сортирања бирањем најмањег елемента.

Идеја бабл-сорт алгоритма је такође једноставна:

1. Упоредимо први и други елемент низа, па ако је први већи од другог, заменимо им места.

2. Онда упоредимо други и трећи елемент низа, па ако је други већи од трећег, замени им места.

3. Онда упоредимо трећи и четврти елемент низа, и тако до краја низа.

4. Ако смо у овом пролазу кроз низ направили бар једну замену, кренемо из почетка.

5. Када прођемо кроз низ и не направимо ниједну замену, низ је сортиран (јер је први елемент мањи од другог, други мањи од трећег, итд.).

На пример пођимо од низа:

3, 1, 2, 5, 0, -1, 4
#--#

Крећемо први пролаз кроз низ. Пошто је први елемент већи од другог, заменимо им места.

1, 3, 2, 5, 0, -1, 4
   #--#

Сада поредимо други и трећи елемент низа. Пошто је други већи од трећег, заменимо им места.

1, 2, 3, 5, 0, -1, 4
      #--#

Трећи елемент није већи од четвртог, па овде не треба мењати места елементима низа.

1, 2, 3, 5, 0, -1, 4
         #--#

Како је 5 веће од 0, заменимо места елементима.

1, 2, 3, 0, 5, -1, 4
            #---#

Поново заменимо места.

1, 2, 3, 0, -1, 5, 4
                #--#

И још једном.

1, 2, 3, 0, -1, 4, 5

Овим је окончан први пролаз кроз низ. Приметимо да је у првом пролази највећи елемент низа стигао на крај, као мехурић који се пење у чаши (по овој аналогији је бабл-сорт и добио име: енгл. bubble = мехур). Зато у наредном пролазу нема потребе ићи до краја низа. Довољно је упоређивати елементе до претпоследњег елемента. Други пролаз изгледа овако:

1, 2, 3, 0, -1, 4, 5
#--#

1, 2, 3, 0, -1, 4, 5
   #--#

1, 2, 3, 0, -1, 4, 5
      #--#

1, 2, 0, 3, -1, 4, 5
         #---#

1, 2, 0, -1, 3, 4, 5
             #--#

Видимо да је на крају другог пролаза други највећи елемент „испливао на површину“. Овим је окончан други пролаз. Након трећег пролаза низ постаје:

1, 0, -1, 2, 3, 4, 5

а након четвртог:

0, -1, 1, 2, 3, 4, 5

У петом пролазу нећемо ниједном пару елемената заменити места, и процес се зауставља.

Ево Пајтон функције која тачно тако сортира низ:

Неколико коментара:

1. за празне низове и низове дужине 1 не треба ништа радити (нпр. низ [3] је већ сортиран);

2. променљива zamena садржи информацију о томе да ли смо направили бар једну замену места суседних елемената; иницијално је постављамо на True како бисмо отпочели сортирање;

3. одмах након уласка у циклус је постављамо на False и тек ако се током проласка кроз низ направи бар једна замена, њена вредност ће бити враћена на True;

4. на крају тела циклуса смањујемо n за један зато што сваким пролазом кроз циклус још један „мехурић исплива на површину“ и тај део низа нема потребе даље проверавати (крај низа је увек сортиран);

5. циклус ће се завршити када прођемо кроз низ и не направимо ниједну замену; то значи да ниједaн елемент није већи од свог десног суседа, односно да је низ сортиран.

Следећи видео демонстрира рад функције bubble_sort на још једном примеру:

Пример.¶

У следећем низу је за групу ученика дато неколико података о њима (име, пол, старост, маса и висина):

razred = [["Ana",     "ž", 13, 46, 160],
          ["Bojan",   "m", 14, 52, 165],
          ["Vlada",   "m", 13, 47, 157],
          ["Gordana", "ž", 15, 54, 165],
          ["Dejan",   "m", 15, 56, 163],
          ["Đorđe",   "m", 13, 45, 159],
          ["Elena",   "ž", 14, 49, 161],
          ["Žaklina", "ž", 15, 52, 164],
          ["Zoran",   "m", 15, 57, 167],
          ["Ivana",   "ž", 13, 45, 158],
          ["Jasna",   "ž", 14, 51, 162]]

Написати Пајтон функцију bubble_sort_by(k, L) која овако структуриране податке у низу L сортира по садржају колоне k. На пример, bubble_sort_by(0, razred) ће сортирати низ razred по колони 0, дакле, по имену.

Изврши исти програм и у Пајтон окружењу!

Покрени овај програм на свом рачунару тако што ћеш у пакету фајлова за вежбу, покренути IDLE и из потфолдеру P05 извршити програм BubSort_po_kriterijumu.py.