Unit 3. 들어가기 앞서

 알고리즘 해보고싶어서 Coursera에 Introduction of Algo에서 과제가 pass 안되서 전전긍긍한지 언 6개월... inflearn 덕택에 원하던 것을 찾을 수 있게되어 감사 !  주로 강의를 듣고 그 내용을 python으로 구현해보면서 넘어가고 있습니다. 

 

 정렬 섹션에 들어가기 앞서 bubble, insertion, select, quick sort를 정리하고 가겠습니다.  10분이면 되니, 이번에 정리하고 이후엔 스킵!

import random
 
 
def bubbleSort(list):
    length = len(list)
    for i in range(0, length):
        for j in range(i + 1, length):
            if list[i] > list[j]:
                list[i], list[j] = list[j], list[i]
    return list
 
 
def selectionSort(list):
    length = len(list)
    for i in range(0, length):
        minIdx = i
        for j in range(i, length):
            if list[j] < list[minIdx]:
                minIdx = j
        list[i], list[minIdx] = list[minIdx], list[i]
    return list
 
 
def insertionSort(list):
    length = len(list)
    for i in range(0, length):
        j = 0
        while j < i:
            if list[j] > list[i]:
                list[j], list[j+1:i+1] = list[i], list[j:i]
            j = j +1
    return list
 
 
def quickSort(list):
    length = len(list)
    if length <= 1:
        return list
    else:
        pivot = list[length / 2]
        current = []
        less = []
        more = []
 
        for el in list:
            if el > pivot:
                more.append(el)
            elif el < pivot:
                less.append(el)
            elif el == pivot:
                current.append(el)
        return quickSort(less) + current + quickSort(more)
 
 
sorts = [bubbleSort, selectionSort, insertionSort, quickSort]
for sort in sorts:
    List = [random.randint(1, 10) for _ in xrange(10)]
    print "before : ", List
    print "after : ", sort,  sort(List)

basicSort.py