Sort

선택 정렬 (Selection sort)

주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬

def selectionSort(mylist):
	for i in range(len(mylist) - 1):
    	minIdx = i
        for j in range(i+1, len(mylist) - 1):
        	if mylist[j] < mylist[minIdx]:
            	minIdx = j
        temp = mylist[minIdx]
        mylist[minIdx] = mylist[i]
        mylist[i] = temp
	return mylist

버블 정렬 (Bubble Sort)

첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬

def bubbleSort(mylist):
	for i in range(len(mylist)-1, 0, -1):
    	for j in range(i):
        	if mylist[j] > mylist[j+1]:
            	tmp = mylist[j]
                mylist[j] = mylist[j+1]
                mylist[j+1] = tmp
    return mylist

삽입 정렬 (Insertion Sort)

삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법. i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입하는 방식

def insertionSort(mylist):
	for i in range(1, len(mylist)):
    	index = i
        while index > 0 and mylist[index-1] > mylist[i]:
        	mylist[index] = mylist[index-1]
            index -= 1
    mylist[index] = mylist[i]
    return mylist

병합 정렬 (Merge Sort)

배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 방식

def mergeSort(mylist):
	if len(mylist) <= 1:
    	return mylist
    mid = len(mylist) // 2
    left = mylist[:mid]
    right = mylist[mid:]
    L = mergeSort(left)
    R = mergeSort(right)
    i = j = 0
    result = []
    while i < len(L) and j < len(R):
    	if L[i] < R[j]:
        	result.append(L[i])
            i += 1
        else:
        	result.append(R[j])
            j += 1
    result += L[i:]
    result += R[j:]
    return result

퀵 정렬 (Quick Sort)

하나의 축(pivot)을 정해서 이 축보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시킴 그리고 왼쪽과 오른쪽에 해당하는 원소들에 대해 다시 축을 각각 정하고 마찬가지로 그 안에서 작은 값은 왼쪽에 큰값은 오른쪽에 위치시킴

def quickSort(mylist):
	if len(mylist) <= 1:
    	return mylist
    pivot = mylist[len(mylist) // 2]
    left, equal, right = [], [], []
    for num in mylist:
    	if num < pivot:
        	left.append(num)
        elif num > pivot:
        	right.append(num)
        else:
        	equal.append(num)
         return quickSort(left) + equal + quickSort(right)

Time complexity & Space complexity (순서대로 average, best, worst, space)
선택 정렬 -> O(N^2), O(N^2), O(N^2), O(N^2)
버블 정렬 -> O(N^2), O(N), O(N^2), O(N)
삽입 정렬 -> O(N^2), O(N), O(N^2), O(N^2)
병합 정렬 -> O(NlogN), O(NlogN), O(NlogN), O(NlogN)
퀵 정렬 -> O(NlogN), O(NlogN), O(N^2), O(NlogN)