[알고리즘] 정렬 알고리즘(Sorting Algorithm) #1

✅선택 정렬 (Selection Sort)

• 가장 작은 원소부터 가장 큰 원소로 오름차순 순서대로 원소를 재배치 시키며 배열을 정렬하는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다고 가정
2. n개의 key 중 가장 작은 것을 찾아 첫번째 key인 arr[0]과 자리바꿈
3. 남아있는 원소들 중에 가장 작은 키를 찾아 그 원소와 arr[1]의 자리를 바꿈
4. k번째 단계에서는 남아있는 (n - k + 1)개의 key 중 가장 작은 것을 찾아 arr[k - 1]과 자리바꿈
5. 위 단계를 n - 1번 반복

• k번째 단계에서는 항상 (n - k)회의 비교를 수행하므로, (n - 1) + (n - 2) + ... + 1 이므로 n(n - 1) / 2 의 시간 복잡도를 가진다. 따라서, 평균 및 최악의 시간 복잡도는 O(n^2)이 된다.
• 아래는 C++로 작성한 선택 정렬 함수이다.

void selectionsort(int arr[], int n){
    int i, j, MinIndex;
    for(i = 0; i < n - 1; i++){
        MinIndex = i;
        for(j = MinIndex + 1; j < n; j++){
            if(arr[MinIndex] > arr[j]){
             	MinIndex = j;
            }
        }
        if(MinIndex != i){
            swap(&arr[i], &arr[MinIndex]);
        }
    }
}

• i, j, MinIndex 등 상수 크기의 메모리를 사용하므로 제자리 정렬
• 안정성: 불안정한 정렬

✅버블 정렬 (Bubble Sort)

• 좌측서부터 우측으로 이동하며 인접한 두 개의 원소를 서로 비교하고 좌측의 원소가 더 크면 우측의 원소와 교환되는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다 가정
2. 한 번 완료되었을 때 n개의 원소 중 가장 큰 원소가 우측 끝인 n-1 인덱스에 존재
3. 0번째 인덱스부터 n-2번째 인덱스까지 차례로 검색 후 완료되면 2번째로 큰 원소가 n-2번째 인덱스에 존재
4. 위 단계들 반복

• 역순으로 정렬된 배열일 경우 최악의 시간복잡도를 가진다.
• 1번째 일때 n-1번 비교, 2번째일 때 n-2번 비교, k번째일때 n-k번 비교하기 때문에, (n-1) + (n-2) ... + 1 = n(n-1)/2이므로 O(n^2)의 시간복잡도를 가지게 된다.
• 아래는 C++로 작성한 버블 정렬 함수이다.

void bubblesort(int arr[], int n){
   	for(int i = 0; i < n; i++){
       	for(int j = 1; j < n - i; j++){
           	if(arr[j - 1] > arr[j]){
               	swap(&arr[j - 1], &arr[j]);
            }
		}	
	}
}

• i, j 등 상수 크기의 메모리를 사용하므로 제자리 정렬
• 안정성: 안정된 정렬

✅삽입 정렬 (Insertion Sort)

• 앞에서부터 하나씩 순서를 맞춰나가는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다 가정
2. k번째 단계일 때, 배열 맨 처음 k-1개의 key들(0 ~ k-2 인덱스에 존재하는 원소들)은 이미 정렬되어있음.
3. k-1번째 인덱스 원소 값을 0 ~ k-2 인덱스 원소들의 값들과 비교해 적절한 위치에 삽입해 0 ~ k-1번째 인덱스의 값들이 정렬되도록 함

※ 인덱스 값이 배열 내 최소 값인 경우 arr[1]과 비교 후 멈추지 않고 다시 arr[0]과 비교되려하기 때문에 이를 막기 위해 arr[0]에는 배열의 최소 값보다도 더 작은 값을 추가로 저장하면, 실제 자료들은 1 ~ n번 인덱스에 저장됨

• 비교 횟수가 원소들의 순서에 민감
• 이미 정렬되어 있을 경우, 최선의 경우로 시간복잡도는 O(n)을 가짐
• 역순으로 정렬되어 있을 경우는 최악의 경우로 시간복잡도는 O(n^2)을 가짐
  (k번째 키 삽입 시 k번의 비교를 수행하므로 2 + 3 + ... +n = n(n+1)/2 - 1)
• 평균 시간 복잡도 또한 O(n^2)을 가짐
• 아래는 C++로 작성한 삽입 정렬 함수이다.

void insertionsort(int arr[], int n){
   	int i, j, val;
    for(i = 2; i <= n; i++){
       	val = arr[i];
        j = i;
        while(arr[j - 1] > val){
          	arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = val;
    }   
}

• i, j, val 등 상수 크기 메모리를 사용하므로 제자리 정렬
• 인접한 원소 값과 비교하면서 자신의 값과 같은 값이 나올 경우 바꾸지 않으므로 안정된 정렬

📖참고자료

• 대학교 ppt 교안