2. juni, 2017. Omer Ramić Obrazovanje
Uporedba vremenske efikasnosti algoritama sortiranja u jeziku python

Benchmark vremenske efikasnosti algoritama sortiranja.

Vrijeme potrebno za sortiranje liste od 7000 nasumično generisanih elemenata između vrijednosti od 0 do 9999 prikazano je u listingu koji možete vidjeti ispod:

5.9300 sekundi za BubbleSortAsc
5.6220 sekundi za BubbleSortDsc
1.6525 sekundi za SelectionSortAsc
1.6672 sekundi za SelectionSortDsc
4.0712 sekundi za InsertionSortAsc
4.0218 sekundi za InsertionSortDsc
2.4006 sekundi za ShellSortAsc
2.3620 sekundi za ShellSortDsc
0.0557 sekundi za MergeSortAsc
0.0505 sekundi za MergeSortDsc
0.0329 sekundi za QuickSortAsc
0.0306 sekundi za QuickSortDsc

1. Sortiranje zamjenom elemenata

Sortiranje zamjenom elemenata predstavlja najjednostavnije oblike sortiranja. U ove algoritme spadaju primjeri sortiranja Bubble sort i Selection sort. Ispod imamo primjere ovih algoritama.

  • Bubble sort (sortiranje zamjenom susjednih elemenata)
  • Selection sort (sortiranje odabirom najmanjeg elementa)

#Bubble sort algorithm ascending - python code
#by Omer Ramić
def BubbleSortAsc(lst):
    swapped = True
    sortedvalue=0
    while swapped:
        swapped = False
        sortedvalue+=1
        for i in range(0,len(lst)-sortedvalue):
            if lst[i]>lst[i+1]:
                lst[i], lst[i+1], swapped = lst[i+1], lst[i], True

#Bubble sort algorithm descending - python code
#by Omer Ramić
def BubbleSortDsc(lst):
    swapped = True
    sortedvalue=0
    while swapped:
        swapped = False
        sortedvalue+=1
        for i in range (0,len(lst)-sortedvalue):
            if lst[i]<lst[i+1]:
                lst[i], lst[i+1], swapped = lst[i+1], lst[i], True

#Selection sort algorithm ascending - python code
#by Omer Ramić
def SelectionSortAsc(lst):
    swapped = True
    counter=0
    while swapped:
        swapped = False
        min=lst[counter]
        for i in range (counter,len(lst)):
            if min>=lst[i]:
                min=lst[i]
                index=i
                swapped = True
        lst[counter], lst[index] = lst[index], lst[counter]
        counter+=1
        if counter==len(lst): break

#Selection sort algorithm descending - python code
#by Omer Ramić
def SelectionSortDsc(lst):
    swapped = True
    counter=0
    while swapped:
        swapped = False
        min=lst[counter]
        for i in range (counter,len(lst)):
            if min<=lst[i]:
                min=lst[i]
                index=i
                swapped = True
        lst[counter], lst[index] = lst[index], lst[counter]
        counter+=1
        if counter==len(lst): break

2. Sortiranje umetanjem elemenata

Sortiranje umetanjem elemenata se zasniva na ubacivanju elemenata u već sortirani niz. Primjeri ove vrste sortiranja su Insertion sort i Shell sort.

  • Insertion sort (jednostavno sortiranje umetanjem)
  • Shell sort (višestruko sortiranje umetanjem)

#Insertion sort algorithm ascending - python code
#by Omer Ramić
def InsertionSortAsc(lst):
    counter=0
    while counter<len(lst)-1:
        for i in range(counter+1,0,-1):
            if lst[i]<lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i]
            else: break
        counter+=1

#Insertion sort algorithm descending - python code
#by Omer Ramić
def InsertionSortDsc(lst):
    counter=0
    while counter<len(lst)-1:
        for i in range(counter+1,0,-1):
            if lst[i]>lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i]
            else: break
        counter+=1

#Shell sort algorithm ascending - python code
#by Omer Ramić
def ShellSortAsc(lst):
    gap=len(lst)//2
    while gap>0:
        for i in range(0, len(lst)-gap):
            if lst[i]>lst[i+gap]:
                lst[i], lst[i+gap] = lst[i+gap], lst[i]
                for j in range(i-gap,-1,-gap):
                    if lst[j]>lst[j+gap]:
                        lst[j], lst[j+gap] = lst[j+gap], lst[j]
        gap//=2

#Shell sort algorithm descending - python code
#by Omer Ramić
def ShellSortDsc(lst):
    gap=len(lst)//2
    while gap>0:
        for i in range(0, len(lst)-gap):
            if lst[i]<lst[i+gap]:
                lst[i], lst[i+gap] = lst[i+gap], lst[i]
                for j in range(i-gap,-1,-gap):
                    if lst[j]<lst[j+gap]:
                        lst[j], lst[j+gap] = lst[j+gap], lst[j]
        gap//=2

3. Rekurzivno sortiranje - zavadi pa vladaj tehnikom (divide and conquer)

Rekurzivni algoritmi predstavljaju one algoritme kod kojih funkcije pozivaju same sebe. U ovu grupu ubrajamo Merge sort i Quick sort.
Merge sort (sortiranje spajanjem)

  • potrebna veća količina memorije
  • kreiranje zasebnih listi pri svakom prolazu koje se nakon sortiranja spajaju

Quick sort (brzo sortiranje)

  • ne koristi dodatnu memoriju
  • elementi liste se direktno sortiraju unutar proslijeđene liste

#Merge sort algorithm ascending - python code
#by Omer Ramić
def MergeSortAsc(lst):
    half = len(lst)//2
    left_half, right_half = lst[:half], lst[half:]
    if len(left_half) > 1: left_half = MergeSortAsc(left_half)
    if len(right_half)> 1: right_half= MergeSortAsc(right_half)
    sorted_list = []
    while left_half and right_half:
        if left_half[0] <= right_half[0]:
            sorted_list.append(left_half.pop(0))
        else:
            sorted_list.append(right_half.pop(0))
    return sorted_list + (left_half or right_half)

#Merge sort algorithm descending - python code
#by Omer Ramić
def MergeSortDsc(lst):
    half = len(lst)//2
    left_half, right_half = lst[:half], lst[half:]
    if len(left_half) > 1: left_half = MergeSortDsc(left_half)
    if len(right_half)> 1: right_half= MergeSortDsc(right_half)
    sorted_list = []
    while left_half and right_half:
        if left_half[0] >= right_half[0]:
            sorted_list.append(left_half.pop(0))
        else:
            sorted_list.append(right_half.pop(0))
    return sorted_list + (left_half or right_half)

#Quick sort algorithm ascending - python code
#by Omer Ramić
def QuickSortAsc(lst,pivot,high):
    index=pivot+1
    if index>high: return
    border=pivot
    while index<=high:
        if lst[index]<=lst[pivot]:
            border+=1
            lst[index], lst[border] = lst[border], lst[index]
        index+=1
    if lst[pivot]>lst[border]:
        lst[pivot], lst[border] = lst[border], lst[pivot]
    QuickSortAsc(lst,pivot,border-1)
    QuickSortAsc(lst,border+1,index-1)

#Quick sort algorithm descending - python code
#by Omer Ramić
def QuickSortDsc(lst,pivot,high):
    index=pivot+1
    if index>high: return
    border=pivot
    while index<=high:
        if lst[index]>=lst[pivot]:
            border+=1
            lst[index], lst[border] = lst[border], lst[index]
        index+=1
    if lst[pivot]<lst[border]:
        lst[pivot], lst[border] = lst[border], lst[pivot]
    QuickSortDsc(lst,pivot,border-1)
    QuickSortDsc(lst,border+1,index-1)