손가락놀이터

Abstract

정렬에는 많은 종류의 정렬이 있지만 해당 포스트에서는 아래 6가지 정렬을 정리하려고 합니다.

1. $O(n^2)$
   • Bubble Sort, 거품 정렬
   • Selection Sort, 선택 정렬
   • Insertion Sort, 삽입 정렬
2. $O(nlogn)$
   • Quick Sort, 퀵 정렬
   • Merge Sort, 병합 정렬
   • Heap Sort, 힙 정렬

해당 글은 gyoogle 님 github의 tech-interview-for-developer를 기반으로 작성합니다.

코드는 파이썬으로 작성하려 노력합니다.

거품 정렬 (Bubble Sort)

Abstract

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다. 아래는 위키백과에서 나오는 무작위 배열 수의 정렬 예시입니다.

Process

1.  1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를..... 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다.
2.  1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외도, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정령에서 제외되는 데이터가 하나씩 늘어납니다.

Python Code(Ascending)

def bubbleSort(arr:list):
	
    for i in range(len(arr)):				# 1.
    	for j in range(len(arr)-i-1):			# 2.
        	if arr[j] > arr[j+1]:			# 3.
            	arr[j], arr[j+1] = arr[j+1], arr[j]
    
    return arr

1.  제외될 원소의 갯수를 의미합니다. 1회전이 끝났을 때, 배열의 마지막에 가장 큰 원소가 위치하므로 1씩 증가합니다.
2.  비교할 원소의 idx를 지정하는 for문입니다. 1회전이 끝났을 때, 마지막 값 1개가 고정, 2회전이 끝났을 때, 마지막 값 2개가 고정.... 이므로 전체 길이에서 i를 뺀 만큼 반복을 실행합니다.
3. 현재 idx가 가르키고 있는 2개의 값을 비교합니다. 위의 코드는 오름차순 정렬이므로 현재 원소가 다음 원소보다 큰 경우 서로 자리를 교환합니다.

시간 복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + ....... + 2 + 1 -> n(n-1)/2 이므로 O(n^2)입니다. 또한, Bubble Sort는 정렬이 돼있던 안돼 있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)로 동일합니다.

코드를 활용해 더 자세하게 계산해보자.

def bubbleSort(arr:list):
	
    for i in range(len(arr)):				# 1.
    	for j in range(len(arr)-i-1):			# 2.
        	if arr[j] > arr[j+1]:			# 3.
        		arr[j], arr[j+1] = arr[j+1], arr[j]	# 4.
    
    return arr # 5.

먼저 arr의 갯수를 n으로 생각한다.

1. for i in range(len(arr)) -> n번 반복
2. for j in range(len(arr)-i-1) -> n번, n-1, n-2 ......, 2, 1번 반복 -> 최대 n번 반복
3. 1번 실행하므로 O(1)
4. 1번 실행하므로 O(1)
5. 이를 계산해보면 $\Sigma^n \Sigma^n {(O(1) + O(1))}$
6. 결과적으로 $O(n^2)$

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

장점 & 단점

1. 장점
   • 구현이 매우 간단하고, 소스코드가 직관적이다
   • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. -> 제자리 정렬(in-place sorting)
   • 안정 정렬(stable Sort)이다.
2. 단점
   • 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로, 굉장히 비효율적이다.
   • 정렬돼있지 않은 원소가 정렬됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

추가적으로 생각해보는 왜?

Bubble sort와 Selection sort가 유사하다고 하는데 어떤 점에서 유사할까?