[알고리즘] 정렬

 

알고리즘하면 가장 기초가 되는 것은 정렬이라고 생각한다.

정렬이란 데이터나 요소를 특정 기준에 따라 순서대로 배열하는 과정을 의미한다.

이러한 정렬 알고리즘에는 여러가지가 있는데 여기서는 버블 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬에 대해서 다뤄볼것이다.

 

1. 버블 정렬

버블 정렬의 작동 방식은 인접한 두 값을 비교해가며 정렬하는 것이다.

가장 기본적인 정렬방식이자 비효율적인 정렬 방식의 1티어(?)라고 볼 수 있다.

그 이유는 평균적인 시간복잡도가 N^2이기 때문이다.

물론 버블 정렬은 최상의 케이스에는 한번씩만 값을 비교하고 끝나기 때문에 이 경우에는 N의 시간복잡도를 가질 수 있다.

하지만 이는 이미 정렬된 케이스를 의미하며 평균적으로는 N^2의 시간복잡도를 지닌다. 

아래는 코드 예시이다.

function bubbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

 

2. 삽입정렬

삽입정렬의 경우, 각 요소를 적절한 위치에 삽입하여 정렬하는 방식이다.

자세한 작동방식은 다음과 같다.

1. 정렬되지 않은 리스트에서 첫번째 요소를 선택한다.
2. 이 요소를 리스트에 삽입할 위치를 찾아 삽입한다.
3. 그리고 이 과정을 리스트의 모든 요소에 대해 반복한다. 

보다시피 삽입정렬 또한 모든 요소에 대해 탐색을 진행하기 때문에 버블 정렬과 마찬가지로 이미 정렬된 리스트의 경우 N의 시간복잡도를 지닐 수 있지만, 평균적으로 N^2의 시간복잡도를 지닌다는 것을 알 수 있다. 

 

아래는 코드예시이다

// 삽입정렬
function insertionSort(array) {
  let list = new Array(array.length);

  for (let i = 1; i < array.length; i++) {
    let current = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > current) {
      array[j + 1] = array[j];
      j -= 1;
    }
    array[j + 1] = current;
  }
  return array;
}

 

 

3. 병합 정렬

여기서부터 조금 까다로워진다. (나만 그럴수도 ㅎㅎ)

병합 정렬은 입력의 크기를 줄이고, 해결 후 다시 합치는 전략인 분할 정복 기법을 사용하는 방식이다. 

일반적으로 재귀 함수를 이용하여 구현되며, 병합 정렬의 최대 장점은 최선과 최악 모두 nlogn인 사실상 완전한 세타 nlogn의 시간복잡도를 가지는 일정한 알고리즘이라는 것이다.

대부분의 경우 뒤에 서술할 퀵 정렬보다 느릴 수 있지만 일정한 성능, 그리고 무엇보다 안정 정렬이라는 점이 장점이다.  

여기서 안정 정렬이란 중복된 값을 입력 순서와 동일하게 정렬하는 것을 의미한다. 

 

아래는 코드예시이다.

// 병합정렬
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex += 1;
    } else {
      result.push(right[rightIndex]);
      rightIndex += 1;
    }
  }
  return result.concat(left.slice(leftIndex).concat(right.slice(rightIndex)));
}

 

 

퀵 정렬

퀵 정렬은 리스트중 특정 값, 피벗(pivot)이라는 값을 기준으로 좌우를 나누는 특징을 가지고 있다.

병합 정렬과 마찬가지로 분할 정복 알고리즘이며 이 피벗이라는 값보다 작으면 왼쪽, 크면 오른쪽에 두어가며 파티셔닝하면서 리스트를 쪼개나가며 정렬을 진행하는 방식이다.

퀵정렬은 그 이름처럼 매우 빠르며 효율적인 알고리즘이다.

최상, 평균적인 경우 nlogn의 시간복잡도를 지닌다.

그러나 최악의 경우 N^2의 시간복잡도를 지니게 된다.

이 경우는 크게 2가지로 나뉜다.

1. 피벗 위치가 한쪽으로 고정되어 있는 경우 
2. 이미 정렬된 상태, 역으로 정렬된 상태, 모두 동일 값을 가질 때

2번째 경우, 피벗 위치를 랜덤하게 설정하여 개선이 가능하기는 하지만, 극악의 확률로 한쪽으로 고정될 수 있기에 최악의 경우 동일하게 N^2의 시간복잡도를 지니게 된다. 

 

아래는 코드예시이다.

// 퀵 정렬
function quickSort(arr) {
  quick_sort(arr, 0, arr.length - 1);
  return arr;
}
function quick_sort(arr, left, right) {
  if (left < right) {
    let pivot = partition(arr, left, right);
    quick_sort(arr, left, pivot - 1);
    quick_sort(arr, pivot + 1, right);
  }
  return arr;
}
function partition(arr, left, right) {
  let pivot = arr[Math.floor(Math.random() * right)]; // pivot값을 랜덤으로 설정함으로서 최악의 경우를 어느정도 방지
  let start = left + 1;
  let end = right;

  while (start <= end) {
    while (start <= end && arr[start] <= pivot) start += 1;
    while (start <= end && arr[end] >= pivot) end -= 1;
    if (start < end) {
      let temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
    }
  }
  let temp = arr[left];
  arr[left] = arr[end];
  arr[end] = temp;

  return end;
}