[CS] 정렬 알고리즘 (JAVA)

정렬 알고리즘 (Sorting Algorithm)

정렬 알고리즘은 크게 비교 방식(Comparisons)과 미비교 방식(Non-Comparisons)으로 나눌 수 있다.

비교 기반 정렬 알고리즘에는 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬이 있다.

미비교 기반 정렬 알고리즘에는 기수 정렬과 계수 정렬이 있다.

 

거품 정렬 (Bubble Sort)

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

• 수행 과정

1회전에 첫번째 원소부터 마지막 원소까지 인접한 원소끼리 대소를 비교하여 조건에 맞춰 서로 교환한다.

1회전이 끝나면 가장 큰 원소가 맨 뒤에 위치해 있으므로 2회전에는 맨 끝에 있는 원소는 정렬에서 제외한다.

이러한 방식으로 원소의 갯수가 N이면 (N - 1)번 해당 과정을 반복한다.

 

• 시간복잡도

\(O((N - 1) + (N - 2) + ... + 1) = O(\dfrac{N \times (N - 1)}{2})\) = \(O(N^2)\)

 

• 공간복잡도

주어진 배열 안에서 교환을 통해 정렬을 수행하므로 \(O(1)\) 이다.

 

• 장점과 단점

구현이 간단하고 소스코드가 직관적이다.

다른 메모리 공간을 필요로 하지 않는다.

중복된 값이 입력 순서와 동일하게 정렬되는 안정 정렬 알고리즘이다.

정렬 되어있지 않은 자료 상태에 대해서는 교환 연산이 많이 일어나게 된다.

시간복잡도가 최선, 평균 최악 모두 \(O(N^2)\) 으로, 다른 정렬에 비해 정렬 속도가 느려 매우 비효율적이다.

 

• 구현 코드

void bubbleSort(int[] arr) {
    int temp = 0;
    for (int i = 0; i < arr.length; i++) {       
        for (int j = 1 ; j < arr.length - i; j++) { 
            if (arr[j - 1] > arr[j]) {             
                swap(arr, arr[j - 1], arr[j])
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

선택 정렬 (Selection Sort)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

• 수행 과정

1회전에 주어진 배열 중에서 최솟값을 찾고 구한 값을 첫번째 원소와 교체한다.

2회전에는 맨 앞의 위치를 제외한 나머지 배열에서 최솟값을 찾는다.

이러한 방식으로 원소의 갯수가 N이면 (N - 1)번 해당 과정을 반복한다.

 

• 시간복잡도

\(O((N - 1) + (N - 2) + ... + 1) = O(\dfrac{N \times (N - 1)}{2})\) = \(O(N^2)\)

 

• 공간복잡도

주어진 배열 안에서 교환을 통해 정렬을 수행하므로 \(O(1)\) 이다.

 

• 장점과 단점

알고리즘이 간단하고 다른 메모리 공간을 필요로 하지 않는다.

정렬을 위한 비교 횟수는 많지만, 거품 정렬에 비해 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서는 비교적 효율적이다.

시간복잡도가 최선, 평균 최악 모두 \(O(N^2)\) 으로, 비효율적이다.

중복된 값이 입력 순서와 동일하지 않게 정렬되는 불안정 정렬 알고리즘이다.

 

• 구현 코드

void selectionSort(int[] arr) {
    int index, temp;
    for (int i = 0; i < arr.length - 1; i++) {        
        index = i;
        for (int j = i + 1; j < arr.length; j++) {  
            if (arr[j] < arr[index]) {           
                index = j;
            }
        }
        
        swap(arr, arr[i], arr[index]);
  }
  System.out.println(Arrays.toString(arr));
}

 

삽입 정렬 (Insertion Sort)

두번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘

• 수행 과정

1회전에 두번째 인덱스의 값을 저장하고 이전에 있는 원소들과 비교하여 삽입해나간다.

2회전에는 맨 처음으로 다시 돌아가서 그 다음 인덱스의 값을 저장하고 위의 과정을 수행한다. 

이러한 방식으로 원소의 갯수가 N이면 (N - 1)번 해당 과정을 반복한다.

 

• 시간복잡도

\(O((N - 1) + (N - 2) + ... + 1) = O(\dfrac{N \times (N - 1)}{2})\) = \(O(N^2)\)

 

• 공간복잡도

주어진 배열 안에서 교환을 통해 정렬을 수행하므로 \(O(1)\) 이다.

 

• 장점과 단점

알고리즘이 간단하고 다른 메모리 공간을 필요로 하지 않는다.

중복된 값이 입력 순서와 동일하게 정렬되는 안정 정렬 알고리즘이다.

대부분이 정렬되어 있는 자료 상태라면 매우 효율적이다.

버블 정렬이나 선택 정렬과 같은 \(O(N^2)\) 알고리즘에 비교하여 상대적으로 빠르다.

시간복잡도가 최선, 평균 최악 모두 \(O(N^2)\) 으로, 비효율적이다.

 

• 구현 코드

void insertionSort(int[] arr) {
    for (int index = 1; index < arr.length; index++) {
        int temp = arr[index];
        int prev = index - 1;
        while ( (prev >= 0) && (arr[prev] > temp) ) {  
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = temp;                          
   }
   System.out.println(Arrays.toString(arr));
}

 

퀵 정렬 (Quick Sort)

분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬하는 방식
주어진 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다.
피벗을 중심으로 왼쪽에는 피벗보다 작은 요소들, 오른쪽에는 피벗보다 큰 요소들이 위치하게 한다.

• 수행 과정

배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.

피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

 

• 시간복잡도

최선과 평균의 경우에는 \(O(NlogN)\) 이다. (비교 횟수 : \(log_{2}{N}\)  / 비교 연산 : N)

피벗 값이 최소이거나 최대일 때인 최악의 경우에는 \(O(N^2)\) 이다. (비교 횟수 : N  / 비교 연산 : N)

 

• 공간복잡도

피벗을 이용해 계속 둘로 나누면서 정렬을 수행하므로 \(O(logN)\) 이다.

 

• 장점과 단점

불필요한 데이터의 이동을 줄일 수 있고 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간복잡도가 \(O(NlogN)\) 인 다른 정렬 알고리즘과 비교했을 때에도 가장 빠르다.

중복된 값이 입력 순서와 동일하지 않게 정렬되는 불안정 정렬 알고리즘이다.

정렬된 배열에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

• 구현 코드

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    // 분할 (Divide)
    int pivot = partition(); 
    
    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(arr, left, pivot - 1);  // 정복(Conquer)
    quickSort(arr, pivot + 1, right); // 정복(Conquer)
}

int partition(int[] arr, int left, int right) {
    // 가장 왼쪽값을 피벗으로 설정
    int pivot = arr[left]; 
    
    int i = left;
    int j = right;
    
    while (i < j) {
        while (pivot < arr[j]) {
            j--;
        }
        
        while (i < j && pivot >= arr[i]){
            i++;
        }
        
        swap(arr, i, j);
    }
    
    arr[left] = arr[i];
    arr[i] = pivot;
    
    return i;
}

 

병합 정렬 (Merge Sort)

퀵 정렬과 마찬가지로 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬하는 방식
요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식

• 수행 과정

먼저 더 이상 나누어지지 않을 때까지 반씩 분할하여 mergeSort 함수를 호출한다.

그 후 merge 함수에서는 이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬하면 된다.

 

• 시간복잡도

최선, 평균, 최악의 경우 모두 \(O(NlogN)\) 이다.

 

• 공간복잡도

반환된 값끼리 병합할 때, 비교 결과를 기반으로 정렬되어 임시 저장 공간에 저장되므로 \(O(N)\) 이다.

 

• 장점과 단점

데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 어떻든 정렬되는 시간은 \(O(NlogN)\) 으로 동일하다. 

순차적인 비교로 정렬을 진행하므로 LinkedList의 정렬이 필요하다면 다른 어떤 정렬 방법보다 효율적이다.

중복된 값이 입력 순서와 동일하게 정렬되는 안정 정렬 알고리즘이다.

데이터의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

• 구현 코드

void mergeSort(int[] arr, int left, int right) {
    
    if (left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(arr, left, mid);	// 왼쪽 부분 배열
        mergeSort(arr, mid + 1, right);	// 오른쪽 부분 배열
        merge(arr, left, mid, right);	// 나눈 부분 배열을 합친다
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(arr, left, mid + 1);
    int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
    
    int i = 0;
    int j = 0;
    int k = left;
    
    int ll = L.length;
    int rl = R.length;
    
    // 두 부분 배열을 비교하면서 각각의 원소 중에 더 작은 원소를 먼저 넣는다 
    while (i < ll && j < rl) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        }
        else {
            arr[k++] = R[j++];
        }
    }

    // 위의 과정에서 왼쪽 혹은 오른쪽 부분 배열 중 하나의 배열이라도 
    // 모든 원소가 들어갔다면 빠져나왔기 때문에 여기서 나머지 원소를 채워준다
    while (i < ll) {
        arr[k++] = L[i++];
    }    
    while (j < rl) {
        arr[k++] = R[j++];
    }
}

 

힙 정렬 (Heap Sort)

완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식

• 수행 과정

먼저 최대 힙을 구성하면 힙의 루트에 가장 큰 값이 존재하게 된다.

이때, 루트의 값을 마지막 요소와 바꾼 후, 힙의 크기를 하나 줄인다.

힙의 크기가 1보다 크다면 위의 과정을 계속 반복한다.

 

• 시간복잡도

최선, 평균, 최악의 경우 모두 \(O(NlogN)\) 이다.

 

• 공간복잡도

주어진 배열 안에서 교환을 통해 정렬을 수행하므로 \(O(1)\) 이다.

 

• 장점과 단점

가장 크거나 가장 작은 값을 구할 때 한번의 힙 구성을 통해 쉽게 구할 수 있어 효율적이다.

중복된 값이 입력 순서와 동일하지 않게 정렬되는 불안정 정렬 알고리즘이다.

퀵 정렬과 합병 정렬의 성능에 비해 좋지 않다.

 

• 구현 코드

void heapSort(int[] arr) {
    int n = arr.length;
    
    // 최대 힙 만들기
    // 자식 노드 : (n / 2 - 1) * 2 + 1 = n - 1
    for (int i = n / 2 - 1; i >= 0; i--){
        heapify(arr, n, i);
    }
    
    // 최대 힙에서 최댓값 뽑아내는 연산
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i); 
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int parent = i;		// 부모 노드
    int left = i * 2 + 1;	// 왼쪽 자식 노드
    int right = i * 2 + 2;	// 오른쪽 자식 노드
    
    // 왼쪽 자식 노드와 부모 노드를 비교하여 큰 값을 부모 노드로 올린다.
    if (left < n && arr[parent] < arr[left]) {
        parent = left;
    }
    // 오른쪽 자식 노드와 부모 노드를 비교하여 큰 값을 부모 노드로 올린다.
    if (right < n && arr[parent] < arr[right]) {
        parent = right;
    }
    
    // "부모 노드 < 자식 노드"라서 parent 값이 바뀌었다면  
    // 위치를 교환하고 heapify()를 호출하여 과정을 반복한다.
    if (i != parent) {
        swap(arr, parent, i);
        heapify(arr, n, parent);
    }
}

 

계수 정렬 (Counting Sort)

 Comparison을 하지 않고 말 그대로 몇 개인지 개수를 세어 정렬하는 방식

• 수행 과정

정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 

정렬하고자 하는 배열의 값을 인덱스로 하는 임시 배열의 값을 증가시킨다.

그 다음, 해당 배열의 값을 누적된 값으로 변경해준다.

이 누적된 값은 정렬하고자 하는 값들이 정렬될 인덱스를 나타내게 된다. 

마지막으로, 뒤에서부터 배열을 돌면서 해당하는 값의 인덱스에 값을 넣어주면 된다.

 

• 시간복잡도

최선, 평균, 최악의 경우 모두 \(O(N + k) = O(N)\) 이다. (k = 배열에서 등장하는 최대값)

 

• 공간복잡도

배열에서 등장하는 최대값만큼의 배열을 만들어야 하므로 \(O(k) = O(N)\) 이다.

 

• 장점과 단점

비교 기반 정렬 알고리즘과 달리 \(O(N)\) 의 시간복잡도를 가진다. 

하지만, 배열 사이즈인 N만큼 돌 때, 증가시켜주는 임시 배열의 크기가 크기 때문에 메모리 낭비가 심하다.

 

• 구현 코드

int arr[5]; 		
int sorted_arr[5];

// 과정 1 - counting 배열의 사이즈를 최대값 5가 담기도록 크게 잡는다.
int counting[10];	

// 과정 2 - counting 배열의 값을 증가해준다.
for (int i = 0; i < arr.length; i++) {
    counting[arr[i]]++;
}

// 과정 3 - counting 배열을 누적합으로 만들어준다.
for (int i = 1; i < counting.length; i++) {
    counting[i] += counting[i - 1];
}

// 과정 4 - 뒤에서부터 배열을 돌면서 해당하는 값의 인덱스에 값을 넣어준다.
for (int i = arr.length - 1; i >= 0; i--) {
    counting[arr[i]]--;
    sorted_arr[counting[arr[i]]] = arr[i];
}

 

기수 정렬 (Radix Sort)

데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식
입력 데이터의 최대값에 따라서 계수 정렬의 비효율성을 개선할 수 있다.
자릿수의 값 별로 정렬을 하므로 나올 수 있는 값의 최대 사이즈는 9이다. (범위 : 0 ~ 9)

• 수행 과정

기수 테이블을 나타내는 Queue를 만든다. (bucket)
정렬하고자 하는 원소들을 각 원소의 해당 자릿수 값을 나타내는 기수 bucket에 삽입한다.
모든 기수 bucket로부터 원소를 꺼낸다. (선입선출)
자릿수를 하나 올리고 자릿수가 최댓값의 자릿수보다 커질 때까지 반복한다.

 

• 시간복잡도

최선, 평균, 최악의 경우 모두 \(O(d \times (N + k)) = O(N)\) 이다. (d = 정렬할 숫자의 자릿수, k = 10)

 

• 공간복잡도

k를 크기로 하는 Queue를 만들어야 하므로 \(O(k) = O(N)\) 이다.

 

• 장점과 단점

비교 기반 정렬 알고리즘과 달리 \(O(N)\) 의 시간복잡도를 가진다. 

문자열과 정수까지 모두 정렬 가능하다.

부동 소수점과 같은 자릿수가 없는 것은 정렬할 수 없다.

추가적으로 중간 결과를 저장할 여분의 bucket 공간이 필요하다,

 

• 구현 코드

static final int k = 10;

void radixsort(int[] arr, int n) {
    // bucket 초기화
    Queue<Integer>[] bucket = new LinkedList[k];
    for (int i = 0; i < k; ++i) {
        bucket[i] = new LinkedList<>();
    }
		
    int factor = 1;
    int maxLength = 배열에 들어있는 값 중 최댓값의 자릿수
		
    // d의 크기만큼 반복한다.
    for (int d = 0; d < maxLength; d++) {
        for (int i = 0; i < n; i++) {
            bucket[(arr[i] / factor) % 10].add(arr[i]);
        }
			
        for (int i = 0, j = 0; i < k; i++) {
            while (!bucket[i].isEmpty()) {
                arr[j++] = bucket[i].poll();
            }
        }
			
        factor *= 10;
    }
}