sorting algorithm

1. 버블 정렬 ( Bubble Sort )

- 과정

인접한 두 개의 데이터를 비교해가며 정렬을 진행한다.

가장 크기가 큰 값 ( 또는 정렬의 우선 순위가 가장 낮은 값 ) 을 맨 뒤로 보내고,

그 다음으로 크기가 큰 값을 맨 뒤에서 두번째로 보내고.. 이 과정을 반복한다.

- 시간 복잡도

데이터의 수가 n 개일 때,

제일 처음 비교 횟수 : n-1

그 다음 비교 횟수 : n-2

(n-1) + (n-2) .... + 2 + 1 = n(n-1)/2 =  O(n⌒2)

2. 선택 정렬 ( Selection Sort )

- 과정

가장 크기가 작은 값 ( 또는 정렬의 우선 순위가 가장 큰 값 ) 을 선택해서 가장 왼쪽으로 이동시키고,

원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다.

- 시간 복잡도

데이터의 수가 n 개 일때, ( 배열이니까 0~ n-1 )

제일 처음 비교 횟수: 1에서 n-1까지 보니까 n-1

그 다음 비교 횟수: 2에서 n-1 까지 보니까 n-2

(n-1) + (n-2) .... + 2 + 1 = n(n-1)/2 =  O(n⌒2)

** 버블 정렬과 시간 복잡도는 똑같지만, 데이터의 이동 횟수에는 차이가 있다.

데이터의 교환이 이뤄질 때

temp = A;

A = B;

B = temp;

이므로, 총 3번의 연산이 일어난다.

선택 정렬의 경우 안쪽 for문 바깥쪽에서 이 연산이 일어나고, 버블 정렬의 경우  안쪽 for문의 안쪽에서 이 연산이 일어난다.

따라서 데이터 이동 횟수의 시간 복잡도는, 선택 정렬은 O(n)이고 버블 정렬은 O(n⌒2) 이다.

** 그러나 버블 정렬의 경우 최선의 경우에는 단 한번의 데이터 이동도 발생하지 않으나, 선택 정렬의 경우 최악이나 최선이나 데이터 이동이 같다.

따라서 버블 정렬이나 선택 정렬이나 우열을 가릴 수 없다.

3. 삽입 정렬 ( Insertion Sort )

- 과정

정렬이 완료된 부분과 완료되지 않은 부분으로 나눈 후, 정렬 안된 데이터를 정렬 된 데이터의 특정 위치에 삽입한다.

정렬이 완료된 영역 다음의 데이터가 정렬해야할 데이터이므로,

만약 정렬해야할 데이터의 위치가 k 라면,  k-1 위치의 데이터와 비교하여 자신이 더 작으면 k-1의 데이터를 k 위치로 이동시킨다.

다음 k-2의 데이터와 비교하고, 만약 k-2보다 자신이 크다면  k-1의 위치에 정착한다.

= 데이터를 한 칸씩 뒤로 밀면서 내가 들어갈 자리를 찾는다.

- 시간 복잡도

최악의 경우 모든 데이터를 보고 모든 데이터를 비교하며 이동시켜야하므로

1 + 2 + .... + (n-1) = n(n-1)/2 =  O(n⌒2)

4. 힙 정렬 ( Insertion Sort )

- 과정

힙의 루트 노드에 저장된 값이 가장 커야 한다는 특성을 힙의 루트 노드에 저장된 값이 정렬 순서상 가장 앞선다는 특징을 갖도록 하여 정렬에 이용한다.

데이터를 모두 힙에 넣은 후, 히벵서 다시 데이터를 꺼낸다.

- 시간 복잡도

힙의 데이터 저장 시간 복잡도와 삭제 시간 복잡도는 O(log n)이다.

n개의 데이터가 있을 때 총 n 개의 데이터를 삽입 및 삭제해야 하므로 O(n log n)이다.

5. 병합 정렬 ( Merge Sort )

- 과정

데이터가 1개만 남을 때 까지 분할을 한다.

다시 데이터를 합칠 때, 우선순위를 고려하여 묶는다.

- 시간 복잡도

데이터의 수가 n 개일때, 각 병합 단계마다 최대 n번의 비교연산이 진행된다.

데이터가 8개일 때, 병합은 3번 진행되고, 16개일때, 병합은 4회 진행된다.

병합 과정의 횟수는 log n 이다.

따라서 시간 복잡도는 O(n log n) 이다.

6. 퀵 정렬 ( Quick Sort )

- 과정

가장 처음 값을 피벗으로 잡는다.

a : 왼쪽에서 오른쪽으로 피벗보다 큰 값을 만날때까지 이동하고,  

b: 오른쪽에서 왼쪽으로 피벗보다 작은값을 만날때까지 이동한다. 

그리고 그 값을 교환한다. 만약 a와 b가 교차하게 되면 ( a>b)가 되면 탐색을 멈추고, b와 피벗을 교환한다.

-> 이 과정을 통해  피벗의 왼쪽에는 피벗보다 작은 값들만, 오른쪽에는 피벗보다 큰 값들만 있게 된다.

그리고 피벗을 중심으로 왼쪽과 오른쪽을 나누어 재귀적으로 진행한다.

사실 피벗이 가장 중간값이라면 제일좋은 성능을 보일 수 있다. 만약 이미 잘 정렬되있는 배열을 돌린다면, 1부터 n-1까지의 값들이 순서대로 피벗이 되어 정렬을 하게 된다.

중간 값을 찾는 알고리즘이 있긴 하지만 오히려 그거 때문에 성능이 더 나빠져서 실제로는 안쓴다고 한다.

그냥 세 개 데이터를 추출하여 그 중에 중간 값을 피벗으로 선택하는 것이 ....

- 시간 복잡도

하나의 피벗이 자신의 자리를 찾아가기 위해 n번의 비교 연산이 진행된다.

그리고 분할은 총 log n 번 진행된다. ( 피벗이 중간값인 경우 )

따라서 시간 복잡도는 O(n log n)

** 피벗이 중간 값일 때를 최선의 경우라 생각할 수 있지만, 퀵 정렬의 경우 예외적으로 중간에 가까운 피벗을 선택하는 방법을 적용하여 최선에 가까운 성능을 평균적으로 보인다고 한다. 

** 병합 정렬과 시간 복잡도는 같지만, 별도의 메모리 공간을 필요로 하지 않으므로 실제로 가장 빠르다.

7. 기수 정렬 ( Radix Sort )

- 소개

기수 정렬은 비교 연산을 하지 않고 데이터를 정렬할 수 있다. 그러나 데이터의 길이가 제한적일 수 있다.

간단하게 생각해보면, 0,8,3,5,4의 데이터를 비교한다면, 크기 10짜리의 배열의 인덱스의 그 값을 넣고 ( arr[8] = 8 이런식 ) 그냥 배열을 순차적으로 출력하면 되는 것...

하지만 이를 좀 바꾸어서, 3자리 수의 데이터 비교를 5개의 버킷(공간)을 가지고 정렬할 수 있다. 이를 LSD 기수 정렬(Least Significant Digit)라고 하며, 덜 중요한 자리 수인 일의자리수 부터 정렬을 진행해 나간다는 것이다.

- 과정

데이터: 134, 224, 232, 122

일의자리수 기준으로 하여 순서대로 버킷에 넣는다.

버킷 2: 122, 232 ( -> 넣은 순서)

버킷 5: 224, 134

현재 상태 : 232, 122, 134, 224 ( 꺼낼때는 먼저 넣은 것부터 )

십의 자리수 기준으로 버킷에 넣는다.

버킷2: 224, 122

버킷3: 134, 232

현재 상태 : 122, 224, 232, 134

백의 자리수 기준으로 버킷에 넣는다.

버킷 1: 134, 122

버킷 2: 232, 224

현재 상태 : 122, 134, 224, 232

** MSD 기수 정렬 (Most Significat Digit)은 가장 중요한 자리수, 큰 자리수부터 정렬을 진행한다. 이 정렬의 가장 큰 장점은 중간에 정렬이 완료될 수 있으므로 끝까지 가지 않아도 된다. 그러나  중간에 정렬이 완료되었는데도 불구하고 끝까지 정렬할 시 정렬이 제대로 되지 않는다. 따라서 중간에 데이터를 점검해야하는 상황이 발생한다. ( 모든 데이터에 일괄적 과정을 거칠 수 없다 ) 따라서 이를 해결할 알고리즘을 필요로 하는데 이게 더 시간이 오래 걸릴 수 있음...

- 시간 복잡도

비교연산이 아닌 데이터의 삽입과 추출이 핵심 연산이다.

가장 긴 데이터의 길이만큼 반복하고, 정렬대상의 수 만큼 버킷에 데이터를 삽입하고 추출한다.

데이터의 길이(l) x 데이터의 수(n) = O(ln) = O(n)