Sorting
개념
- 배열 내의 요소를 크기에 따라 오름차순 또는 내림차순 정렬하는 것
- 특정 요소를 검색하고자 할 때 정렬된 배열일 경우 효율성이 높아지는 경우가 있어 효율성에 있어 매우 중요함
- 데이터에 따라 효율적인 정렬 방법을 사용해야하먀 데이터에 따라 효율적인 정렬 방법을 사용해야함
구분
효율성 & 복잡도에 따른 구분
간단하지만 효율적이지 않은 정렬
- Insertion Sort
- Selection Sort
- Bubble Sort
복잡하지만 효율적인 정렬
- Quick Sort
- Heap Sort
- Merge Sort
- Radix Sort
메모리 공간에 따른 구분
Internal Sort
External Sort
- 정렬시 대부분은 외부 저장 공간에 있고 일부분만 메모리에 올라감
Stability에 따른 구분
Stable Sort
- 같은 값을 가진 요소의 순서가 기존 상태와 비교해 바뀌지 않는 것을 보장
- Insertion sort, Bubble sort, Merge sort가 해당
Unstable Sort
- 정렬 수행 후 기존 상태와 비교해 같은 값을 가진 요소의 순서가 바뀔 수 있음
(반드시 바뀌는 것은 아님)
- Stable Sort를 제외한 나머지
1. Selection Sort
개념
- 정렬된 요소를 담을 빈 리스트
left와 정렬되지 않은 상태의 리스트 right를 이용
right를 순회하며 규칙에 따라 요소를 선택해 left에 추가left에 요소가 추가될 때마다 right의 요소가 하나씩 줄어듦right 리스트가 빌 때 정렬이 완료됨리스트가 빌 때 정렬이 완료됨
구현
- 실제 구현시에는
left, right라는 2개의 리스트를 사용할 필요가 없음
- 하나의 배열을 순회하며 자리를 바꾸는 것으로 정렬을 실시하므로 추가적인 메모리 공간을 필요로 하지 않는
Internal Sort임
void selectionSort (int list[], int n)
{
int i, j, least;
for( i=0 ; i<n-1 ; i++) {
least = i;
for(j=i+1; j<n; j++)
if(list[j]<list[least]) least = j;
swap(list[i], list[least]);
}
}
- 주어진 코드에서는 오름차순 정렬을 실시
- 0번 인덱스의 값에서부터 시작해 이후에 있는 배열 요소를 이중 반복문으로 순회하며 최소 값의 인덱스를 찾아
Swap()실시
- 실행시
n-1 + n-2 + ... + 2 + 1 횟수의 비교를 실시하므로 전체 n(n-1)/2 비교 연산 실시
최종적으로 O(n^2)의 시간 복잡도를 가짐
Swap()과정에서도 3번의 이동이 있으나 전체 시간 복잡도는 바뀌지 않음
정리
- Selection Sort는 배열에서 가장 작은(또는 가장 큰) 요소를 찾아 정렬
- 순회 과정에서 최솟값 탐색과 자리 바꾸기 과정이 실행
- 자리를 바꾸는 과정은 횟수가 적지만 비교 과정이 많이 요소가 많아질수록 비효율적
- Unstable & Internal Sort
2. Insertion Sort
개념
- 정렬되지 않은 요소를 반복적으로 정렬될 위치에 삽입
- Selection Sort처럼 추가적인 메모리 공간을 필요로 하지 않음
구현
void insertionSort (int list[], int n )
{
for(int i=1; i<n; i++){
int key = list[i];
int j;
for(j=i-1 ; j>=0 && list[j] > key ;j--)
list[j+1]=list[j]; // Shift element to the right
list[j+1]=key;
}
}
예시
4 2 3 1 6 5 - key : 2
0번 인덱스에서부터 탐색
[4] 2 3 1 6 5 - j는 0이므로 0번 인덱스에서 2보다 큰 요소 확인 ([] : 탐색 범위)
4 4 3 1 6 5 - 1칸 뒤로 미루기
2 4 3 1 6 5 - 0번 위치에 기존 key 값 저장2 4 3 1 6 5 - key : 3
[2 4] 3 1 6 5 - 탐색 범위에서 4를 이동해야함을 발견
2 4 4 1 6 5 - 1칸 뒤로 미루기
2 3 4 1 6 5 - j가 0이므로 1번 위치에 key 값을 삽입2 3 4 1 6 5 - key : 1
[2 3 4] 1 6 5 - j는 2이므로 2~0번 위치를 탐색
2 2 3 4 6 5 - 0~2번 모두 한 칸씩 뒤로 이동
1 2 3 4 6 5 - j는 -1이므로 0번 위치에 key 값을 삽입
...
key 값을 지정한 후 key의 위치 앞에서부터 탐색해 더 큰 값을 한칸 뒤 이동한 후 빈 자리에 key 값을 다시 입력- 이미 정렬된 상태일 경우
O(n)의 시간 복잡도를 가짐
(순서대로 값을 비교하기만 하고 미루는 과정이 없기 때문)
- 최악의 경우 전체 비교 횟수는
n(n-1)/2로 O(n^2)의 시간복잡도를 가짐
정리
- 간단한 방법이지만 반복적으로 이웃한 요소들을 뒤로 이동시키는 과정이 포함되어 비효율적임
- Stable & Internal Sort
- 이미 거의 정렬된 경우 효율적 (정렬된 상태를 빨리 파악하고 elarly exit 할 수 있다면)
3. Bubble Sort
개념
- 인접한 두 요소를 순서를 바꾸는 것을 반복
- 두 요소를 비교하고 더 큰 요소를 뒤로, 작은 요소를 앞에 오도록
Swap
- 1번 전체 배열을 위와 같은 방법으로 순회하면 가장 큰 요소가 배열의 맨 뒤에 위치함
구현
void bubbleSort (int list[], int n)
{
int i, j;
for( i=n-1 ; i>0 ; i-- ){
for( j=0 ; j<i ; j++ )
if(list[j]>list[j+1]) // compare adjacent elements
swap(list[j], list[j+1]); // swap if they are in wrong order
}
}
예시
4 2 3 1 6 5
2 4 3 1 6 5 - 4와 2를 비교하고 자리 바꿈
2 3 4 1 6 5 - 4와 3을 비교하고 자리 바꿈
2 3 1 4 6 5 - 4 와 1을 비교하고 자리 바꿈
2 3 1 4 6 5 - 4 와 6을 비교했지만 자리를 바꿀 필요 없음
2 3 1 4 5 6 - 5 와 6을 비교하고 자리 바꿈
(가장 큰 값이 6이 맨 뒤에 오게 됨)
...(자리 바꿈이 발생하지 않는 것으로 정렬이 완료된 것을 확인)
- 비교 횟수는 언제나
n(n-1)/2로 시간 복잡도는 O(n^2)
- 이미 정렬된 배열일 경우 자리 바꿈은 발생하지 않으나 최악의 경우 3회의 이동이 발생
정리
- 두 인접한 요소를 자리 바꾸는 매우 간단한 구조
- 잦은
Swap이 발생하여 처리 속도가 느림
- Stable & Internal Sort
- 이미 정렬된 배열이나, Early Exit이 적용되면 보다 효율적일 수 있음
