[자바스크립트] 정렬 구현해보기

정렬 구현

JS

 

버블 정렬

버블 정렬은 두 인접 원소를 검사해 정렬 하는 방법입니다. 아래와 같은 gif 파일 처럼 정렬을 시작하고 구현이 단순하다는 장점이 있습니다. 하지만 시간 복잡도가 평균, 최상, 최악 모두 O(N^2) 으로 굉장히 비효율적인 정렬 알고리즘 입니다.

https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif

function bubbleSort(array) {
  // 인덱스와 바로 옆에 있는 인덱스 + 1 값을 비교하기 때문에 i 는 array.length - 1 까지
  for (let i = 0; i < array.length - 1; i++) {
  
    // 맨 마지막 숫자를 고정시키기 때문에 회전을 거듭 할 수록 i 만큼 빼줘야 함
    for (let j = 0; j < array.length - (1 + i); j++) {
    
      if (array[j] > array[j + 1]) {
      
        // 구조 분해 할당 구문을 사용
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

 

 

선택 정렬

선택 정렬은 in-place sorting 알고리즘 입니다. 때문에 다른 추가적인 메모리를 요구하지 않습니다. 매 회전의 초기마다 idx 를 통해 현재 인덱스를 저장합니다. 이후에 자기보다 뒤에 있는 인덱스를 순회하면서 최소값을 가지는 인덱스를 찾는 방식으로 진행됩니다.

 

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Selection-Sort-Animation.gif

만약 초기의 인덱스가 바뀌지 않았다면 (자기 자신이 최소값인 경우라면) swap 을 진행하지 않습니다. 마지막 인덱스는 정렬해주지 않아도 정렬되기 때문에 배열의 length 의 -1 만큼만 반복합니다. 버블 정렬과 마찬가지로 최악, 평균, 최선 모두 O(N^2) 의 시간 복잡도를 가지게 됩니다.

 

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    // idx 는 현재 인덱스. 1씩 증가할 예정.
    let idx = i;

    // i + 1 부터 시작하는 j 를 통해 최소값을 찾아 나간다.
    for (let j = i + 1; j < array.length; j++) {
      
      // 만약 최소값이라면 idx 의 인덱스를 바꿔준다.
      if (array[idx] > array[j]) {
        idx = j;
      }
    }

    // idx 가 i 가 아닌 경우, 즉 자기보다 작은 값이 존재했던 경우에만 swap
    if (idx !== i) {

      // 구조 분해 할당을 통해 구현 가능
      [array[idx], array[i]] = [array[i], array[idx]];
    }
  }

  return array;
}

삽입 정렬

삽입 정렬은 인덱스의 값부터 시작해서 앞의 요소들과 비교하여 자기가 들어갈 위치를 찾아 삽입하는 정렬 알고리즘입니다. 아래의 gif 파일처럼 진행됩니다.

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

첫 번째 값(인덱스가 0)은 비교할 대상이 없으므로 패스하고 2 번째 값(인덱스 1)부터 시작합니다. 이후 이전 값들을 확인하며 삽입 될 위치를 찾아 나갑니다. 삽입 정렬의 경우 선택한 값의 이전 인덱스까지 전부 정렬되어 나갑니다. 아래와 같이 구현이 가능합니다.

function insertionSort(array) {
  let j = 0;
  for (let i = 1; i < array.length; i++) {
    // 뽑은 값을 고정
    const temp = array[i];

    for (j = i - 1; j >= 0; j--) {
    
      // 만약 뽑은 값보다 왼쪽의 값이 크면 스왑
      if (temp < array[j]) {
        array[j + 1] = array[j];
      } else break;
    }
    
    // 반복문에서 -1 됬으니 j + 1 에 temp 를 할당 (정렬)
    array[j + 1] = temp;
  }
  return array;
}

temp 를 사용하지 않고 array[i] 를 사용하면 안되나요?

변수를 최대한 사용하지 않는 것은 좋은 생각입니다. 하지만 지금은 array 의 값들을 계속해서 바꿔 나가고 있습니다. 이는 처음에 생각하던 array[i] 의 값과 정렬이 시작되고 나서의 array[i] 의 값이 달라질 수 있다는 것을 의미합니다. 따라서 array[i] 의 값을 temp 에 고정해 놓는것이 보다 더 안전하게 사용이 가능합니다.

마무리

요새 프론트엔드 개발자는 자바스크립트로만 알고리즘 테스트를 (코딩 테스트) 를 보는 곳이 많아지기 시작했습니다. 이를 대비해서 자바스크립트로 그동안 공부했던 알고리즘에 대해서 조금씩 정리해 나가고자 합니다. 읽어주셔서 감사합니다!