정렬 Sort

 

링크에 있는 내용을 한 눈에 보기 위해 옮겨온 글이며
원문을 참고해주세요

 

거품 정렬 (Bubble Sort)

인접한 두 원소의 값을 비교해 그 크기에 따라 위치를 서로 교환하는 정렬 방식

 

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

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다.

Process (Ascending)

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

Java Code (Ascending)

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

 

1. 제외될 원소의 개수를 의미합니다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜줍니다.
2. 원소를 비교할 index를 뽑을 반복문입니다. j는 현재 원소를 가리키고, j-1은 이전 원소를 가리키게 되므로, j는 1부터 시작하게 됩니다.
3. 현재 가리키고 있는 두 원소의 대소를 비교합니다. 해당 코드는 오름차순 정렬이므로 현재 원소보다 이전 원소가 더 크다면 이전 원소가 뒤로 가야 하므로 서로 자리를 교환해줍니다.

 

GIF로 이해하는 Bubble Sort

 

시간 복잡도

시간 복잡도를 계산하면, (n-1) + (n-2) + (n-3) +.... + 2 + 1 => n(n-1)/2이므로, O(n^2) 입니다.

또한, Bubble Sort는 정렬이 돼있던 안돼 있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일합니다. (개선된 Bubble Sort가 존재하긴 하나, 이번 장은 기초를 다지기 위한 학습이므로 넘어가겠습니다.)

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

장점

• 구현이 매우 간단하고, 소스코드가 직관적입니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)입니다.

단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.
• 정렬돼있지 않은 원소가 정렬됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.

---

선택 정렬 (Selection Sort)

n개의 원소 중에서 최솟값을 찾아 첫 번째 위치에 놓고, 나머지 (n-1) 개 중에서 다시 최솟값을 찾아 두번째 위치에 놓는 방식을 반복해 정렬하는 방법

 

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

Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하시면 편합니다.

Process (Ascending)

1. 주어진 배열 중에 최소값을 찾습니다.
2. 그 값을 맨 앞에 위치한 값과 교체합니다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.

Java Code (Ascending)

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

 

1. 우선, 위치(index)를 선택해줍니다.
2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작합니다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해줍니다.
4. '2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야 하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해줍니다.

GIF로 이해하는 Selection Sort

 

시간 복잡도

데이터의 개수가 n 개라고 했을 때,

• 첫 번째 회전에서의 비교 횟수 : 1 ~ (n-1) => n-1
• 두 번째 회전에서의 비교 횟수 : 2 ~ (n-1) => n-2
• ...
• (n-1) + (n-2) +.... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다.

최선, 평균, 최악의 경우 시간 복잡도는 동일합니다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

장점

• Bubble sort와 마찬가지로 알고리즘이 단순합니다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적입니다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)

단점

• 시간 복잡도가 O(n^2)으로, 비효율적입니다.
• 불안정 정렬(Unstable Sort)입니다.

---

삽입 정렬 (Insertion Sort)

손 안의 카드를 정렬하는 방법과 유사합니다.

(이미 순서화된 파일에 새로운 하나의 원소를 순서에 맞게 삽입시켜 정렬하는 방식)

 

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.

Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다.

Process (Ascending)

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

Java Code (Ascending)

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

 

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작합니다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장합니다.
2. 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 합니다.
3. '2'번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index)를 가리키게 됩니다. 따라서, (prev+1)에 temp 값을 삽입해줍니다.

 

GIF로 이해하는 Insertion Sort

시간 복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) +.... + 2 + 1 => n(n-1)/2 즉, O(n^2)입니다.

하지만, 모두 정렬이 되어있는 경우(Optimal) 한 경우, 한 번씩 밖에 비교를 안 하므로 O(n)의 시간 복잡도를 가지게 됩니다.

또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.

최선의 경우는 O(n)의 시간 복잡도를 갖고, 평균과 최악의 경우 O(n^2)의 시간 복잡도를 갖게 됩니다.

 

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

 

장점

• 알고리즘이 단순합니다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)입니다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠릅니다.

단점

• 평균과 최악의 시간 복잡도가 O(n^2)으로 비효율적입니다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다.

---

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입)

불안정 정렬 : 동일한 값에 기존 순서가 유지 X (선택, 퀵)

퀵 소트

피봇이라는 기준값을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리시키는 과정을 반복하는 정렬 방식

원소의 많은 이동을 없애고 정렬할 원소들을 부분적으로 나누어 가면서 정렬함

 

퀵 소트는 최악의 경우 O(n^2), 평균적으로 O(nlogn)을 가짐

 

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    int pi = partition(array, left, right);
    
    quickSort(array, left, pi-1);
    quickSort(array, pi+1, right);   
}

 

피벗 선택 방식 : 첫 번째, 중간, 마지막, 랜덤

(선택 방식에 따라 속도가 달라지므로 중요함)

 

public int partition(int[] array, int left, int right) {
    int pivot = array[left];
    int i = left, j = right;
    
    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i<j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    
    return i;
}

 

1. 피벗 선택
2. 오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수 찾음
3. 왼쪽(i)에서 오른쪽으로 가면서 피벗보다 큰 수 찾음
4. 각 인덱스 i, j에 대한 요소를 교환
5. 2,3,4번 과정 반복
6. 더 이상 2,3번 진행이 불가능하면, 현재 피벗과 교환
7. 이제 교환된 피벗 기준으로 왼쪽엔 피벗보다 작은 값, 오른쪽엔 큰 값들만 존재함

 

버블 정렬은 모든 배열의 요소에 대한 인덱스를 하나하나 증가하며 비교해나가는 O(n^2)

퀵 정렬의 경우 인접한 것이 아닌 서로 먼 거리에 있는 요소를 교환하면서 속도를 줄일 수 있음

But, 피벗 값이 최소나 최댓값으로 지정되어 파티션이 나누어지지 않았을 때 O(n^2)에 대한 시간 복잡도를 가짐

퀵 소트 O(n^2) 해결 방법

이런 상황에서는 퀵 소트 장점이 사라지므로, 피벗을 선택할 때 중간 요소로 선택하면 해결이 가능함

 

public int partition(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    swap(array, left, mid);
    ...
}

 

이는 다른 O(nlogn) 시간 복잡도를 가진 소트들보다 빠르다고 알려져 있음

 

먼 거리 교환 처리 + 캐시 효율(한번 선택된 기준은 제외시킴)

private void solve() {
    int[] array = { 80, 70, 60, 50, 40, 30, 20 };
    quicksort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static int partition(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    swap(array, left, mid);
 
    int pivot = array[left];
    int i = left, j = right;
 
    while (i < j) {
        while (pivot < array[j]) {
            j--;
        }
 
        while (i < j && pivot >= array[i]) {
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    return i;
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[b];
    array[b] = array[a];
    array[a] = temp;
}
 
public static void quicksort(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
 
    int pi = partition(array, left, right);
 
    quicksort(array, left, pi - 1);
    quicksort(array, pi + 1, right);
}

---

머지 소트(Merge Sort)

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현

평균과 최악 모두 시간 복잡도는 O(nlogn)

분할 정복이란?

큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

 

빠른 정렬로 분류되며, 퀵 소트와 함께 많이 언급되는 정렬 방식이다.

퀵 소트와는 반대로 안정 정렬에 속함

시간 복잡도

평균	최선	최악
O(nlogn)	O(nlogn)	O(nlogn)

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵 정렬과 유사

mergeSort

public void mergeSort(int[] array, int left, int right) {
    
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
    
}

 

정렬 로직에 있어서 merge() 메서드가 핵심

퀵 소트와의 차이점

퀵 정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)

합병 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

merge()

public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

 

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

★★★합병 정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.★★★

LinkedList를 퀵 정렬을 사용해 정렬하면?

성능이 좋지 않음

퀵 정렬은, 순차 접근이 아닌 임의 접근이기 때문

LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적임

따라서 임의로 접근하는 퀵 소트를 활용하면 오버헤드 발생이 증가하게 됨

배열은 인덱스를 이용해서 접근이 가능하지만, LinkedList는 Head부터 탐색해야 함

배열[O(1)] vs LinkedList [O(n)]

 

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    mergeSort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
 
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}
 
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
 
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
 
    while (i < ll && j < rl) {
        if (L[i] <= R[j]) {
            array[k] = L[i++];
        } else {
            array[k] = R[j++];
        }
        k++;
    }
 
    while (i < ll) {
        array[k++] = L[i++];
    }
 
    while (j < rl) {
        array[k++] = R[j++];
    }
}

---

힙 소트(Heap Sort)

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

평균과 최악 최선 모두 시간 복잡도는 O(nlogn)이다.

 

힙 소트는 불안정 정렬에 속함

시간 복잡도

평균	최선	최악
O(nlogn)	O(nlogn)	O(nlogn)

과정

1. 최대 힙을 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의 사이즈가 1보다 크면 위 과정 반복

루트를 마지막 노드로 대체 (11 → 4), 다시 최대 힙 구성

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 소트

 

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

 

 

1번째 heapify

일반 배열을 힙으로 구성하는 역할

자식 노드로부터 부모 노드 비교

• n/2-1부터 0까지 인덱스가 도는 이유는?
• 부모 노드의 인덱스를 기준으로 왼쪽 자식 노드 (i2 + 1), 오른쪽 자식 노드(i2 + 2)이기 때문

2번째 heapify

요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함

루트를 기준으로 진행(extract 연산 처리를 위해)

 

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;
    
    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }
    
    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

 

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap 하며 재귀 진행

퀵 정렬과 합병 정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않음.

하지만 힙 자료구조가 많이 활용되고 있으며, 이때 함께 따라오는 개념이 힙 소트

 

힙 소트가 유용할 때

• 가장 크거나 가장 작은 값을 구할 때 (최소 힙 or 최대 힙의 루트 값이기 때문에 한 번의 힙 구성을 통해 구하는 것이 가능)
• 최대 k 만큼 떨어진 요소들을 정렬할 때 (삽입 정렬보다 더욱 개선된 결과를 얻어낼 수 있음)

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
 
    if (l < n && array[p] < array[l]) {
        p = l;
    }
 
    if (r < n && array[p] < array[r]) {
        p = r;
    }
 
    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

---

기수 정렬(Radix sort = Bucket Sort)

Queue를 이용해 자릿수(Digit) 별로 정렬하는 방식

원소 값을 분석해 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 원소를 꺼내어 정렬한다.

평균과 최악 모두 시간 복잡도는 O(dn)이다.

---

비트 마스크(BitMask)

이진수를 사용하는 컴퓨터의 연산 방식을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이다.

 

집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉

왜 비트 마스크를 사용하는가?

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제
• 작은 메모리와 빠른 수행 시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함)
• 집합을 배열의 인덱스로 표현할 수 있음
• 코드가 간결해짐

 

출처

https://github.com/gyoogle/tech-interview-for-developer