2023.04.03[유클리드 호제법, 퀵 정렬]

📖오늘 배운  것

 

유클리드 호제법

유클리드 호제법은 2개의 자연수 사이의 최대공약수를 구하는 알고리즘의 하나이다.

 

원리

1. 큰 수를 작은 수로 나눈다.

2. 나머지가 0이면 작은 수가 최대 공약수

3. 나머지가 0이 아니라면 작은 수를 나머지로 나눈다.

4. 나머지가 0이 될 때까지 반복.

 

자바스크립트로 구현

function gcd(a, b) {
  const rest = a % b;
  if (remainder === 0) return b;  
  return gcd(b, rest); 
}

 

퀵 정렬

: 배열의 요소가 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식

: 하나의 요소를 선택해서(pivot) 그 숫자를 기준으로 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 옮긴다. 옮기는 숫자는 정렬하는 것이 아니라 단순히 옮겨지는 것이고 올바른 위치에 정렬되는 것은 선택된 해당 숫자 하나뿐이게 되는 것이다.

 

 

Pivot Helper

배열이 주어지면 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function pivot(arr, start=0, end=arr.length+1) {
  let pivot = arr[start];
  let swapIdx = start; 
  
  for(let i = start + 1; i<arr.length; i++) {
    if(pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i)
    }
  }
  
  swap(arr, start, swapIdx);
  return swapIdx;
}

 

퀵 정렬 구현

function quickSort(arr, left = 0, rigth = arr.length - 1) {
  if(left < right) {
    let privotIndex = privot(arr, left, right)
    quickSort(arr, left, privotIndex- 1);
    quickSort(arr, privotIndex + 1, right);
  }
  return arr;
}

 

빅오 복잡도

best

배열을 분해할 때 log n개로 분해된다. O(log n)

그리고 해당 배열에서 피벗을 정할 때 O(n)으로 비교를 하기 때문에 베스트의 경우 O(n log n)이 된다.

 

worst

만약 데이터가 이미 정렬되어 있고 피벗을 첫번째 요소로 찾을 때

이미 정렬되어 있기 때문에 데이터가 2개로 분해되지 않고 하나의 하위요소로 나눠진다. 따라서 15개라면 15번 분해하는 셈. 따라서 분해가 O(n)걸리게 된다.

그리고 각각 분해할 때마다 O(n)의 비교를 하기 때문에 최악의 경우 O(n^2)이 걸린다.

이 문제를 해결하기 위해선 데이터가 정렬되어 있는 경우 피벗을 첫 번째 요소가 아니라 무작위 또는 중간 요소로 고르면 된다.

 

 

💭배운 점

유클리드 호제법 분명 전에 해봤을텐데 너무 생소했다. 이런 건 좀 외워둬야할 것 같다! 재귀 강의도 듣고 하니까 그 전보다 개념이 더 잘 이해되는 것 같았다. 재귀..조금은 익숙해졌을지도 ? ㅎㅎ 라고 생각했더니 아니었다.

퀵 정렬도 개념은 이해가 가는데 혼자 구현하라고 하면 못할 것 같다. 재귀 저렇게 쓰는 거 너무 어려워... 그래도 강의 같이 들으면서 이해하면 혼자 이해할 때보다 훨씬 잘 이해되는 것 같다. 코드도 따라 치고 손으로 글씨도 써보면서 흐름을 잘 이해해두면 다른 알고리즘 구현 할 때도 도움이 될 것 같다!