정렬 알고리즘 종류

정렬 알고리즘의 종류는 다음과 같다.

 

- Simple, slow

• Bubble sort
• Insertion sort
• Selection sort

- Fast

• Quick sort
• Merge sort
• Heap sort

- O(N)

• Radix sort

 

오늘은 Simple하고 slow한 특성을 갖는 selection sort와 bubble sort, Insertion sort에 대해 다뤄본다.

 

1. Selection sort

- 가장 큰수와 자리를 바꿔가면서 정렬하는 방법이다.

SelectionSort(A[],n)//배열 A[1...n]을 정렬한다.
{
	for last <- n downto 2 {
    	A[1...last] 중 가장 큰 수 A[k]를 찾는다;
        A[k] <-> A[last]; //A[k]와 A[last]의 값을 교환
    }
}

1) for 루프는 n-1번 반복

2) 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, ..., 2,1

3) 교환은 상수시간 작업

- 시간 복잡도: T(n)=(n-1)+(n-2)+...+2+1= O(n^2) 

    (이 때, 최악, 최선, 평균의 시간 복잡도의 경우가 n(n-1)/2 로 모두 같다.)

 

---

 

2. Bubble sort

- 최대값을 끝으로 모는 점은 Selection sort와 비슷하지만, 미세하게 다르다.

- 앞에서부터 크기를 비교해 자리를 바꾸는 과정을 거친다.

- 망을 이용해 크기가 다른 물고기를 모는 것과 같다고 비유한다.

- 최대값이 어디있든 간에 마지막으로 올 수밖에 없는 논리이다.

bubbleSort(A[],n)//배열 A[1,...,n]을 정렬한다.
{
	for last <- n downto 1 {
    	for i <- 1 to last-1 
        	if ( A[i] > A[i+1] ) then A[i] <-> A[i+1]; //교환
    } 
}

1) 첫번째 for루프는 n-1번 반복 (last의 개수는 n-1개)

2) 두번째 for루프는 n-1, n-2, ..., 2, 1번 반복

3) 교환은 상수시간 작업

- T(n)=(n-1)+(n-2)+...+2+1=O(N^2) = N(N-1)/2

  (이 때, 최악, 최선, 평균의 시간 복잡도의 경우가 n(n-1)/2 로 모두 같다.)

 

---

 

3. Insertion sort

- '어떤 것을 끼워넣으면서 정렬해보자'라는 아이디어로 시작한다.

- 그렇다면, 앞에서부터 끼워넣을 것을 정할 것인가, 뒤에서부터 끼워넣을 것을 정할 것인가?

    -> A. 작은 수를 검사하고 큰수는 뒤로 자리를 이동해야하기 때문에 뒤에서부터 검사해서 이동을 최소화하도록 한다.

insertionSort(A[],n)
{
	for i <- 2 to n {
    		A[1...i]의 적당한 자리에 A[i]를 삽입한다.}
 }

1) for 루프는 n-1번 반복 (맨 첫번째를 제외한 n-1개)

2) 삽입은 최악의 경우 i-1번, 최선의 경우 1번 검사하게 된다.

- 최악의 경우: T(n)=(n-1)+(n-2)+...+2+1=O(n^2)

---

병렬의 종류도 여러개가 있음을 알게되었다.