42page

정렬알고리즘 & 시각화 (Sorting Algorithms)

October 10th 2018

목차

  • 정렬알고리즘 소개
  • 버블정렬(Buble Sort)
  • Stability-Adaptability
  • 선택정렬(Selection Sort)
  • 삽입정렬(Insertion-Sort)
  • 병합정렬(Merge-Sort)
  • 퀵정렬(Quick-Sort)

정렬알고리즘 소개

정렬 알고리즘을 사용하면 아래와 같은 여러 작업을 할 때 도움이 될 수 있습니다.

  • 어떠한 리스트를 정렬할 때
  • 중간값을 찾아야 할 때
  • 중복값을 찾을 때
  • Database에서 Binary Search를 할 때 등

정렬 알고리즘을 학습하면 어떠한 애플리케이션을 만드는데 보장된 성능이 필요할 때, 그에 맞는 알고리즘을 선택해 사용할 수 있을 것입니다. 또는 대용량의 데이터를 다루거나 소규모의 데이터를 다루는 작업을 할 때 상황에 맞는 특정 알고리즘을 사용할 수 있을 것입니다.

버블정렬(Buble-Sort)

버블정렬은 데이터의 인접한 두 요소를 비교하여, 정렬 기준에 맞지 않으면 두 요소의 위치를 서로 변경하는 정렬방법입니다. 비교적 간단한 정렬 알고리즘이지만 그에 따라 시간복잡도가 O(n2)이기에 코드 성능이 떨어져 실용적이지 못 합니다.

버블정렬의 숫자 정렬 방식은 아래와 같습니다.

  • list를 loop합니다.
  • 인접한 두 요소를 비교합니다.
  • 큰 수를 뒤쪽에 위치하도록 두 요소의 자리를 변경합니다.
  • 위 방법을 배열의 길이만큼 반복합니다.

Pseudocode로 작성하고, 옆에 시간복잡도를 표기했습니다.

for k, loop through 1 to n-1 (n-1)
  for i loop through 0 to n-2 (n-1)
    if arr[ i ] is greater than arr[ i+1 ](constant)
      swap arr[ i ] with arr [ i+1 ](constant)

시간복잡도

  • F(n) = (n-1) _ (n-1) _ c
  • F(n) = c(n2) - 2cn + 1
  • constant를 제거한 시간복잡도는 F(n2)

만약 정렬이 이미 된 상태라면, best case로 O(n)의 시간복잡도가지 나올수도 있기는 합니다.

단점 성능이 좋지 않습니다. 특히 데이터의 양이 크면 더더욱 좋지 않습니다. 따라서, 거의 학습용으로 사용하는 정렬 알고리즘이라고 간주할 수 있습니다.

장점 Bubble-sort는 "in-place"로, 공간복잡도가 좋습니다. 쓰고 이해하기 쉽습니다.

아래는 제가 작성한 버블정렬 알고리즘을 애니메이션을 추가해 시각화 해 보았습니다.

개념이해를 했으니 이제 코드로 표현해 보도록 하겠습니다. 매 loop마다 배열의 인접한 두 요소를 비교하기 때문에 첫번째 for-loop는 '배열의 길이 - 1회'를 실행합니다. nested for-loop에서 끝의 두 요소를 비교하면 마지막 index에서 loop를 또 실행할 필요가 없습니다. 때문에, 마찬가지로 '배열의 길이-1'회를 실행합니다.

그리고 한번의 loop가 끝나면 배열 맨 뒤 쪽에 가장 큰 수가 쌓이게됩니다. 따라서, 중복으로 확인할 필요가 없기에 'wall-k'로 loop범위를 1씩 줄였습니다.

function bubbleSort(arr) {
  const wall = arr.length - 1;

  for (let k = 0; k < wall; k++) {
    for (let i = 0; i < wall - k; i++) {
      if (arr[i] > arr[i + 1]) {
        let small = arr[i + 1];
        let big = arr[i];
        arr[i] = small;
        arr[i + 1] = big;
      }
    }
  }

  return arr;
}

아래는 동일한 버블정렬이지만 while-loop를 사용한 코드입니다.

function bubbleSort(arr) {
  let wall = arr.length - 1;

  while (wall > 0) {
    for (let i = 0; i < wall; i++) {
      if (arr[i] > arr[i + 1]) {
        arr = swap(arr, i, i + 1);
      }
    }

    wall--;
  }

  return arr;
}

function swap(arr, i1, i2) {
  // Bitwise swap
  // Note: only works with integer elements
  arr[i1] = arr[i1] ^ arr[i2];
  arr[i2] = arr[i1] ^ arr[i2];
  arr[i1] = arr[i1] ^ arr[i2];
  return arr;
}

stability and adaptability

안정정렬은 정렬을 하며, 동일한 요소일 때 기존 배열의 순서를 유지하며 그렇지 않은 경우 불안정 정렬이라 합니다. 만약 정렬할 리스트가 일부분 정렬되어 있다면 adaptability에 대해 고려해 볼 수 있습니다. 정렬 알고리즘이 특정 리스트를 바탕으로 더 효율적으로 작성할 수 있다면 adaptive하다고 할 수 있어요.


선택정렬(Selection-Sort)

선택정렬은 배열에서 가장 작은 수를 찾은 후, 새로운 배열에 push하는 정렬방법입니다. 만약 공간복잡도를 고려한다면, 선택정렬은 새로운 배열을 생성하기 때문에 좋지는 않습니다.

function selectionSort(arr) {
  let newArr = [];
  let minVal;
  let wall = arr.length;

  while (wall > 0) {
    minVal = arr.reduce((acc, cur) => {
      minVal = acc > cur ? cur : acc;
      return minVal;
    }, arr[0]);

    newArr.push(minVal);

    arr.splice(arr.indexOf(minVal), 1);

    wall--;
  }

  return newArr;
}

using for loop instead of while loop

function selectionSort(arr) {
  let newArr = [];
  let minVal;
  let wall = arr.length;

  for (let k = 0; k < wall; k++) {
    arr.reduce((acc, cur) => {
      acc > cur ? (minVal = cur) : (minVal = acc);
      return minVal;
    }, arr[0]);

    newArr.push(minVal);

    arr.splice(arr.indexOf(minVal), 1);
  }

  return newArr;
}

선택정렬 (in place )

이번에는 위의 방법과 다르게 새로운 배열을 생성하지 않고 기존의 배열을 그대로 사용합니다. 굳이 새로운 공간을 차지하지않고 동일한 결과를 얻을 수 있습니다.

function selectionSort(arr) {
  arr.forEach((cur, idx) => {
    let minVal = cur;

    // loop를 돌며 두 요소만 비교해서 최소값을 찾을 수 없음. 따라서 기준점을 설정함.
    for (let i = idx; i < arr.length; i++) {
      minVal = minVal > arr[i] ? arr[i] : minVal;
    }

    arr.splice(arr.indexOf(minVal), 1);

    arr.unshift(minVal);
  });

  return arr.reverse();
}

// 밑의 코드는 내부 함수를 만들어 recursion을 사용해 보았습니다.
function recursiveSelectionSort(array) {
  let end = array.length;

  innerRecursion(array);

  function innerRecursion(arr) {
    let minVal = arr[0];

    for (let i = 0; i < end; i++) {
      minVal = minVal > arr[i] ? arr[i] : minVal;
    }

    arr.push(minVal);

    arr.splice(arr.indexOf(minVal), 1);

    if (end === 1) {
      return;
    } else {
      end--;
      innerRecursion(arr);
    }
  }

  return array;
}

Recursion으로도 구현을 해 보았습니다. 정렬알고리즘 공부하며 재귀 연습을 더 하려 했는데 loop를 쓴 것보다 더 복잡해 보입니다. 더 연습이 필요한것 같습니다.


삽입정렬(Insertion-Sort)

삽입정렬은 선택정렬과 유사합니다. 차이점은 삽입정렬은 배열의 처음부터 순차적으로 요소를 선택해 새로운 배열에 push 합니다. 새로운 배열에 새로운 요소가 추가될때마다, 해당 요소의 위치를 알맞게 설정해줍니다.

삽입정렬의 시간복잡도 버블정렬과 마찬가지로 O(n2)이고, best-case로 O(n)까지 될 수 있습니다.

삽입정렬( in place )

삽입정렬( in place )은 배열의 첫 요소를 선택하고, 이것을 정렬된 리스트로 간주합니다. 순차적으로 다음 요소를 선택해 앞서 정렬된 리스트에 요소를 추가합니다. 요소를 추가할 때마다 알맞은 자리에 위치를 설정해줍니다.

function insertSort(arr) {
  let flag = 0;

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      break;
    }

    if (arr[i] < arr[i + 1]) {
      flag = i + 1;
    }
  }

  for (let i = flag + 1; i <= arr.length - 1; i++) {
    let temp = arr.splice(i, 1)[0];
    let count = flag;

    while (count >= 0) {
      if (arr[count] < temp) {
        arr.splice(count + 1, 0, temp);
        flag++;
        break;
      }

      if (count === 0 && temp < arr[count]) {
        arr.unshift(temp);
      }

      count--;
    }
  }

  return arr;
}

또는 for loop를 사용하면,

function insertionSort(arr) {
  let flag = 0;

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      break;
    }

    if (arr[i] < arr[i + 1]) {
      flag = i + 1;
    }
  }

  for (let i = flag + 1; i <= arr.length - 1; i++) {
    let temp = arr.splice(i, 1)[0];

    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] < temp) {
        arr.splice(j + 1, 0, temp);
        break;
      }

      if (j === 0 && temp < arr[j]) {
        arr.unshift(temp);
      }
    }
  }

  return arr;
}

저는 배열을 argument로 전달 받은 후 loop를 한 번 진행했습니다. 그리고, 어느 지점까지 배열이 순차적으로 정리되어 있는지 확인을 한 번 거친 후, 정리간 안 된 인덱스부터 Insertion Sort를 진행했습니다. 이 부분은 생략을 하고 배열의 처음부터 차례로 정렬을 진행해도 됩니다.

위 insertionSort 함수가 compare function을 argument로 받을 수 있도록 코드를 수정할 수 있습니다. 만약 compare function이 undefined일 경우를 대비해 default로 Array.sort compareFunction을 지정하도록 하겠습니다.

이 compare function을 비교하는 두 요소의 값이 같을 때 우선 순위를 정하도록 사용하여, 안정정렬이 될 수 있도록 사용할 수 있습니다. 아래의 코드는 Array.sort 메소드의 compareFunction을 참고한 default function을 별도로 작성한 것입니다.

function defaultFunction(a, b) {
  if (a < b) {
    return -1;
  } else if (a > b) {
    return 1;
  }

  return 0;
}

이제 compare function을 위에서 작성한 insertFunction 함수에 추가해 보도록 하겠습니다.

function insertionSort(arr, comparator) {
  let flag = 0;
  comparator = comparator || defaultFunction;

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      break;
    }

    if (arr[i] < arr[i + 1]) {
      flag = i + 1;
    }
  }

  for (let i = flag + 1; i <= arr.length - 1; i++) {
    let temp = arr.splice(i, 1)[0];

    for (let j = i - 1; j >= 0; j--) {
      if (comparator(arr[j], temp) < 0) {
        arr.splice(j + 1, 0, temp);
        break;
      }

      if (j === 0 && temp < arr[j]) {
        arr.unshift(temp);
      }
    }
  }

  return arr;
}

위와 같이 argument로 배열과 compareFunction을 전달 받아 insertion sort로 졍렬을 진행하는 알고리즘을 작성했습니다. 배열에서 loop를 돌며 splice 메서드를 사용했는데, 사실 iteration 중 splice를 사용하는 것은 index가 변형되기 때문에 오류를 발생시킬 수 있습니다. 이번에는 splice를 사용하지 않고 insertion sort를 작성해 보았습니다.

function insertionSort(arr, comparator) {
  comparator = comparator || defaultFunction;

  // start at index 1 as sublist of arr[0] is already sorted;
  for (let idx = 1; idx < arr.length; i++) {
    let value = arr[idx];
    let compareIdx = idx - 1;

    while (compareIdx >= 0 && comparator(arr[compareIdx], value) > 0) {
      arr = swap(arr, compareIdx, idx);
      idx = compareIdx;
      compareIdx--;
    }
  }

  return arr;
}

function swap(array, i1, i2) {
  let temp = array[i1];

  array[i1] = array[i2];
  array[i2] = temp;

  return array;
}

병합정렬(Merge-Sort)

합병정렬은 분할정복(Divide and conquer) 방식의 알고리즘입니다. 말그대로 배열을 둘로 쪼갠 후 두 배열의 각 요소를 비교해가며, 하나의 새로운 배열을 만들어가는 방식입니다. merge-sort는 위에서 살펴본 bubble-sort, selection-sort, insertion-sort 보다 좀 더 빠른 시간복잡도를 가집니다. 이는 중복된 loop를 사용하지 않기 때문입니다. 따라서, 우리가 정렬을 할 때 많이 사용하게 될 정렬 방식입니다. Array.prototype.sort도 대부분 merge sort를 사용한다고 하고, firefox의 자바스크립트 엔진은 데이터 타입에 따라 quick sort를 사용하는 경우도 있다고 합니다.

Merge-sort는 recursion을 사용합니다. Argument로 전달 받은 list를 둘로 쪼갠 후, 둘로 나뉜 list에 다시 recursive call을 적용합니다. Recursion의 base case는 list에 한 개의 요소가 남아있을 때입니다. Recursion call이 base case에 도달하면, 쪼개진 리스트들을 낮은 숫자가 앞쪽에 위치하도록 다시 합치며 최종적으로 하나의 리스트를 도출합니다.

merge-sort는 유일하게 시간복잡도가 O(n log n)으로 안정화된 알고리즘입니다. 이것은 이상하게 느껴질 수도 있습니다. 위에서 살펴본 정렬방식은 각각의 요소를 한번씩 비교했고, 시간복잡도가 exponential이었습니다. Merge-sort는 쪼개진 리스트에서 비교를 합니다.

Merge-sort는 recursion을 진행할수록 새로운 리스트를 생성하기 때문에, 공간복잡도는 위의 다른 정렬방식보다 좋지 못 한 O(n)입니다. 나쁘지는 않지만 인지할 필요는 있습니다. Merge-sort는 stable 합니다. 그래서 두 값이 같을때 기존의 순서를 유지합니다.

코드로 바로 작성하기 전 쪼개진 리스트를 다시 합치는 과정의 pseudocode를 먼저 작성해 보았습니다.

merge(L, R)

Lpointer = 0;
Rpointer = 0;
newArr = [];

Loop until L.length === Lpointer and R.length === Rpointer
  if L[Lpointer] is less than R[Rpointer]
    push L[Lpointer] to a new array
    increment Lpointer
  else
    push R[Rpointer] to a new array
    increment Rpointer

그리고 아래는 merge-sort의 전체 과정의 pseudocode 입니다. 개인적으로 이렇게 알고리즘을 어떻게 짤지 큰 부분을 사전에 생각하고 코드를 쓰면, 코드가 좀 더 수월하게 쓰여지는것 같습니다. 하지만 어떤식으로 코딩할지 생각해 내는 것이 또한 가장 어려운 것 같습니다.

mergeSort(list)

  • base case: if list.length < 2, return
  • break the list into halves L and R
  • Lsorted = mergeSort(L);
  • Rsorted = mergeSort(R);
  • return merge(Lsorted, Rsorted)

아래는 위에서 정리한 개념을 바탕으로 merge-sort를 작성했습니다. 코드를 한 번에 쭉 쓰고 테스트를 몇 개 했는데 문제가 없었습니다. 제가 이렇게 한 번에 깨끗한 코드를 쓴적이 거의 없는데 기분이 사뭇 좋네요...;;

function recursiveMergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }

  let mid = Math.floor(arr.length / 2);
  let leftArr = recursiveMergeSort(arr.slice(0, mid));
  let rightArr = recursiveMergeSort(arr.slice(mid));

  return merge(leftArr, rightArr);
}

function merge(left, right) {
  const sortedArr = [];

  while (left.length !== 0 && right.length !== 0) {
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  return sortedArr.concat(left, right);
}

merger 함수를 argument 배열을 건드리지 않고 진행하고 싶으면 아래와 같은 방식으로 할 수도 있지만 가독성이 떨어져서 개인적으로 별로인 것 같습니다.

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

  while (result.length < left.length + right.length) {
    if (leftIdx === left.length) {
      result.concat(right.slice(rightIdx));
    }

    if (rightIdx === right.length) {
      result.concat(left.slice(leftIdx));
    } else if (left[leftIdx] <= right[rightIdx]) {
      result.push(left[leftIdx++]);
    } else {
      result.push(right[rightIdx++]);
    }
  }

  return result;
}

위에서 recursion을 사용했고, 아래는 반복문을 사용해 merge-sort를 구현해 보았습니다.

function mergeSort(arr) {
  let splitArr = arr.map(el => [el]);

  while (splitArr.length > 1) {
    let result = [];

    for (let i = 0; i < splitArr.length; i += 2) {
      if (splitArr[i + 1]) {
        result.push(merge(splitArr[i], splitArr[i + 1]));
      } else {
        result.push(splitArr[i]);
      }
    }

    splitArr = result;
  }

  return splitArr[0];
}

퀵정렬(Quick-Sort)

Quick-sort는 또다른 분할정복(divide and conquer) 방식의 알고리즘입니다. Quick-Sort의 기본적인 개념은 배열 내 중심축(pivot)이 될 요소를 정하고, pivot보다 작으면 왼쪽 배열에, pivot보다 크면 오른쪽 배열로 분류 후 각각의 배열에 recusrive call을 적용하는 것입니다. 최종적으로는 왼쪽과, pivot, 오른쪽 배열을 하나로 합친 정렬된 배열을 도출합니다.

퀵정렬의 시간복잡도는 일반적으로 O(nlogn)입니다. 하지만, 경우에 따라 정렬된 배열에 quick-sort를 적용하면 좋지 못 한 성능을 보입니다.

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

  const pivot = [arr.pop()];
  const left = quickSort(arr.filter(el => el <= pivot[0]));
  const right = quickSort(arr.filter(el => el > pivot[0]));

  return left.concat(pivot, right);
}

위아 같이 quick-sort를 작성했습니다. Built-in method 이긴 하지만 filter 메소드를 두 번 사용했습니다. 그리고 argument로 전달 받은 원본 배열도 매 execution context마다 수정을 했습니다. 이부분을 피하고 싶으면 아래와 같이 작성할 수도 있습니다.

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

  const pivot = arr.slice(-1);
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

Quick-Sort in place

별도의 메모리 공간을 사용하지 않으려면, quick-sort in place로 구현해야하며, 대신 로직이 조금 더 길어집니다. Merge-Sort가 배열을 쪼갠 후 병합하는 과정에서 정렬이 이루어 졌다면, quick-sort는 그 반대입니다. Pivot을 선정하고 배열을 둘로 나누는 partition과정에서 모든 작업이 이루어집니다. 둘로 나뉜 배열에 각각 recursion call 을 적용합니다. 저는 Pivot을 배열의 맨 마지막 요소로 정하고 아래와 같이 먼저 pseudocode를 작성했습니다.

- partition(arr, first, last)
    - choose last element as pivot
    - keep track of pivotLoc (초기값 = 0)

    - for loop from beginning
        - if current arr[pivotLoc] <= pivot
            - increment pivotLoc
        - else
            - swap arr[pivotLoc] to pivot
            - swap pivot to arr[last]

위의 pseudocode를 바탕으로 quick sort 함수를 작성하면 아래와 같습니다. quick sort에서 아래 함수 자체는 정렬에 관여하는 로직이 있지는 않아요. 정력 자체는 partition을 나누는 과정에서 진행됩니다.

function quickSort(arr, low, high) {
  if (low < high) {
    let pivotNum = partition(arr, low, high);

    quickSort(arr, low, pivotNum - 1);
    quickSort(arr, pivotNum + 1, high);
  }

  if (high - low === arr.length - 1) {
    return arr;
  }
}

아래 partition 함수를 통해 pivot을 정하고, pivot을 기준으로 왼쪽, 오른쪽 요소를 정렬합니다.

function partition(arr, pivotLoc, pivot) {
  while (pivotLoc !== pivot) {
    if (arr[pivotLoc] > arr[pivot]) {
      swap(arr, pivotLoc, pivot);
      swap(arr, pivotLoc, --pivot);
    } else {
      pivotLoc++;
    }
  }
}

partition 함수를 for loop으로도 구현할 수 있는데 아래의 코드에 대해, 좀 더 세세히 알고 싶은신 분은 Lumoto partiton scheme을 검색해 보시길 바랍니다.

function partition(arr, low, high) {
  let pivot = arr[high];
  let pivotLoc = low;

  for (let i = low; i < high; i++) {
    if (arr[i] <= pivot) {
      swap(arr, pivotLoc, i);
      pivotLoc++;
    }
  }

  swap(arr, pivotLoc, high);

  return pivotLoc;
}

위와 같이 배열 내에서 pivot을 선정하고, 그것을 기준으로 작은 수는 pivot 앞쪽에 큰 수는 pivot 뒤쪽에 위치시키는 함수를 작성했습니다.

© Chanwhe Kim 2019

Handmade with .