[c++] 정렬/솔팅 알고리즘 정리(삽입정렬, 선택정렬, 버블솔트, 퀵솔트, 병합정렬)

정렬 알고리즘

Sorting algorithm에는 흔히 5가지를 사용한다.

1. 삽입정렬(Insertion sort) :O(n^2)

2. 선택 정렬(Selection sort) : O(n^2)

3. 버블솔트(Bubble sort) : O(n^2)

4. 퀵솔트(Quick sort) : O(nlgn)

5. 머지솔트(Merge sort) : O(nlgn)

자, 이제 이 중에 원하는 알고리즘을 사용해보자. ʘ‿ʘ

참고로, 이번 포스팅에는 알고리즘 방법과 시간복잡도 그리고 슈도 코드만 써놓을 것이다. 소스코드를 복붙하여 가져다 쓰는 방법보다, 방법만 숙지하고 직접 적용해가며 배우는 것이 자신에게 훨씬 좋다. 사실 본인이 복붙해서 매번 쓸까봐도 있지만...

 

삽입 정렬(Insertion sort)

출처: 위키백과

 삽입 정렬은 2번째 인덱스부터 시작한다. 그리고 내 앞에 있는 애들과 비교한다고 생각하면 된다.

'삽입' 정렬인 만큼 내가 내 앞에 있는 애들과 비교했을 때 작으면, 그 사이에 끼어 들어가면 된다. 

for i = 1 to n:
    a[0]부터 a[i - 1]까지 a[i]와 차례로 비교하여 a[i]의 값은 a[j]와 a[j+1]사이에 있다고 하자.
    a[j] <= a[i]
    a[i] < a[j+1]
    a[i]를 a[j]와 a[j+1] 사이에 삽입하고 j+1부터는 뒤로 한칸씩 민다.

 

선택 정렬(Selection sort) 

출처: 위키백과

 이번에는 gif로 보면 되겠다. 사실 gif보다 의사코드가 더 이해하기 쉽다.

'선택' 정렬인 만큼 0 to n-1까지 흝으면서 가장 작은 값을 찾고, 그 값을 현재 인덱스에 있는 값과 맞바꾼다.

for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.

버블 솔트(Bubble sort) 

출처:Parker

버블 솔트는 버블버블하게 옆에 있는 아이와만 연관된다. 옆에 있는 아이와 비교해서 솔트하고, 끝에서 부터 고정을 시켜 모든 요소가 고정이 될 때까지 반복하는 알고리즘이다.

for i = 0 to n:
  for j = 0 to n-i:
      if a[j] < a[j+1]
		swap(a[j], a[j+1])

퀵 솔트(Quick sort) 

출처: Heee's Development Blog

퀵솔트는 기준점(pivot)을 정한 뒤 이를 기준으로 pivot보다 작은 값은 앞에 큰 값은 뒤에 놓는 방법이다. 그리고 점점 작아지는 비교 리스트가 없어질 때까지 반복한다. 이때! pivot을 어떻게 세울 것인가??

보통 리스트 맨 앞의 값을 기준점으로 잡는다. 예시에서는 첫번째 기준점은 5, 두번째 기준점은 1과 9가 되겠다.

sort(list):
	if list의 크기가 0이거나 1이면 return.
    
	pivot = list[0];
	for i = 1 to n:
		if pivot >= list[i]: pivot 앞으로 이동. 
		if pisot < list[i]: pivot 뒤로 이동.
	sort(list[0...pivot])
	sort(list[pivot...n])
	완성된 리스트 합치기.
    
        
main:
	sort(list)
    

 

머지 솔트(Merge sort) 

출처: Heee's Development Blog

머지 소트는 나누고 나누고 다 나누면 다시 순서대로 합병하는 방법이다. 나누고 다시 합병하는 과정은 퀵소트와 비슷해보이지만, 기준점의 유무가 가장 큰 차이점이라는 것.

merge:
    list1과 list2의 원소들을 하나씩 비교해서 순서대로 merge 한다.


divide:
    mid = (low+high)/2
    list[low...mid]
    list[mid...high]
    if list의 크기가 0이거나 1일 때 merge 시작.