정렬 알고리즘

1. 선택정렬(Selection Sort)

선택 정렬이란 n-1번 원소 넣을 위치를 선택하고 해당 위치의 원소를 정하는 알고리즘이다. 따라서 1번째 위치에서는 가장 우선순위가 높은 원소를 찾아 넣는다. 그 다음 2번째 위치에서는 2번째부터 n번째까지 원소 중 우선순위가 높은 원소를 넣는다. 이런식으로 n-1번째까지 반복하면 원소가 다 위치를 찾아들어간다.

 

시간복잡도는 O(n^2)이다. 참고로 이중선택정렬이라해서 처음부터 끝까지 훑어서 최소, 최대값을 동시에 탐색하여 넣으면서 탐색횟수를 절반으로 줄여주는 파생알고리즘도 있다.

void Selection_Sort(int a[], int size) {
    int min_idx, temp;

    for (int i = 0; i < size - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        // 해당 위치 자리교환
        temp = a[min_idx];
        a[min_idx] = a[i];
        a[i] = tmp;
    }
}

2. 삽입정렬(Insertion Sort)

삽입 정렬이란 i번째 원소를 지정해서 1번째부터 i-1번째 원소를 비교하며 더 우선순위에 맞을 때까지 위치를 왼쪽으로 이동한다. 이렇게 1~n-1번째까지 도달하게 되면 원소는 전부 정렬된다.

 

시간복잡도는 O(n^2)이다. 그런데 특징은 인간이 무의식적으로 사용하는 알고리즘이다. 실제로 배열의 사이즈가 작을 때는 효율이 굉장히 우수한 알고리즘이다. 그래서 O(NlogN)의 정렬 알고리즘들도 배열의 사이즈가 작을 때는 삽입 정렬으로 전환하여 사용하기도 한다.

void Insertion_Sort(int a[], int size) {
    int temp;
    for (int i = 1; i < size; i++) {
        temp = a[i];
        int j = i;
		// 위치 찾을 때까지 이동
        while (j > 0 && a[j - 1] > temp) {
            a[j] = a[j - 1];
            j--;
        }
        // 위치에 삽입
        a[j] = temp;
    }
}

3. 버블정렬(Bubble Sort)

버블 정렬이란 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소, .. 이런식으로 n-1번째 원소와 n번째 원소까지 비교해가며 위치를 바꾼다. 그리고 다시 1번째 원소와 2번째 원소로 돌아와 n-2번째 원소와 n-1번째 원소를 비교한다. 이런식으로 총 n(n-1)/2 번의 비교를 통해 정렬을 하는 알고리즘이다.

 

특징은 O(n^2) 의 시간복잡도를 지니고 있는데 성능적으로 최악이다. 그러나 이미 정렬된 자료에 한해서는 1번만 돌면 되기에 최선의 성능을 보여준다. 

void Bubble_Sort(int a[], int len)
{
     for(int i = len - 1; i > 0; i--)
          for (int j = 0; j < i; j++)
               if (a[j] > a[j+1])
               {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
               }
}

4. 합병정렬(Merge Sort)

합병 정렬이란 배열들을 잘게 쪼개서 각각 정렬하여 작은 배열들을 합쳐나가며 정렬하는 알고리즘이다. 작은 배열들로 쪼개서 정렬해나가기에 2개 이하의 원소가 될때까지 쪼개고 이 2개의 원소로 이루어진 배열들을 합쳐나간다.

 

시간복잡도는 O(NlogN)으로 우수하다. 그렇지만 메모리를 많이 잡아먹기도 하고 퀵정렬에 비해 실제로 시간이 더 걸리기도 한다. 그래서 대부분 퀵정렬을 선호한다.

void Merge_Sort(int arr[], int left, int right) { 
  int mid; 
  // 분할이 다 되지 않았을 경우 if 문 실행 
  if(left < right){ 
	mid = (left + right)/2; 
    merge_sort(arr, left, mid); //왼쪽 블록 분할 
    merge_sort(arr, mid+1, right); //오른쪽 블록 분할 
    merge(arr, left, mid, right); //분할된 블록 병합 
} 

void merge(int arr[], int left, int mid, int right) {  
    int i = left, j = mid + 1, k = left; 
    // 정렬 배열을 담을 임시 Arr
    int tempArr[size];
    
    //left부터 mid 까지의 블록과 mid+1부터 right까지의 블록을 서로 비교하는 부분 
    while (i <= mid && j <= right) { 
        //left index 값이 right index 값보다 작으면 left index 값을 결과 result에 복사
    	if (arr[i] < arr[j]){  
        tempArr[k] = arr[i]; i++; 
        }
        
        //아니라면 right index 값을 결과 result에 복사 
        else{ 
        tempArr[k] = arr[j]; j++; 
        } 
        
        k++; 
    } 
    
    // left 블록의 값은 다 처리되었는데 right 블록의 index가 아직 남아있을 경우 
    // right index를 순차적으로 결과 result에 복사 
    if (i > mid){ 
    	for (m = j; m <= right; m++){ 
        	tempArr[k] = arr[m]; k++; 
        } 
    } 
    
    // left 블록의 index가 아직 남아있을 경우 left index를 순차적으로 결과 result에 복사
    else { 
    	for (m = i; m <= mid; m++){ 
        	tempArr[k] = arr[m]; 
            k++; 
        } 
    }
    
    for(m = left; m <= right; m++){ 
    arr[m] = tempArr[m]; 
    } 
}

출처: https://yujuwon.tistory.com/entry/병합정렬Merge-Sort [Ju Factory]

5. 퀵정렬(Quick Sort)

퀵 정렬이란 원소 중에서 피벗값을 하나 선정한다. 그리고 피벗보다 왼쪽에 있으면서 큰 값과 피벗보다 오른쪽에 있으면서 작은 값을 서로 교환하며 위치를 조정한다. 이렇게 전부 교환한 다음 피벗을 기준으로 배열을 분할하여 2개의 분할에 대해 반복적으로 위의 과정을 반복한다.

 

특징은 이름에서부터 알 수 있듯이 평균적으로는 가장 우수한 성능을 보인다. 시간복잡도도 약 O(NlogN)이다. 그렇지만 피벗을 최소값 또는 최대값으로 계속 선정하게 되면 시간복잡도가 O(N^2)까지 떨어지게 된다. 그래서 피벗을 랜덤하게 선정하는 것이 중요하다.

 

다음의 코드는 잘 정리된 코드이다.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
  int pivot, temp;
  int low, high;

  low = left;
  high = right + 1;
  pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)

  /* low와 high가 교차할 때까지 반복(low<high) */
  do{
    /* list[low]가 피벗보다 작으면 계속 low를 증가 */
    do {
      low++; // low는 left+1 에서 시작
    } while (low<=right && list[low]<pivot);

    /* list[high]가 피벗보다 크면 계속 high를 감소 */
    do {
      high--; //high는 right 에서 시작
    } while (high>=left && list[high]>pivot);

    // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
    if(low<high){
      SWAP(list[low], list[high], temp);
    }
  } while (low<high);

  // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
  SWAP(list[left], list[high], temp);

  // 피벗의 위치인 high를 반환
  return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

  /* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
  if(left<right){
    // partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
    int q = partition(list, left, right); // q: 피벗의 위치

    // 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
    quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
    quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
  }

}
출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html