알고리즘 & 자료구조 9,10주차 스터디[합병,퀵, 기수]

Jun 7, 2023 🐰

🤯 오늘 배울 개념은 SortSort!!!!

• sort Algorithmes는 무엇일까?
  정렬 알고리즘은 컬렉션의 항목을 재배열하는 과정이다. 영화, 데이터, 객체, 연도, 국내 수익 등등에 사용할 수 있다.

🔑 Merge Sort

일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘

분할, 정렬, 합병 세가지가 모두 일어난다.
0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용
배열을 더 작은 배열로 나누는 방식, 분할 정복 알고리즘이라고 알려짐 , 계속 분할시킨 후 합친다.

• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

👩🏻‍🌾 Merge Sort function

• slice 사용하기 , 재귀 사용하기

function merge(arr1, arr2) {
  let results = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr2[j] > arr1[i]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  return results;
}

//재귀를 사용
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  //slice 를 통해 0~ mid
  let left = mergeSort(arr.slice(0, mid));
  //slice 를 통해 mid~ end
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

const result2 = mergeSort([10, 24, 76, 73, 72, 1, 9]);
const result1 = merge([1, 10, 50], [2, 14, 99, 100]);
console.log(result2);

👩🏻‍🌾 Merge Sort 시간 복잡도

🔑 Quick Sort

퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

• 재귀를 통해 해결하기 가장 쉬운 방식
• 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식이다.
• 피벗 포인트라 부르는 단일 요소를 선택하여 수행

👩🏻‍🌾 Quick Sort function

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

function pivot(arr, start = 0, end = arr.length + 1) {
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  var pivot = arr[start];
  var swapIdx = start;

  for (var i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
      console.log(arr);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  //재귀의 종료 조건을 추가.
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    //left
    quickSort(arr, left, pivotIndex - 1);
    //right
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

let re = quickSort([4, 8, 2, 1, 5, 7, 6, 3]);
console.log(re);

👩🏻‍🌾 Quick Sort 시간 복잡도

🔑 Radix Sort

비교를 수행하지 않는 특별한 정렬 알고리즘, 숫자로 작동한다. (이진 사용)
숫자 크기에 대한 정보를 자릿수로 인코딩한다.

1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다.
2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.
3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.
4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.

👩🏻‍🌾 Radix Sort function

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

function radixSort(nums) {
  let maxDigitCount = mostDigits(nums);
  for (let k = 0; k < maxDigitCount; k++) {
    let digitBuckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < nums.length; i++) {
      let digit = getDigit(nums[i], k);
      digitBuckets[digit].push(nums[i]);
    }
    nums = [].concat(...digitBuckets);
  }
  return nums;
}

radixSort([23, 345, 5467, 12, 2345, 9852]);

👩🏻‍🌾 Radix Sort 시간 복잡도

1. 시간 복잡도는 O(nk)
2. 자리수가 고정되어 있어서 안정성이 있는 정렬 방식

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure