정렬 알고리즘

게으른개발자·2020년 6월 26일

면접준비

목록 보기

2/6

Sorting 정렬

Bubble sort (거품 정렬)

배열의 consecutive한 두 원소를 비교하여 정렬하는 것을 반복
O(n2) 으로 성능이 좋지 않아 사용할 일은 별로 없다.

var bubbleSort = function(array) {
  var length = array.length;
  var i, j, temp;
  for (i = 0; i < length - 1; i++) { // 순차적으로 비교하기 위한 반복문
    for (j = 0; j < length - 1 - i; j++) { // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
      if (array[j] > array[j + 1]) { // 두 수를 비교하여 앞 수가 뒷 수보다 크면
        temp = array[j]; // 두 수를 서로 바꿔준다
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};

Selection sort (선택 정렬)

선택 정렬은 제자리 비교 정렬이다. 복잡도는 O(n2) 이므로 큰 리스트에는 비효율적이며, 유사한 삽입 정렬보다 성능이 더 떨어지는 것이 일반적이다. 선택 정렬은 단순함이 특징이며 특정한 상황에서는 더 복잡한 알고리즘보다 성능상 우위가 있다.
이 알고리즘은 최소값을 찾고 값을 최초 위치와 바꿔친 다음 리스트의 나머지 부분에 대해 이 과정을 반복한다. 교환 과정은 n개를 넘지 않으므로 교환 비용이 많이 드는 상황에서 유용하다.

//javascript
function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
      let min_index = i;
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[min_index] > arr[j]) {
          min_index = j;
        }
      }

      let temp = arr[min_index];
      arr[min_index] = arr[i];
      arr[i] = temp;
    }
    return arr;
  }

#python
def selectionSort(arr) {
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
        	if arr[min_index] > arr[j]:
            		min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
}

Insertion sort (삽입 정렬)

삽입 정렬은 작은 리스트와 대부분 정렬된 리스트에 상대적으로 효율적인 단순한 정렬 알고리즘이며 더 복잡한 알고리즘의 일부분으로 사용되기도 한다.
리스트로부터 요소를 하나씩 취한 다음 마치 돈을 지갑에 넣는 방식과 비슷하게 이들을 올바른 위치에, 새로 정렬된 리스트에 삽입함으로써 동작한다. 배열의 경우 새 리스트와 남아있는 요소들은 배열 공간을 공유할 수 있으나 삽입의 경우 잇따르는 모든 요소를 하나씩 이동해야 하므로 비용이 많이 든다. 셸소트는 큰 리스트에 더 효율적인 삽입 정렬의 변종이다.
삽입 정렬의 시간 복잡도는 O(n2)이며, 선택 정렬과 마찬가지로 반복문이 두번 중첩되어 사용된다.
이미 정렬되어 있는 상태서 다시 삽입 정렬을 수행하면 O(N)의 시간 복잡도를 가진다.

//javascript
function insertIndex(sorted_arr, value) {
    for(let i in sorted_arr){
      if(value < sorted_arr[i]){
        return i;
      }
    }
    return sorted_arr.length;
}

function insertSort(arr) {
   let sorted_arr = [];

   while (arr.length != 0){
     let value = arr.shift();
     let index = insertIndex(sorted_arr, value);
     sorted_arr.splice(index, 0, value);
   }
   return sorted_arr;
}

#python
def insertSort(array):
	for i in range(1,len(array)):
    	for j in range(i, 0, -1):
        	if array[j] < array[j - 1]:
            	array[j], array[j - 1] = array[j - 1], array[j]
            else:
            	break
    return array

Merge sort (병합 정렬)

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다.

리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

function mergeSort(arr){
  if (arr.length <= 1){
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
  let result = [];

  while (left.length && right.length){
    if (left[0] < right[0]){
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}

Quick sort (퀵 정렬)

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있다.
최악의 경우 O(n2)의 시간 복잡도를 가진다.
- 첫 번쨰 원소를 피벗으로 삼을 떄, 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 때

//javascript
function quickSort(arr){
    if (arr.length <= 1){
      return arr;
    }

    const pivot = arr[0]; //기준점
    const left = [];
    const right = [];

    for (let i=1; i<arr.length; i++){
      if(arr[i] < pivot){
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

#python
def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

Counting sort (계수 정렬)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때 사용 가능하다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을 수록 유리하며 공간 복잡도는 O(N+K)이다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

Heap sort (힙 정렬)

힙 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다. (완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다)
힙에는 부모 노드의 값이 자식 노드의 값보다 항상 큰 최대 힙과 그 반대인 최소 힙이 존재한다.

주의할 점은 부모-자식 관계간의 이야기이고, 형제간은 고려하지 않는다.
시간복잡도는 worst, best, average 모두 O(nlogn) 을 가진다.

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

위와 같은 방식으로 힙 정렬을 할 수 있다. 랜덤한 순서의 숫자들을 힙으로 만들어 넣고, 힙에서 하나씩 제거하면 된다. 가장 큰 값 또는 가장 작은 값 순서로 빠지기 때문에 알아서 정렬이 된다.

Heap sort vs Quick sort

힙 정렬은 worst, best, average 시간 복잡도가 모두 동일하게 O(nlogn)이 나오는 좋은 알고리즘이다.
퀵 정렬의 best 와 average 의 시간 복잡도는 힙 정렬과 동일하게 O(nlogn)이 나오지만 worst는 O(n2)이다.

그렇다면 당연히 최악의 경우에도 조금 더 빠른 힙 정렬이 좋은 거 아닌가?
그렇게 단순한 문제가 아니다. Big-O notation은 컴퓨터 계산 속도의 대략적인 측정 방법이고, 힙 정렬에는 Heapify 라는 특수한 작업이 있다. 바로 정렬되는 값이 힙에서 빠져나오면서 다시 힙 상태로 돌아가기 위해 원소들끼리 자리를 바꾸는 작업이다.

데이터가 많지 않다면 큰 영향이 없겠지만, 많은 수의 데이터를 정렬하고자 한 다면 Heapify 작업에서의 swap 수행은 무시할 수 없게 된다.

자세한 내용은 여기