[면접 준비] selection/bubble/merge/insertion/quick/heap sort

학습 키워드: selection sort, bubble sort, merge sort, insertion sort, quick sort, heap sort

 

2024-08-01 면접 카타 질문

다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요:

1. 선택 정렬(Selection Sort): 배열의 정렬되지 않은 부분에서 가장 낮은 값을 가진 항목을 선택하여 정렬된 부분으로 하나씩 옮겨나가는 방식입니다. O(n^2)의 시간 복잡도를 가지며 O(1)의 보조 공간을 사용합니다. 보조 공간 BigO에서 알 수 있듯이 추가적인 메모리 사용이 적다는 장점이 있으나, O(n^2)의 시간복잡도로 인해 규모가 큰 데이터 셋에 사용하기는 적합하지 않습니다.

// Java

void selectionSort (int arr[]) {

  for (int i = 0; i < arr.length - 1; i++) {

    minAt = i;

    for (int j = i + 1; j < arr.length; j++) {

      if (arr[j] < arr[minAt]) minAt = j;

    }

    swap(arr, i, minAt);

  }

}

 

void swap (int[] arr, int i, int j) {

  int temp = arr[i];

  arr[i] = arr[j];

  arr[j] = temp;

}

 

 

2. 버블 정렬(Bubble Sort): 배열의 맨 앞 항목에서부터 차례대로 순회하며 오른쪽 항목과 값을 비교하며 오른쪽 값이 작을 때 swap을 진행하여 결과적으로 배열의 뒷 부분에 가장 큰 값 부터 차례대로 쌓여 나가도록 하는 방식입니다. 선택 정렬과 마찬가지로 O(n^2)의 시간복잡도와 O(1)의 보조 공간을 사용하지만, swap이 더 자주 일어나며, swap이 발생하지 않으면 루프를 종료한다는 차이점이 있습니다.

// Java

void bubbleSort (int arr[]) {

  for (int i = 0; i < arr.length - 1; i++) {

    boolean swapped = false;

    for (int j = i + 1; j < arr.length - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {

        swap(arr, j, j + 1);

        swapped = true;

      }

    }

    if (swapped == false) break;

  }

}

 

void swap (int[] arr, int i, int j) {

  int temp = arr[i];

  arr[i] = arr[j];

  arr[j] = temp;

}

 

 

3. 병합 정렬(Merge Sort): 분할 정복(Divide and Conquer) 방식으로 배열을 정렬하는 알고리즘입니다. 배열을 최소 단위까지 분해한 뒤 정렬하고 합쳐나갑니다. 모든 케이스에서 균일하게 O(n log n)의 시간 복잡도를 가지기 때문에 규모가 큰 데이터 셋을 정렬하는데 사용하기 좋다.

void mergeSort (int[] arr) {

  if (arr.length < 2) return;

  int[] aux = new int[arr.length];

  divide(arr, aux, 0, arr.length);

}

void divide (int[] arr, int[] aux, int left, int right) {

  if (left >= right) return;

  int mid = left + (right - left) / 2

  divide(arr, aux, left, mid);

  divide(arr, aux, mid + 1, right);

  merge(arr, aux, left, mid, right);

}

 

void merge (int[] arr, int[] aux, int left, int mid, int right) {

  for (int i = left; i <= right; i++) {

    aux[i] = arr[i];

  }

  int i = left, j = mid + 1, k = right;

  while (i <= mid && j <= right) {

    if (aux[i] <= aux[j]) {

      arr[k++] = aux[i++];

    } else {

      arr[k++] = aux[j++];

    }

  }

  while (i <= mid) {

    arr[k++] = aux[i++];

  }

  while (j <= right) {

    arr[k++] = aux[j++];

  }

}

 

4. 삽입 정렬 (Insertion Sort): 배열의 두 번째 인덱스부터 마지막 인덱스까지 순회하면서 앞의 숫자들과 비교하여 적절한 위치에 끼워넣는 방식입니다. 추가적인 메모리 공간 사용이 없고 구현이 쉽다는 장점이 있으나, 대부분의 케이스에서 O(n^2) 의 시간으로 실행되기 때문에 다른 정렬 알고리즘에 비해 효율이 좋지 않아 크기가 큰 배열을 정렬하는데는 적합하지 않습니다.

 

void sort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

 

5. 퀵 정렬 (Quick Sort): 기준점인 pivot을 두고 정렬하는 분할 정복의 한 방식인데, 이 pivot이 어느 위치에 있는지에 따라 구현이 조금씩 다릅니다. 다음은 가장 오른쪽을 pivot으로 잡은 경우입니다. 배열의 맨 앞을 low, 맨 뒤를 high로 잡고, low 인덱스에 위치한 숫자가 pivot보다 작은 값이면 무시, 큰 값이면 high 인덱스를 줄여가며 정지한 low 인덱스에 위치한 값보다 작은 값이 나올 때 까지 내려간 뒤 swap을 진행합니다. 위 과정을 low == high 전까지 반복한 뒤 해당 index와 pivot index의 값을 swap 합니다. 그 다음 swap된 위치를 기준으로 좌 우로 나누어 앞의 과정을 반복합니다.

 

 평균적으로 O(n log n) 의 시간 복잡도를 가지지만, 이미 정렬되어있는 배열을 정렬할 때, 혹은 파티션이 지속적으로 비균등한 배열을 만들어낼 때와 같은 worst case에서 O(n^2) 의 시간 복잡도를 보입니다. 이를 방지하기 위해 pivot을 적절하게 선택하는 것이 중요하며, 때문에 중간 pivot 방식이 주로 사용됩니다.

 

static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int partition(int[] arr, int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);
  for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return (i + 1);
}

void quickSort(int[] arr, int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }

}

 

6. 힙 정렬 (Heap Sort): 배열을 heap property (max heap / min heap)를 만족하는 완전 이진 트리 (Complete Binary Tree)로 변환하여 진행합니다. 다음은 Max heap의 예시입니다. 먼저 앞서 말한 변환 과정을 거칩니다. 변환은 root 노드를 자식 노드 중 큰 쪽과 비교하고, 자식 노드가 더 크다면 swap 합니다. 해당 방향으로 leaf 노드까지 탐색했다면 root 노드를 제거한 뒤 배열의 가장 뒤 쪽 부터 차례대로 추가해줍니다. 남은 index들 안에서 다시 heapify를 진행하며, 마지막 하나의 root가 제거될 때 까지 반복하면 최종적으로 오름차순 정렬된 배열을 얻을 수 있습니다.

 

 항상 균일하게 O(n log n)의 시간 복잡도를 가지며, call stack으로 인해 O(log n)의 공간 복잡도를 가지지만, 보조 공간(auxiliary space)의 사용에는 O(1)의 공간 복잡도를 가집니다. 균등한 시간 복잡도 및 적은 메모리 사용률과 쉬운 구현으로 인해 큰 데이터 셋을 정렬하는데 적합하지만, 세부적으로는 다른 비등한 알고리즘들에 비해 효율이 떨어집니다.

 

void sort(int arr[]) {
    int N = arr.length;

    for (int i = N / 2 - 1; i >= 0; i--)
        heapify(arr, N, i);

    for (int i = N - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);
    }
}

void heapify(int arr[], int N, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < N && arr[l] > arr[largest])
        largest = l;

    if (r < N && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, N, largest);
    }
}

 

 

--