# Sorting

## Bubble

시간복잡도는 $O(N^2)$이다.
공간복잡도는 $O(1)$

def bubbleSort(n, a):
cumulatedNumSwap = 0
for i in range(0, n):
numSwap = 0
for j in range(0, n-1):
if a[j] > a[j+1]:
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
numSwap += 1
cumulatedNumSwap += numSwap
if numSwap == 0:
break
return cumulatedNumSwap, a

if __name__ == "__main__":
a = [2, 1, 3, 1, 2]
numSwap, sortedA = bubbleSort(len(a), a)

print("Array is sorted in %d swaps."%numSwap)
print("First Element: %d"%sortedA[0])
print("Last Element: %d"%sortedA[-1])

## Insertion

Time Complexity:

• best: $O(n)$
• worst: $O(n^2)$
Space Complexity: $O(1)$

간단한 삽입정렬

def InsertionSort(input):
for i in range(len(input)-1):
for j in range(i+1,len(input)):
if(input[j] < input[i]):
input[i], input[j] = input[j], input[i]
return input
import random

def InsertionSort(input):

for idx, valueToInsert in enumerate(input):
# select the hole position where number is to be inserted
holePosition = idx

# check if previous no. is larger than value to be inserted
while holePosition > 0 and input[holePosition-1] > valueToInsert:
input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
holePosition = holePosition - 1

return input

if __name__ == "__main__":
A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
print(A)
InsertionSort(A)
print(A)

실행결과

[84, 59, 97, 41, 6, 93, 80, 62, 19, 37, 83, 24, 86, 95, 46]
[6, 19, 24, 37, 41, 46, 59, 62, 80, 83, 84, 86, 93, 95, 97]

## Selection

Time complexity: $O(n^2)$
Space complexity: $O(1)$

import random
def selectionSort(input):
for i in range(len(input) - 1):
# assume the min is the first element
idx_min = i
j = i + 1

# test against elements after i to find the smallest
while j < len(input):
if(input[j] < input[idx_min]):
# found new minimum; remember its index
idx_min = j
j = j + 1

if idx_min is not i:
# swap
input[idx_min], input[i] = input[i], input[idx_min]

return input

if __name__ == "__main__":
A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
print(A)
selectionSort(A)
print(A)

실행결과

[72, 10, 31, 7, 51, 11, 97, 9, 45, 54, 35, 26, 61, 55, 13]
[7, 9, 10, 11, 13, 26, 31, 35, 45, 51, 54, 55, 61, 72, 97]

## Merge

worst와 average모두 $O(n \log n)$인 엄청나게 좋은 알고리즘이다.
하지만 공간 복잡도는 $O(n)$을 메모리는 많이 사용 합니다.
그래도 기본적인 Dvide and Conquer를 적용한 알고리즘이기에 확실히 알고 넘어가면 좋다.

위키피디아에 나온 그림으로 나타낸 동작 방법은 아래와 같다.

$T(n)=2T\left(\frac{n}{2}\right)+n$
\begin{aligned} T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline &=4T\left(\frac{n}{4}\right)+n+n\newline &=…\newline &\approx O(\underbrace{n+n+…+n}_{\log n})\newline &=O(n\log n) \end{aligned}

코드는 아래와 같다.

import random

# Time Complexity O(nLogn)
# Space Complexity O(n)

def mergeSort(A):
### Base case ###

if len(A) <= 1:
return A

### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.
left = mergeSort(A[:int(len(A)/2)])
right = mergeSort(A[int(len(A)/2):])

### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
i, j, k = 0, 0, 0
while i<len(left) and j<len(right):
if left[i] < right[j]:
A[k] = left[i]
i += 1
else:
A[k] = right[j]
j += 1
k += 1
if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
while j<len(right):
A[k] = right[j]
j += 1
k += 1
elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
while i<len(left):
A[k] = left[i]
i += 1
k += 1
return A #마지막으로 정렬된 list를 리턴합니다.

if __name__ == "__main__":

A=[random.randint(1,100) for _ in range(10)]
print("unsorted List:")
print(A)
print("Sorted List:")
print(mergeSort(A))

실행결과

unsorted List:
[94, 22, 47, 26, 28, 29, 33, 53, 5, 54]
Sorted List:
[5, 22, 26, 28, 29, 33, 47, 53, 54, 94]

## Quick

분할 정복 알고리즘으로 Sorting한다.
Merge Sort와 다르게 분할 할 때 복잡하고 병합할 때는 복잡하지 않다.

평균 시간 복잡도는 $O(nlogn)$이다. 메모리 측면에서 좀 더 효율 적이다. 따라서 실제로 동작하는 속도가 좀 더 빠르다.
$$T(n)\approx n+2T(\frac{n}{2})$$

하지만, 최악의 상황인 이미 정렬이 완료된 List를 정렬할 경우 $T(n)=n+T(n-1)$으로 분할 된다.
왜냐하면 pivot이 가장 큰 값이라면 left side n-1개가 존재하고 이 부분을 계속 quick sort로 recursive하게 호출이 발생하기 때문이다. 결국 $O(n^2)$의 복잡도를 가진다.

Pivot이 Median값이라면 merge sort와 같은 복잡도를 가진다. 최악의 경우를 피하는 방법은 통상 random choice를 이용한다.

import random

# 아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, start, end):
if start < end:
p = partition(A, start, end)
quicksort(A, start, p - 1)
quicksort(A, p + 1, end)

# 이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, start, end):
pivot = end
wall = start
# 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
for i in range(start, end):
if A[i] < A[pivot]:
#swap
A[i], A[wall] = A[wall], A[i]
wall += 1
A[pivot], A[wall] = A[wall], A[pivot] # 마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
return wall

if __name__ == "__main__":
A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
print(A)
quicksort(A, 0, len(A)-1)
print(A)

#### 'Computer Science > Coding Interview' 카테고리의 다른 글

 Ch02 LinkedList  (0) 2017.08.11 2017.08.10 2017.08.06 2017.08.06 2017.07.31 2017.07.31