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

✅쉘 정렬 (Shell Sort)

• Donald Shell에 의해 삽입 정렬의 결점을 보안하기 위해 고안된 정렬방식
• 입력 배열을 부분 배열로 나눠 정렬하는 과정을 부분 배열의 개수를 바꾸며 이 과정을 여러번 거치는 방식
• 부분 배열의 개수를 정하기 위해 h를 설정
• 아래는 간격이 4인 쉘 정렬을 C++로 작성한 코드이다

void shellsort(int arr[], int n){
	int h, i, j, val;
    h = 1;
    do {
    	h = 3 * h + 1;
    } while(h < n);
    do {
    	h = h / 3;
        for(i = h; i < n; i++){
        	val = arr[i];
            j = i;
            while (arr[j - h] > val) {
            	arr[j] = arr[j - h];
                j = j - h;
                if (j < h - 1) {
                	break;
                }
            }
            arr[j] = val;
        }
    } while(h > 1);
}

• i, j, val 등 상수 크기 메모리를 사용하므로 제자리 정렬
• 크기가 같은 원소의 상대적 위치가 바뀌는 불안정한 정렬

✅퀵 정렬 (Quick Sort)

• 분할 정복 (divide and conquer) 방식의 정렬 알고리즘
  - 분할 정복 (divide and conquer): 해결할 수 없는 문제를 작은 문제로 분할해서 해결하는 방식
• 분할 원소 (partitioning element) 사용
• 배열의 양 끝으로부터 배열의 중심을 향해 동시 검색
  1. 좌측 -> 우측: 분할 원소보다 큰 원소를 탐색, 우측 -> 좌측: 분할 원소보다 작은 원소를 탐색 후 서로 교환
  2. 반복하다 둘이 만나게 될 경우 탐색 종료 후 그 자리에 분할 원소 대입
• 아래는 분할 원소인 partition을 구하는 것을 C++로 작성한 코드이다

int partition(int arr[], int left, int right) {
	int part, val;
    part = left;
    val = arr[part];
    do {
    	do {
        	left++;
        } while (arr[left] < val);
        
        do {
        	right--;
        } while (arr[right] > val);
        
        if (left < right) {
        	swap(&arr[left], &arr[right]);
        }
        else {
        	break;
        }
    } while(1);
    arr[part] = arr[right];
    arr[right] = val;
    return right;
}

• 아래는 퀵 정렬을 수행하는 함수를 순환 알고리즘(재귀)을 이용해 C++로 작성한 코드이다

void quicksort(int arr[], int left, int right) {
	int k;
    if(right > left) {
    	k = partition(arr, left, right + 1);
        quicksort(arr, left, k - 1);
        quicksort(arr, k + 1, right);
    }
}

• 오름차순 또는 내림차순으로 정렬되어 있을 때가 최악의 경우
• 1번의 quicksort 호출에 의해 분할 원소 1개가 제자리를 잡고 부분 배열이 치우쳐질 경우 최악의 시간 복잡도를 갖음
• 최악의 시간 복잡도는 O(n^2)
• 제자리 정렬이며, 크기가 같은 원소의 상대적 위치가 바뀌는 불안정한 정렬

사진 출처

📖참고자료

• 대학교 ppt 교안