[정렬] 기본 정렬(선택, 버블, 삽입), 고급 정렬(병합, 퀵, 힙), 계수정렬

• - 기본 정렬 알고리즘
• 선택 정렬
• 버블 정렬
• 삽입 정렬
• - 고급 정렬 알고리즘
• 병합 정렬
• 퀵 정렬
• 힙 정렬
• - 계수 정렬

기본 정렬 알고리즘(선택, 버블, 삽입 정렬)

1. 선택 정렬(Selection Sort)

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 입력에 민감하지 않은 정렬이다. 

또한 선택 정렬은 항상 일정한 시간 복잡도를 가지는 정렬 알고리즘이기도 하다.

 

 - 선택 정렬 알고리즘

① 배열 A[1..n]에서 가장 큰 원소를 찾는다.

② 가장 큰 원소와 끝자리에 있는 A[n]과 자리를 바꾼다.

    -> 여기서 맨 뒷자리로 옮긴 원소는 자기 자리를 찾은 것이므로 이제 신경쓰지 않아도 된다.

③ 나머지 원소 n-1개에 대해서도 동일한 작업을 반복한다.

 

- 선택 정렬 pesudo code

selectionSort(A[], n) {
   for last <- n downto 2 {
      k <- theLargest(A, last);
      A[k] <-> A[k];
   }   
}

theLargest(A[], n) {
    largest <- 1;
    for i <-2 to last
    	if (A[i] > A[largest]) then largest <- i;
    return largest;
}    

 

- 수행 시간

선택 정렬의 수행시간은, 모든 경우에  O(n^2) 이다.

선택 정렬은 selectionSort에서 수를 비교하는 횟수가 전체 시간을 좌우하기 때문에 이를 기준으로 수행시간을 분석한다.

총 횟수는 (n-1) + (n - 2) + ... + 2 = n (n - 1) / 2, 즉 O(n^2) 의 시간이 소요된다.

 

- 선택정렬 알고리즘의 특징

장점 : 자료 이동 횟수가 미리 결정된다.

단점 : 안정성을 보장하지 못한다. (값이 동일한 원소가 있을 경우, 정렬되며 이들의 상대적 위치가 바뀔 수 있다.)

 

---

2. 버블 정렬(Bubble Sort)

버블 정렬도 위에서 본 선택 정렬과 유사하게, 가장 큰 값을 오른쪽으로 옮기는 정렬 알고리즘이다.

 

- 버블 정렬 알고리즘

① 정렬할 배열이 주어지면, 왼쪽부터 시작해 이웃한 쌍들을 비교한다. 

②  이웃한 쌍끼리 순서대로 정렬되어 있지 않으면 자리를 바꾼다.

③ 배열의 끝까지 (n-1)번 비교한 후, 맨 마지막에 있는 원소를 제외한 후 나머지 원소들에 대해 계속 위의 과정을 반복한다.

 

출처  :  https://wonjayk.tistory.com/219

- 버블 정렬 pesudo code

bubbleSort(A[], n) {
	for last <- n downto 2
    	for i <- 1 to last - 1
          	if (A[i] > A[i + 1]) then A[i] <-> A[i + 1]
}            

 

- 수행 시간

버블 정렬에서 수행시간은 평균과 최악일 경우에,  O(n^2)이다.

버블 정렬은 bubbleSort에서 수를 비교하는 횟수가 전체 시간을 좌우하기 때문에 이를 기준으로 수행시간을 분석한다.

총 횟수는 (n-1) + (n - 2) + ... + 2 = n (n - 1) / 2, 즉 O(n^2) 의 시간이 소요된다.

 

하지만, 최선일 때는 O(n)의 수행 시간을 가질 수 있다.

배열이 정렬되어 들어올때 이러한 최선의 수행시간을 가질 수 있다.

위의 pesudo 코드에 한가지 장치를 추가하여, 배열이 정렬되어 있을 경우를 처리할 수 있다.

 

bubbleSort(A[], n) {
	 sorted <- TRUE;
     for last <- n downto 2 {
    	for i <- 1 to last - 1 { 
          	if (A[i] > A[i + 1]) then{
            	A[i] <-> A[i + 1]
                sorted <- FALSE;
            }    
       }
       if (sorted == TRUE) then return;
     }  
}

두번째 for문이 시작되기 전, sorted를 TURE로 두고, 이것이 두번째 for문을 도는 동안 변하는지 확인한다.

만약 원소의 자리가 바뀌게 되면, 이 배열은 정렬되어 있는 상태가 아닌 것이므로 sorted를 FALSE로 바꿔준다.

 

하지만, 두번째 for문을 다 돌고 나와도 여전히 sorted가 TRUE라면, 한번도 자리 바꿈이 일어나지 않았다는 의미이므로, 배열이 이미 정렬되어 있음을 알수 있다. 이때는 바로 리턴해줌으로써 알고리즘을 끝내주면 된다.

 

---

3. 삽입 정렬(Insertion Sort)

삽입 정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더하여 정렬된 i + 1개짜리 배열을 만드는 과정을 반복하는 정렬 알고리즘이다. 선택 정렬과 버블 정렬은 n개짜리 배열에서 시작하여, 그 크기를 하나씩 줄이는 것에 비해, 삽입 정렬은 이와 반대로 한개짜리 배열에서 시작하여 그 크기를 하나씩 늘리는 정렬이다.

 

- 삽입 정렬 알고리즘

①  배열이 주어지면, 배열의 두번째 원소부터 시작하여 그 앞의 자료들과 비교하여, 삽입할 위치를 찾는다.

② 원소를 삽입할 위치 뒤에 있는 원소들을 뒤로 옮긴다.

③ 그 다음 지정한 자리에 원소를 삽입한다. 모든 배열이 정렬될 때까지 이 과정을 반복한다.

 

 

출처 :  https://marinelifeirony.tistory.com/68

 

 

- 삽입 정렬 pesudo code

insertionSort(A[], n) {
    for i <-2 to n {
    	loc <- i - 1;
        newItem <- A[i];
        // 이 지점에서 A[1. . i-1]은 이미 정렬되어 있는 상태
        while(loc >= 1 and newItem < A[loc]) {
        	A[loc + 1] <- A[loc];
            loc--;
        }
        A[loc+1] <- newItem;
     }
}     

 

- 수행 시간

삽입 정렬에서 수행시간은 평균과 최악일 경우에,  O(n^2)이다.

총 횟수는 (n-1) + (n - 2) + ... + 2 = n (n - 1) / 2, 즉 O(n^2) 의 시간이 소요된다.

 

삽입 정렬은 수행시간이 O(n^2)인 비효율적인 정렬 알고리즘이다.

하지만, 배열이 거의 정렬된 상태에서 입력되는 경우에 가장 매력적인 알고리즘이다.

 

배열이 완전히 정렬된 상태로 입력되면, insertionSort의 while문은 한번도 수행되지 않는다. for문만 한번 순환하기 때문에

O(n)의 시간이 소요된다.  삽입 정렬은 배열이 이미 정렬된 상태라면 버블 정렬에서처럼 굳이 다른 코드를 추가하지 않아도 효율적으로 끝난다.

 

정리하자면,

평균과 최악의 경우 수행시간은  O(n^2)

최선의 경우 수행시간은  O(n)

 

---

고급 정렬 알고리즘(병합, 퀵, 힙 정렬)

1. 병합 정렬(Merge Sort)

병합 정렬은 분할 정복 방법을 사용하는 정렬 알고리즘이다. 입력을 반으로 나누어 전반부와 후반부를 각각 독립적으로 정렬한다. 그 다음 정렬된 두 부분을 병합하여 정렬된 배열을 얻는다.

 

- 병합 정렬 알고리즘

① 정렬할 배열이 주어지면, 이 배열을 반으로 나눈다.  

② 나눈 각각의 배열을 독립적으로 정렬한다.

③ 나눈 배열을 병합하여 정렬을 완료한다.

 

 

- 병합 정렬 pesudo code

mergeSort(A[], p, r) {
	if(p < r) then {
    	q <- (p+r)2; // p,r의 중간지점 계산
        mergeSort(A, p, q);
        mergeSort(A, q+1, r);
        merge(A, p, q, r);
    }
}

merge(A[], p, q, r) {
    // 전반부 배열 변수 : i, p에서 시작
    // 후반부 배열 변수 : j, q + 1에서 시작
	i <- p; j <- q+1, t <- 1;
    while(i <= q and j <= r)
    	ir (A[i] <= A[j])
        then tmp[t++] <- A[i++];
        then tmp[t++] <- A[j++];
    }
    // 왼쪽 부분 배열이 남은 경우
    while(i <= q) tmp[t++] <- A[i++];
    // 오른쪽 부분 배열이 남은 경우
    while(j <= r) tmp[t++] <- A[j++];
    
    i <- p; t <- 1;
    while(i <= r) A[i++] <- tmp[t++];
}    
    

 

- 수행 시간

최악의 경우에도 O(nlogn) 이다.

 

 

---

2. 퀵 정렬(Quick Sort)

퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰는 정렬 알고리즘이다. 퀵 정렬은 비균등 분할 정복 방식을 사용한다.

 

- 퀵 정렬 알고리즘

 

① 정렬할 배열이 주어지면, 맨 뒤의 원소를 기준원소(피벗)로 삼는다. (기준원소는 반드시 맨 마지막일 필요는 없다.)

② 기준 원소보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 배치한다.

③ 기준 원소 왼쪽과 오른쪽을 독립적으로 정렬한다.

 

- 퀵 정렬 pesudo code

quickSort(A[], p, r) {
	if(p < r) then {
    	q <- partition(A,p,r); // 분할
        quickSort(A, p, q-1);  // 왼쪽 부분 배열 정렬
        quickSort(A, q+1, r);  // 오른쪽 부분 배열 정렬
     }
}

partition(A[], p, r) {
    x <- A[r];
    i <- p-1; // i는 1구역의 끝지점
    for j <- p to r-1 // j는 3구역의 시작지점
    	if (A[j] <= x) then A[++i] <-> A[j]; // 기준 원소보다 작은 경우, i값 증가후 A[i] <-> A[j] 교환
        
   A[i+1] <-> A[r];
   return i+1;
}

 

- 수행 시간

이상적인 경우는, 분할이 항상 반반식 균등하게 될 때이다. 이때의 수행시간은 O(n)이다.

 

최악의 경우는, 계속해서 한쪽은 하나도 없고, 다른쪽에 다 몰리도록 분할되는 경우이다. 이때의 수행시간은 O(n^2)이다.

하지만 이렇게 계속 한쪽이 완전히 비거나 이러한 상황에 근접한 상태가 계속 반복될 경우는 매우 희박하다.

 

평균적인 경우, 퀵 정렬의 수행시간은 분할이 어떻게 균형있게 되냐에 달려있다. 따라서 평균 수행 시간은 분할했을 때 모든 가능한 경우를 평균내면 된다. 따라서 이때의 수행시간은 O(nlogn)이다.

 

---

3. 힙 정렬(Heap Sort)

힙 정렬은 힙이라는 특수한 자료구조를 사용하는 정렬 알고리즘이다. 힙에는 최소힙과 최대힙이 있다. 여기서는 최소 힙을 기준으로 설명한다.

 

◎ 힙(Heap)

힙은 이진 트리로서, 맨 아래 층을 제외하고는 완전히 채워져 있고, 맨 아래층은 왼쪽부터 꽉 채워져 있다.

힙 성질은, "각 노드의 값은 자기 자식의 값보다 작다."

 

- 힙 만들기

힙은 링크나 포인터를 이용하여 만들 수 있지만, 힙 정렬에서 사용하는 트리는 꽉 찬 이진 트리이기 때문에 더 간단하게 1차원 배열로 구현할 수 있다. 배열 A[k]의 자식은 A[2k], A[2k+1]이다. 이를 이용해 힙을 만들 수 있다.

 

힙을 만드는 방법은,

1 ) 주어진 배열 A에 수들이 아무렇게나 들어가있다.

2 ) 맨 뒤에서부터 따져 힙 성질에 위배되는지 확인하고, 힙 성질을 만족하도록 수정한다.

 

buildHeap(A[], n) {
	for i <- n/2 downto 1
    	heapify(A,i,n);
}

heapify(A[], k, n) { // A[k]를 루트로 하는 힙성질을 만족하도록 수선한다.
	left <- 2k; right <- 2k + 1;
    
    //작은 자식 고르기
    //(1) k가 두 자식을 가지는 경우
    if(right <= n)  then {
    	if( A[left] < A[right]) then smaller <- left;
        						then smaller <- right;
	}
     //(2) 왼쪽 자식만 있는 경우
    else if (left <= n) then smaller <- left;
    // (3) A[k]가 리프노드
    else return;
    
    if(A[smaller] < A[k]) then {
    	A[k] <-> A[smaller];
        heapify(A, smaller, n);
     }
}     

힙을 만드는 heapify 함수의 경우, 어떤 서브 트리도 높이가 log₂n을 넘지 않으므로, heapify을 한번 수행하는데 O(logn)이 소요된다.

 

◎ 정렬

힙을 완성한 후, 정렬 작업을 진행한다. 루트 노드에 있는 원소를 제거하여 임시 배열에 저장한다.

루트 노드를 제거하면 트리의 크기가 하나 줄어든다. 이때 맨 끝에 있는 원소를 루트로 옮겨 새로운 루트로 삼는다.

이렇게 하면, 대부분의 경우 루트 노드와 자식 간에 힙성질이 깨진다. 다시 heapify()를 이용해 힙성질을 만족하도록 다시 수선해야한다.

 

heapSort(A,n) {
	buildHeap(A,n);
    for i <- n downto 2 {
    	A[1] <-> A[i]; // 루트와 마지막 원소를 교환
        heapify(A, 1, i - 1); 
     }
 }    

 

buildHeap()은 O(n)의 시간이 든다. heapify()는 O(log n) 의 시간이면 된다.

따라서 힙정렬의 총 수행시간은, O(nlogn)이다.

 

---

계수 정렬(Counting Sort)

계수 정렬은 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에 사용할 수 있다.

예를 들어, 배열 A[1..n]의 원소들이 k를 넘지 않는 자연수인 경우를 들 수 있다. 

계수 정렬은 먼저 배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇 번 나타나는지를 센다. 이를 통해 A[1..n]의 각 원소가 몇 번째에 놓이면 되는지 계산할 수 있다.

 

- 계수 정렬 pesudo code

 

countingSort(A[], B[], n) {
    for i <- 1 to k // 배열안에 최대 k를 넘지 않는 원소만 들어갈 수 있다.
    	 C[i] <- 0;
         
    for j <- 1 to n
    	 C[A[j]]++;
         
    for i <- 2 to k
    	 C[i] <- C[i] + C[i-1];
         
    for j <- n downto 1 {
    	 B[C[A[j]]] <- A[j];
         C[A[j]]--;
     }
}     

 

- 수행 시간

계수 정렬의 수행 시간은 O(n)이다.

총 네개의 for문이 시간을 결정한다.

첫번째는 O(k), 두번째는 O(n), 세번째는 O(k), 네번째는 O(n)의 시간이 소요된다.

 

여기서 k가 O(n)을 초과하면 시간은 O(k)가 된다. k가 O(nlogn)을 초과하면 계수 정렬은 위의 고급 정렬들보다 매력이 없어진다.

그래서 일반적으로 계수 정렬은 k가 O(n)을 초과하지 않은 경우에 선형 시간에 정렬하기 위해 사용한다.