Sorting Algorithm in Python

Due to my research works, I make myself familiar with Python. Python is a programming language. It is easy to use and human-understandable, especially it has so many tools for analyzing data. Anyway, I am also new in learning Python, I use several online learning resources to deepen my understanding in Python. Here is one of my favorite learning resource: http://interactivepython.org. You need to create an account and log in whenever you want to learn something. Once you are logged in, it will keep track your last reading chapter. Awesome, isn’t it?

I read sorting chapter in two consecutive weeks. Haha. I know, it is too long. I do really need to do more practice to gain more power and be stronger, otherwise, I will become weaker each day😦. Well, any of computer science students must have learned about sorting algorithm. The most favorite sorting algorithm is QuickSort because it is less usage space and has better big-O analysis than others. I hope you are still feeling well after reading this post😄.

Bubble Sort

bubble-sort-example-300px
def diyBubbleSort(alist):
    for iterasiEksternal in reversed(range(len(alist))):
        print iterasiEksternal
        for nilaiInternal in range(iterasiEksternal):
            if alist[nilaiInternal] > alist[nilaiInternal+1]:
                temp = alist[nilaiInternal]
                alist[nilaiInternal] = alist[nilaiInternal+1]
                alist[nilaiInternal+1] = temp
            print alist

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
diyBubbleSort(blist)

Selection Sort

selection-sort-animation
def diySelectionSort(alist):
    # yang udah di-swap ngga usah dibandingkan lagi,
    # urutkan dari kecil ke besar
    # goalnya : [17,20,26,31,44,54,55,77,93]

    for i in reversed(range(len(alist))):
        pointerOfMin = 0
        for j in range(i):
            if alist[pointerOfMin] > alist[j+1]:
                pointerOfMin = pointerOfMin
            else:
                pointerOfMin = j + 1
            print "   ",alist


        # mau tuker 17 dan 20
        temp = alist[pointerOfMin] #17
        alist[pointerOfMin] = alist[j+1]
        alist[j+1] = temp
        print "\n"

alist = [54,26,93,17,77,31,44,55,20]
diySelectionSort(alist)

Insertion Sort

insertion-sort-example-300px
def diyInsertionSort(alist):
    for i in range(0, len(alist)-1, 1):
        currentPos = i
        for j in reversed(range(len(alist[:i]))):
            print "nilai j : ", j
            print alist[currentPos], ">", alist[j]
            print "posisi :", currentPos, ">", j
            if alist[currentPos] < alist[j]:
                # shift position
                temp = alist[currentPos] # 4
                alist[currentPos] = alist[j] # 7
                alist[j] = temp #4
                currentPos = j
        print alist

alist = [15, 5, 4, 18, 12, 19, 14, 10, 8, 20]
diyInsertionSort(alist)

Shell Sort

shell-sort-demonstration

<pre># improves the insertion sort by breaking the original list into a number of smaller sublist

def diyShellSort(alist, gap = None):
    # pembagi didapat dari faktor pembagi len(alist)
    # misal, 10 maka fpb nya 2, 5, 1

    # kalo gap ada isinya
    if gap :
        print gap
        diyGap(alist, gap)
    else:
        # kalo gap ga ada isinya, jalankan ini
        i = len(alist)
        hasilBagi = []
        while i > 1:
            i = i // 2
            hasilBagi.append(i)

        for i in hasilBagi:
            print i
            diyGap(alist, i)

    #return hasilBagi

def diyGap(alist, gap):
    # prinsipnya adalah:
    # breakdown and conquer dengan nilai yang ada pada setiap breakdown-an

    for i in range(0, gap, 1):
        # print "   ", i

        if gap == len(alist):
            gap = 1

        # for sampe sejumlah pembagi
        for j in range(i, len(alist), gap):
            # print "      ", j

            for k in range(j+gap, len(alist), gap):
                # print "         ", k

                # j = minPointer
                # k = currentPointer
                if alist[j] > alist[k]:
                    # tukar
                    # ketika nilai alist[j] lebih besar dari alist[k]
                    temp = alist[j]
                    alist[j] = alist[k]
                    alist[k] = temp
    print alist

alist1 = [54, 26, 93, 17, 77, 31, 44, 55, 20, 21]
alist2 = [5, 16, 20, 12, 3, 8, 9, 17, 19, 7]
# diyShellSort(alist2, 3)
diyShellSort(alist2)

Merge Sort

merge-sort-example-300px
# divide and conquer
# recursive algorithm that continuously splits a list in half
# first: the list is splitted into halves
# second :
# second: process in the merge

# kunci dari recursive adalah: kerjakan dengan input yang paling kecil
# kalau berhasil, baru diulang ke input yang lebih besar

# non-recursive merge sort

hasil = []
def recursivebagi(x):
    hasil.append(x)
    x = x // 2

    if x > 1:
        recursivebagi(x)

    return hasil

# recursivebagi(20)

def diyMergeSort(alist):
    division = recursivebagi(len(alist))
    # print division
    for i in reversed(range(len(division))):
        print division[i]

        start = 0
        gap = division[i]
        for j in range(start, len(alist), gap):
            print "   ", j
            for k in range(j,j+gap-1, 1):
                print "      ", k
                for l in range(k+1, j+gap, 1):
                    if alist[k] > alist[l]:
                        # print "      tukar"
                        temp = alist[k]
                        alist[k] = alist[l]
                        alist[l] = temp
                        print "      ", alist
            # start += finish
            # finish += finish
    print alist

alist = [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40]
diyMergeSort(alist)

Quick Sort

quicksort-example
def diyQuickSort(alist):
    if len(alist) > 1:
        print "lebar : ", len(alist)
        pivot = alist[0]
        smallerAlist = []
        greaterAlist = []
        equalAlist = []
        # print len(alist)
        for i in range(0, len(alist), 1):
            # print i
            print pivot , ">", alist[i]
            if pivot > alist[i]:
                smallerAlist += [alist[i]]
            if pivot == alist[i]:
                equalAlist += [alist[i]]
            if pivot < alist[i]:
                greaterAlist += [alist[i]]

            print smallerAlist
            print equalAlist
            print greaterAlist
            newlist = diyQuickSort(smallerAlist) + equalAlist + diyQuickSort(greaterAlist)
        return newlist
    else:
        return alist
        # print "newalist ", newalist

# alist = [54,26,93,17,77,31,44,55,20]
alist =  [14, 17, 13, 15, 19, 10, 3, 16, 9, 12]
print diyQuickSort(alist)
# print sort(alist)

2 thoughts on “Sorting Algorithm in Python

  1. waah, sedikit mumet pas baca krn sudh jarang coding pake algoritma yg diajarkan di kelas.

    anyway, good post (y) sekedar saran kalau blogpostnya ditulis dlm bhs inggris, lebih bagus lagi kalau variable name dan commentnya dalam bhs inggris juga.

    ya meski saya nulis komentar ini dalam bahasa indonesia😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s