[정렬] Javascript로 정렬 알고리즘 공부하기

가장 기본적인 정렬 알고리즘부터 복기 중! 안보고 칠 수 있을 정도로 해둬야 까먹지 않는 거 같다.

지금까지, C++, Python으로는 많이 했었는데 이제 자바스크립트로도 알고리즘 문제를 어느정도 풀고 싶어졌다.

 

1. 선택 정렬(Selection sort)

 

요약: 최소값을 뽑아서 첫번째 인덱스부터 swap

시간복잡도: O(n^2)

 

function selectionSort (arr) {
  var len=arr.length
  for (var i=0;i<len-1;i++) {
    var minIdx = i;
 
    for (var j=i+1;j<len;j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }
    if (i !== minIdx) {
      var tmp = arr[i];
      arr[i] = arr[minIdx];
      arr[minIdx] = tmp;
    }
  }
 
  return arr;
}

 

2. 삽입 정렬(Insertion sort)

 

요약: 0~k와 k+1 인덱스요소를 비교해가면서 swap해나감

시간복잡도: O(n^2)

 

function insertionSort (arr) {
  var len = arr.length;
 
  for (var i=0;i<len;i++) {
    for (var j=i-1;j>-1;j--) {
      if (arr[j+1] < arr[j]) {
        var tmp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = tmp;
      }  
    }
  }
 
  return arr;
}

 

3. 거품 정렬(Bubble sort)

 

요약: k인덱스와 k+1을 비교하면서 swap

시간복잡도: O(n^2)

 

function bubblesort (arr) {
  var len = arr.length;
  for (var i=0;i<len;i++) {
    for (var j = 0; j< len-i;j++) {
      if (j+1 < len && arr[j] > arr[j+1]) {
        var tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
 
  return arr;
}

 

 

4. 병합 정렬(merge sort)

 

요약: 배열을 반씩 재귀적으로 쪼개어 합치면서 정렬함 (분할·정복-병합)

시간복잡도: O(nlogn)

 

function merge (arr, l, m, r) {
  var i = l, j = m+1, k=l;
  var tmpArr=[];
 
  while (i <= m && j <= r) {
    if (arr[i] > arr[j]) {
      tmpArr[k++] = arr[j++]
    } else {
      tmpArr[k++] = arr[i++];
    }
  }
 
  var restIdx = i, endIdx = m;
 
  if (i>m) {
    restIdx=j, endIdx=r;
  }
 
  for (var n=restIdx;n<=endIdx;n++) {
    tmpArr[k++] = arr[n];
  }
 
  for (var n=l;n<=r;n++) {
    arr[n] = tmpArr[n];
  }
}
 
function mergeSort (arr, left, right) {
  if (left < right) {
    var mid = Math.floor((left + right)/2);
 
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
    merge(arr, left, mid, right);
  }
}

 

5.  계수 정렬(Counting sort)

 

요약: 각 숫자가  몇 개씩 등장하는지 세어서 반복되는 횟수만큼 정렬

시간복잡도: O(n+k) if n> k, O(infinite) if n < k (k는 배열 중 가장 큰 값)

 

k가 배열의 개수보다 너~~~무 크면 O(n^2,3,...)이 될 수 있음

 

function countingSort (arr) {
  var maximum = Math.max(...arr);
 
  var counters = new Array(maximum);
 
  counters.fill(0);
 
  for (var i=0;i<arr.length;i++) {
    var idx = arr[i];
 
    counters[idx]++;
  }
 
  var result = [];
 
  for (var i=0;i<counters.length;i++) {
    if (counters[i] > 0) {
      var subArr = new Array(counters[i]);
      subArr.fill(i);
 
      result = result.concat(subArr);
    }
  }
 
  return result;
}

 

따라서 누적합 배열을 만들어 등장 횟수를 저장한다.

 

이 때 누적합 배열의 값은 해당 숫자가 처음 들어갈 인덱스를 의미한다. 정렬을 하면서 해당 숫자가 들어갈 인덱스를 보고 그 인덱스에 대입 후 counter배열의 해당 횟수를 하나씩 차감한다.

 

5-1. 누적합 배열 적용한 계수 정렬

 

function countingSort (arr) {
  var maximum = Math.max(...arr);
 
  var counters = new Array(maximum+1);
 
  counters.fill(0);
 
  for (var i=0;i<arr.length;i++) {
    var idx = arr[i];
 
    counters[idx]++;
  }
 
  // 누적합 배열 만듦
  for (var i=0;i<counters.length-1;i++) {
    counters[i+1] += counters[i];
  }
 
  var result = [];
 
  // 앞, 뒤 순서 구분없음
  for (var i=arr.length-1;i>=0;i--) {
    var idx = arr[i];
    counters[idx] > 0 && 
    (result[counters[idx]] = idx),
    counters[idx]--;
  }
 
  result.shift(); // 앞 인덱스가 비어있음
  
  return result;
}

 

6. 빠른 정렬(Quick sort: In-place / Not-in-place)

요약: 특정 요소를 기준(pivot)으로 삼아 기준보다 큰 값들과 작은 값들을 분리하여 재귀적으로 정렬해나감

시간복잡도: O(nlogn) (Best)

 

추가 공간을 사용하는여부에 따라 구현 방법이 다르다.

 

6-1. Not-in-place

 

요약: 정렬을 위한 추가 공간을 활용하여 재귀적으로 정렬

 

function quickSort (arr) {
  if (arr.length <= 1) return arr;
 
  var pivot=arr[0];
  var left=[], right=[], same=[pivot];
 
  for (var i=1;i<arr.length;i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else if (arr[i] > pivot) {
      right.push(arr[i])
    } else {
      same.push(arr[i])
    }
  }
 
  var sortedLeft = quickSort(left);
  var sortedRight = quickSort(right);
 
  var merged = sortedLeft.concat(same);
  var result = merged.concat(sortedRight);
 
  return result;
}

 

6-2. In-place

 

요약: 정렬할 배열 내에서 pivot을 기준으로 왼쪽엔 pivot보다 작은 수, 오른쪽엔 pivot보다 큰 수로 나누어 나뉜 인덱스를 기준으로 재귀적으로 반족하여 빠른 정렬을 수행

 

function quickSortInPlace (array, start=0, end=array.length-1) {
  if (start >= end) return;
  let mid = Math.floor((start + end)/2);
  let pivot = array[mid];
 
  const division = divide(array, start, end, pivot);
 
  quickSortInPlace(array, start, division-1);
  quickSortInPlace(array, division, end);
 
  function divide(array, left, right, pivot) {
    while (left <= right) {
      while (pivot > array[left]) {
        left++;
      }
      while (pivot < array[right]) {
        right--;
      }
 
      if (left <= right) {
        let tmp = array[right];
        array[right] = array[left];
        array[left] = tmp;
 
        left++;
        right--;
      }
    }
    return left;
  }
  return array;
}

 

기억에 남는 문제 1

 

요약: 굵은 글씨 조건을 만족하는 삼각형이 존재할 시 1, 아니면 0

(출처: https://jobjava00.github.io/algorithm/codility/lesson6/Triangle/)

 

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
For example, consider array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1

the function should return 0.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

 

정렬된 상태라면 A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]는 무조건 만족하므로 A[P] + A[Q] > A[R]만 고려하면 된다.

 

따라서 배열을 우선 정렬해야 한다.

 

function solution(A) {
    // 정렬된 상태라면 첫번째+마지막 > 중간, 중간+마지막 > 첫번째 이 두 조건은 무조건 만족하므로 패스하고 P+Q>R 만 체크
    
    function compare(a, b) {
        return a-b;
    }
    
    A.sort(compare);
    
    for (var i=0;i<A.length-2;i++) {
        var P = A[i], Q=A[i+1], R=A[i+2];
        
        if (P+Q > R) return 1;
    }
    
    return 0;
}