Drugi razred - Peta lekcija - Sortiranje

6. Сортирање

У овој лекцији се бавимо сортирањем низова.

1. Прво показујемо како се низови сортирају позивом уграђене функције.
2. Потом имплементирамо алгоритам за сортирање бирањем најмањег елемента (selection sort).
3. На крају показујемо бабл-сорт (bubble sort).

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

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

$$[3,1,2,5,0,-1,4]\to [-1,0,1,2,3,4,5]$$

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

In [1]:

L = [3, 1, 2, 5, 0, -1, 4]
L.sort()

Ако проверимо вредност променљиве L након позива функције sort видећемо да су елементи низа сада поређани од мањих ка већим вредностима:

In [2]:

L

Out[2]:

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

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

In [3]:

L.sort(reverse=True)
L

Out[3]:

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

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

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

In [4]:

razred = [
    "Nenadović, Nenad",
    "Petrović, Petar",
    "Milanović, Milan",
    "Anić, Ana",
    "Vuković, Vuk",
    "Sarić, Sara"
]

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

In [5]:

razred.sort()
razred

Out[5]:

['Anić, Ana',
 'Milanović, Milan',
 'Nenadović, Nenad',
 'Petrović, Petar',
 'Sarić, Sara',
 'Vuković, Vuk']

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

In [6]:

razred = [
    "Ненадовић, Ненад",
    "Петровић, Петар",
    "Милановић, Милан",
    "Анић, Ана",
    "Вуковић, Вук",
    "Сарић, Сара"
]

In [7]:

razred.sort()
razred

Out[7]:

['Анић, Ана',
 'Вуковић, Вук',
 'Милановић, Милан',
 'Ненадовић, Ненад',
 'Петровић, Петар',
 'Сарић, Сара']

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

In [2]:

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 зада критеријум за сортирање, али је он веома апстрактан и оставићемо га за неки каснији разред. Ми ћемо овај проблем решити тако што ћемо написати наш алгоритам за сортирање којим ћемо моћи да соритрамо произвоље податке по критеријуму који нам у том тренутку одговара.

6.2. Сортирање бирањем најмањег елемента (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

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

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

In [9]:

def selection_sort(L):
    n = len(L)
    if n <= 1: return
    for i in range (n-1):
        m = i
        for j in range(i+1,n):
            if L[j] < L[m]: m = j
        L[i], L[m] = L[m], L[i]

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

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

Пример. Ево како ову стратегију можемо да искористимо да решимо проблем са краја прошлог одељка. Да се подсетимо, променљива razred садржи податке о ученицима једног разреда:

In [4]:

razred

Out[4]:

[['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]]

Написаћемо Пајтон функцију која сортира табелу управо презентованим алгоритмом према вредностима колоне к:

In [3]:

def selection_sort_by(k, L):
    n = len(L)
    if n <= 1: return
    for i in range (n-1):
        m = i
        for j in range(i+1,n):
            # ovde poredimo vrednosti na k-tom mestu u redu L[j] i L[m]
            if L[j][k] < L[m][k]: m = j
        L[i], L[m] = L[m], L[i]

Ако желимо да сортирамо табелу по висини, рецимо, позваћемо горњу функцију овако:

In [9]:

selection_sort_by(4, razred)
razred

Out[9]:

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

а ако желимо да сортирамо табелу по старости, позваћемо функцију овако:

In [8]:

selection_sort_by(2, razred)
razred

Out[8]:

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

6.3. Бабл-сорт алгоритам (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

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

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

In [10]:

def bubble_sort(L):
    n = len(L)
    if n <= 1: return
    zamena = True
    while zamena:
        zamena = False
        for i in range(n-1):
            if L[i] > L[i+1]:
                zamena = True
                L[i], L[i+1] = L[i+1], L[i]
        n -= 1

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

1. за празне низове и низове дужине 1 не треба ништа радити (нпр. низ [3] је већ сортиран);
2. променљива zamena садржи информацију о томе да ли смо направили бар једну замену места суседних елемената; иницијално је постављамо на True како бисмо отпочели сортирање;
3. одмах након уласка у циклус је постављамо на False и тек ако се током проласка кроз низ направи бар једна замена, њена вредност ће бити враћена на True;
4. на крају тела циклуса смањујемо n за један зато што сваком пролазом кроз циклус још један "мехурић исплива на површину" и тај део низа нема потребе даље проверавати (крај низа је увек сортиран);
5. циклус ће се завршити када прођемо кроз низ и не направимо ниједну замену; то значи да ниједна елемент није већи од свог десног суседа, односно, да је низ сортиран.

Пример. Ево како ову стратегију можемо да искористимо да решимо проблем са краја првог одељка. Написаћемо Пајтон функцију која сортира табелу управо презентованим алгоритмом према вредностима колоне к:

In [3]:

def bubble_sort_by(k, L):
    n = len(L)
    if n <= 1: return
    zamena = True
    while zamena:
        zamena = False
        for i in range(n-1):
            # ovde poredimo vrednosti na k-tom mestu u redu L[i] i L[i+1]
            if L[i][k] > L[i+1][k]:
                zamena = True
                L[i], L[i+1] = L[i+1], L[i]
        n -= 1

Ако желимо да сортирамо табелу по маси, рецимо, позваћемо горњу функцију овако:

In [4]:

bubble_sort_by(3, razred)
razred

Out[4]:

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

6.4. Задаци

Задатак 1. Написати Пајтон функцију kti_po_velicini(L, k) која враћа елемент низа L који је $k$-ти по величини.

Задатак 2. Медијана низа је елемент низа који се налази тачно на средини низа по величини. Написати Пајтон функцију medijana(L) која одређује медијану низа L.

Задатак 3. Написати Пајтон функцију po_prezimenu(L) која податке о ученицима једног разреда сортира по презимену. Подаци о ученицима су дати низом у коме сваки ред садржи име, презиме и оцене ученика, на пример овако:

In [15]:

razred = [
    ["Dejan", "Dejanović", 3, 4, 5, 4, 5],
    ["Mara", "Marić", 4, 5, 5, 4, 2],
    ["Miloš", "Milošević", 2, 5, 4, 3, 3],
    ["Petar", "Marković", 5, 4, 5, 5, 5]
]

Задатак 4. Написати Пајтон функцију selection_sort_desc(L) која сортира низ стратегијом бирања највећег елемента, тако да елементи низа буду поређани од највећег до најмањег елемента.

Задатак 5. Написати Пајтон функцију bubble_sort_desc(L) која сортира низ бабл-сорт стратегијом, али тако да елементи низа буду поређани од највећег до најмањег елемента.

Задатак 6. Написати Пајтон функцију svi_razliciti(L) која проверава да ли су сви елементи низа L различити.

Задатак 7. На такмичењу из информатике такмичари су радили по 4 задатка. Подаци о именима такмичара и о томе колико су поена за који задатак освојили дати су низом као у следећем примеру:

In [14]:

takmicenje = [
    ["Dejan", 25, 25, 0, 25],
    ["Mira", 25, 0, 20, 25],
    ["Milan", 0, 0, 10, 0],
    ["Milica", 25, 25, 25, 25],
    ["Nenad", 10, 0, 25, 5]
]

Написати Пајтон функцију rang_lista(T) која за овако представљене исписује одређује ранг-листу. На пример,

rang_lista(takmicenje)

треба да испише:

Milica 100
Dejan 75
Mira 70
Nenad 40
Milan 10

Задатак 8*. За два низа кажемо да је један пермутација оног другог ако се елементи првог низа могу испремештати тако да се добије други низ. Написати Пајтон функцију која за два дата низа утврђује да ли је један пермутација оног другог.

Задатак 9*. Написати Пајтон функцију која за два стринга утврђује да ли је први анаграм оног другог. На пример, стринг "I am Lord Voldemort" је анаграм стринга "Tom Marvolo Riddle". Обратити пажњу на то да прилико мпровере да ли је један стринг анаграм оног другог празнине и величина слова не играју никакву улогу!