[ Algorithm - 9가지 정렬 알고리즘에 대하여(06/30~06/31) ]

혹시나 이미 정렬 알고리즘에 대해 공부해본적 있는 사람이라면 이 게시물을 읽기전에 자신이 알고있는 정렬 알고리즘 이름과 코드를 생각해보도록 하자. 몇개가 생각나는가? 최근에 알고리즘 공부를 한 사람이면 모든 알고리즘을 어떤 도움없이 코드를 작성할 수 있고 그에 따른 효율성도 구분할 수 있는 사람도 있을 것이다. 하지만, 전공자 4학년인 필자의 경우도, 오랜만에 다시 공부 겸 되짚어 생각해보니 선택, 삽입, 버블, 퀵 정렬 이렇게 4개를 기억했지만 코드로 바로바로 적을 수 있는 수준은 아니었다. 

 

예상하기로는 아마 다들 3~5가지 정도 말할 수 있을거라 생각한다. 왜일까?

 

우리는 너무나도 당연하게 알고리즘을 공부하는 이유는 효율성 때문이라는 것을 안다. 더 가독성이 좋고, 더 짧고, 더 빠르게 작동하고, 더 메모리는 적게쓰는 "효율적" 알고리즘을 이용하여 코드를 짜는 것, 그것이 궁극의 목표이기 때문이다. 그래서 다들 효율성이 가장 좋은 알고리즘만을 쓰기에 급급하다. 대충 이 알고리즘이 좋다더라 하면 그것만 사용하게 되는 것이다.

 

온라인 저지 사이트들도 살펴보면 대부분 문제 의도(시간제한, 메모리제한, 문제의 흐름 등)와는 관계없이 다들 가장 빠른 알고리즘을 넣어 한 코드로 거의 대부분의 정렬 알고리즘 문제를 풀곤한다. 또한 질문글에는 이러한 말도 올라온다. 백준을 어느정도 경험한 사람이면 보았을 문구라고 생각한다.

 

" 정렬 알고리즘에서 가장 빠른 퀵정렬을 썼는데도 시간초과가 뜹니다.. 고수분들 도와주세요!! "

 

분명 정렬 알고리즘 문제를 푸는 사람들은 학교수업, 유튜브나 인프런 등의 온라인 형식의 강의, 독학 등의 방법으로 공부를 다들 했을 것이다. 하지만 그럼에도 정렬문제를 풀때 틀렸습니다 뜨고, 시간초과가 나고 하는 이유는 몇 문법오류를 제외하고는 상황에 따라 다른 알고리즘을 써야하는데 그걸 놓쳤기 때문이라고 생각한다. 

 

물론, 그렇다고 해서 포스팅할 9가지의 알고리즘을 달달달 외우지는 말았으면 한다. 정말로 본인이 아래의 알고리즘들을 하나하나 설계하는 사람이라 생각하며 각 알고리즘에 본인의 생각들을 많이 담아보길 바란다. 알고리즘을 처음접하거나 기억이 나지 않는 사람들은 일단 그대로 써보자. 한줄씩 적어보며 왜 이렇게 했을까 생각해보는 것이 중요하다. 낯선 코드를 단순히 눈으로만 보게되면 전체적인 느낌만 잡힐뿐 그 알고리즘에 대해 이해를 하진 못한다. 그러니 꼭 써보고 본인입맛대로 가공해보도록 하자!

 

 

1. 선택정렬_Selection Sort
   • 가장 작은 값을 앞으로 보내는 알고리즘
   • 과정
     
     • (원본) 5  3  8  1  2  7
     • ( # 1 ) 1  3  8  5  2  7   => 최솟값 1과 5 변경
     • ( # 2 ) 1  2  8  5  3  7   => 최솟값 2과 3 변경
     • ( # 3 ) 1  2  3  5  8  7   => 최솟값 3과 8 변경
     • ( # 4 ) 1  2  3  5  8  7   => 최솟값 5가 자리에 잘 있으므로 넘어감
     • ( # 5 ) 1  2  3  5  7  8   => 최솟값 7과 8 변경
     • ( # 6 ) 1  2  3  5  7  8   => 마지막 자릿수는 이미 정렬이 된 상태이므로 끝까지 검사할 필요 없음
   • 코드

     • arr = [5,3,8,1,2,7]
       for i in range(len(arr)):
           min_index=i
           for j in range(i+1, len(arr)):
               if arr[min_index]>arr[j]:
                   min_index=j
           arr[i], arr[min_index] = arr[min_index], arr[i]
       print(arr)

   • 시간복잡도
     => 리스트의 크기가 n일 때, n + (n-1) + (n-2) + ... + 2 ≒ n(n+1)/2  →  O(n**2)
     
     
     
2. 삽입정렬_Insertion Sort
   • 데이터를 하나씩 확인하며 앞에 적당한 위치에 삽입하는 알고리즘
   • 과정
     
     • (원본) 5  3  8  1  2  7
     • ( # 1 ) 5  3  8  1  2  7   => 3은 5보다 작으므로 5 앞에 삽입
     • ( # 2 ) 3  5  8  1  2  7   => 8은 5보다 크므로 그대로 위치
     • ( # 3 ) 3  5  8  1  2  7   => 1은 3보다 작으므로 3 앞에 삽입
     • ( # 4 ) 1  3  5  8  2  7   => 2은 3보다 작으므로 3 앞에 삽입
     • ( # 5 ) 1  2  3  5  8  7   => 7은 8보다 작으므로 38 앞에 삽입
     • ( # 6 ) 1  2  3  5  7  8   => 정렬 완료
   • 코드

     • arr = [5,3,8,1,2,7]
       for i in range(1, len(arr)):
           for j in range(i,0,-1):
               if arr[j] < arr[j-1]:
                   arr[j], arr[j-1] = arr[j-1], arr[j]
               else:
                   break
       print(arr)

   • 시간복잡도
     => 리스트의 크기가 n일 때, 1 + 2 + 3 + ... + (n-1) ≒ n(n+1)/2  →  O(n**2)
     but) 거의 정렬된 상태라면 O(n)의 복잡도로 수행가능!
     
     
     
3. 버블정렬_Bubble Sort
   • 인접한 두 값을 비교하며 정렬하는 알고리즘
   • 과정
     • (원본) 5  3  8  1  2  7
     • ( # 1 ) 5  3  8  1  2  7   => 3은 5보다 작으므로 위치변경
     • ( # 2 ) 3  5  8  1  2  7   => 8은 5보다 크므로 그대로 위치
     • ( # 3 ) 3  5  8  1  2  7   => 1은 8보다 작으므로 위치변경  
     • ( # 4 ) 3  5  1  8  2  7   => 2은 8보다 작으므로 위치변경
     • ( # 5 ) 3  5  1  2  8  7   => 7은 8보다 작으므로 위치변경
     • ( # 6 ) 1  2  3  5  7  8   => 8이 첫번째로 큰 값으로 정렬됨
     • ( # 7 )          . . .           => 반복 
   • 코드

     • arr = [5,3,8,1,2,7]
       for i in range(len(arr)-1):
           for j in range(len(arr)-(i+1)):
               if arr[j] > arr[j+1]:
                   arr[j], arr[j+1] = arr[j+1], arr[j]
       print(arr)

   • 시간복잡도
     => 리스트의 크기가 n일 때, (n-1) + (n-2) + ... + 1 = n(n-1)/2  →  O(n**2)
     => 최악/평균/최선의 경우가 모두 O(n**2)로 동일해서 거의 사용되지 않는다.
     
     
     
4. 셀 정렬_Shell Sort
   • 부분 리스트로 나누어 정렬하고 합치는 알고리즘
   • 과정
     • (원본) 5  3  8  1  2  7
     • ( # 1 ) 5          1         => 리스트의 크기(6)/2 = 3 이므로 간격이 3인 부분리스트 생성
     • ( # 1 )     3           2    
     • ( # 1 )         8          7 
     • ( # 1 ) 1          5         => 부분리스트 정렬
     • ( # 1 )     2           3    
     • ( # 1 )         7          8 
     • ( # 1 ) 1  2  7  5  3  8 => 부분리스트 합치기
     • ( # 2 ) 1  2  3  5  7  8 => 3/2=1.5 -> 간격이 1인 부분리스트(는 결국 전체) 분할 후 정렬
   • 코드

     • arr=[5,3,8,1,2,7]
       h=len(arr)//2
       while h>0:
       	for i in range(h, len(arr)):
           	temp=arr[i]
               j=1-h
               while j>=0 and arr[j]>temp:
               	arr[j+h]=arr[i]
                   j-=h
               arr[j+h]=temp
           h//=2
       print(arr)

   • 시간복잡도
     => 
     
     
     
     
5. 병합정렬_Merge Sort
   • 한 리스트를 두 개의 균등한 크기로 분할하고 이를 정렬한 후 병합하는 알고리즘
   • 과정
     • (원본) 5  3  8  1  2  7
     • [ 5 3 8 ] [ 1 2 7 ]
     • [ 5 3 ] [ 8 ] [ 1 2 ] [ 7 ]
     • [ 5 ] [ 3 ] [ 8 ] [ 1 ] [ 2 ] [ 7 ]
     • [ 3 5 ] [ 8 ] [ 1  2 ] [ 7 ]
     • [ 3 5 8 ] [ 1 2 7 ]
     • [ 1 2 3 5 7 8 ]
   • 코드

     • def merge_sort(a):
       	n=len(a)
           if n<=1:
           	return a
           mid=n//2
           left = merge_sort(a[:mid]
           right = merge_sort(a[mid:])
           result=[]
           while left and right:
           	if left[0]<right[0]:
               	result.append(left.pop(0))
               else:
               	result.append(right.pop(0))
               while left:
               	result.append(left.pop(0))
               while right:
               	result.append(right.pop(0))
               return result

   • 시간복잡도
     => 병합 깊이 (log2의 N) * 정렬(N) => O(N*log2의N)
     ※ 정렬에 N만큼만 소요되는 이유는, 이미 정렬된 리스트를 합치는 과정이기 때문임
     => 퀵 정렬과 달리, 최악의 경우에도 O(N*log2의N)를 보장함
     
     
     
     
     
6. 퀵정렬_Quick Sort
   • 특정한 값을 기준으로 큰 숫자와 작은 숫자로 나누는 알고리즘
   • 과정
     • (원본) 5  3  8  1  2  7   => 가장 왼쪽의 숫자(5)가 pivot
     • ( # 1 ) 5  3  8  1  2  7   => pivot을 제외한 리스트에서 왼편은 pivot보다 큰값 / 오른편은 pivot보다 작은값을 선택해 바꾸되, 엇갈린 경우에는 작은값과 pivot을 바꿈
     • ( # 2 ) 5  3  2  1  8  7   => 1과 8이 엇갈린 상태 ( 왼편은 큰값, 오른편은 작은값을 찾는데 해당값이 서로를 넘어갔음 )
     • ( # 3 ) 1  3  2  5  8  7   => pivot이었던 5는 고정이되고, 왼쪽은 작은값, 오른쪽은 큰값으로 나뉘었음
     •                 . . .               => 고정값 기준 왼편, 오른편에 각각 위의 과정 반복수행
   • 코드

     • arr=[5,3,8,1,2,7]
       def quick_sort(arr, start, end):
       	if start>=end:
           	return
           pivot = start
           left = start+1
           right = end
           while left <= right:
           	while left <= end and arr[left] <= arr[pivot]:
               	left+=1
               while right >= end and arr[right] >= arr[pivot]:
               	right+=1
              	if left > right:
               	arr[left], arr[right] = arr[right], arr[left]
           quick_sort(arr, 0, len(arr)-1)
           print(arr)

   • 시간복잡도
     => 평균 n번의 비교 * log2의 n개의 분할 path = O(n*log2의n)
     but) 이미 전체 정렬된 리스트의 경우, 불균형 분할로 n개의 분할 path가 실행되므로 O(n^2) 
     
     
     
7. 힙정렬_Heap Sort
   • Heap구조(완전이진트리)를 이용해 정렬하는 알고리즘
   • 과정
     • (원본) 5  3  8  1  2  7
     • 
     • ④ : ③에서 부모노드 5가 자식노드 8보다 작기때문에 완전이진트리를 만족하지 않으므로 이를 바꾼다.
     • ⑧ : ⑦에서 부모노드 5가 자식노드 7보다 작기때문에 완전이진트리를 만족하지 않으므로 이를 바꾸면 모든 요소가 들어왔고 이는 완전이진트리(위는 max heap)라 명명할 수 있다. 
     • 이후 : max_heap이라면 루트가 가장 큰 값이므로 이를 마지막 노드와 바꾼뒤, 나머지를 다시 max_heap으로 변경하는 과정을 계속 거치면 정렬이 가능하다
   • 코드

     • import heapq
       def heap_sort(iterable):
       	h=[];result=[]
           for value in iterable:
           	heapq.heappush(h.value)
           for i in range(len(h)):
           	result.append(heapq.heappop(h))
           return result
       res = heap_sort([5,3,8,1,2,7])
       print(res)

   • 시간복잡도
     => 힙에 삽입 or 삭제 시간 (log2의 n) * 개수 (n) = O(n * log2의 n)
     but) 모든 데이터를 기준으로 Heapify알고리즘을 쓰지 않아도되므로 O(n)에 가까운 속도를 낼 수 있다.
     
     
     
8. 계수정렬_Count Sort
   • 범위조건이 있을 때 크기를 기준으로 개수를 세는 알고리즘
   • 과정
     • (원본) 5  3  3  1  2  2  4  3  1  5  2  3  1  1  2  4  3

     • 	1의 개수	2의 개수	3의 개수	4의 개수	5의 개수
       # 1	0	0	0	0	1
       # 2	0	0	1	0	1
       # 3	0	0	2	0	1
       	. . .
       # n	전체 개수 합 구함

   • 코드

     • arr=[5,3,3,1,2,2,4,3,1,5,2,3,1,1,2,4,3]
       cnt=[0]*(max(arr)+1)
       for i in range(len(arr)):
       	cnt[arr[i]]+=1
       print(cnt)

   • 시간복잡도
     => 데이터의 개수 (n) + 데이터 중 최댓값 (k) = O(n+k)   ※ 모든 데이터가 양의 정수인 상황에서!
     
     
     
9. 기수정렬_Radix Sort
   • 자릿수를 이용해 정렬하는 알고리즘
   • 과정
     • (원본) 391  582  50  924  134  8  192
     • ( # 1 ) 50  391  582  192  924  134  8
     • ( # 2 ) 08  924  134  50  582  391  192
     • ( # 3 ) 008  050  134  192  391  582  924
   • 코드
   • 시간복잡도