정렬

https://youtu.be/kPRA0W1kECg

 

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

왜 배울까

- 정렬이 프로그래밍에서 정말 흔하게 사용되기 때문

- 데이터를 정렬하는 알고리즘은 많고 각각 장단점이 있다

 

알고리즘	시간복잡도(Best)	시간복잡도(평균)	시간복잡도(Worst)	공간 복잡도
버블 정렬	O(n)	O(n²)	O(n²)	O(1)
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)
합병 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)
기수 정렬	O(nk)	O(nk)	O(nk)	O(n+k)

 

 

버블 정렬

서로 인접한 두 원소를 검사하여 정렬 -> 가장 큰 자료를 뒤로 보내는 방식이다.

만약, 거의 정렬되어 있는 데이터라면 버블 정렬 사용시 더 이상 정렬될 데이터가 없어도 끝까지 실행할 될것이다

[8,1,2,3,4,5] 이런 배열을 버블정렬시 첫번째 루프에 배열이 정렬되는 것을 알 수 있지만 이 알고리즘은 끝까지 실행한다

아래 예시에서 최적화된 버블정렬과 일반 버블정렬을 비교해보길 바란다

 

기본적인 동작은 교환이다.

function swap(arr,idx1,idx2){
  let temp=arr[idx1]
  arr[idx1]=arr[idx2]
  arr[idx2]=temp
}

const swap=(arr,idx1,idx2){
  [arr[idx1],arr[idx2]]=[arr[idx2],arr[idx1]]
}

버블 정렬 구현

function bubbleSort(arr){
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i-1;  j++) {
      console.log(arr,arr[j],arr[j+1]);
      if(arr[j] > arr[j+1]){
        // let temp=arr[j]
        // arr[j]=arr[j+1]
        // arr[j+1]=temp
        [arr[j],arr[j+1]]=[arr[j+1],arr[j]]
      }
    }
  }
}

bubbleSort([37,46,20,8])

버블 정렬 최적화

function bubbleSort(arr){
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    noSwaps=true;
    for (let j = 0; j < i-1;  j++) {
      console.log(arr,arr[j],arr[j+1]);
      if(arr[j] > arr[j+1]){
        let temp=arr[j]
        arr[j]=arr[j+1]
        arr[j+1]=temp
        noSwaps=false
      }
    }
    if(noSwaps) break;
  }
  return arr
}

bubbleSort([8,1,2,3,4,5,6,7])

선택 정렬

버블 정렬과 비슷하지만, 가장 작은 최소 값을 맨 앞에 정렬시킨다 

[19,44,38,5,47,15] -> 첫번째 요소인 19를 가지고 계속 비교해 나간다 19 44 / 19 38 / 19 5 (여기서 최솟값이 바뀜)

5,47 / 5,15 여기까지 비교하고 5가 최소값인것을 알았으니 첫번째로 선택된 19와 5를 바꾼다.

[5,44,38,19,47,15] - > 5는 정렬됬기 때문에 44부터 시작한다

이어서 쭉 진행...

 

function selectionSort(arr){
  for (let i = 0; i < arr.length; i++) {
    let lowest=i;
    for (let j = i+1; j < arr.length; j++) {
      if(arr[lowest]>arr[j]){
        lowest=j
      }
    }
    if(i!==lowest){
    console.log(arr,arr[i],arr[lowest]);
    console.log(i,lowest); // 0 , 3
    let temp=arr[i] // temp 19
    arr[i]=arr[lowest] // arr[i]는 19 arr[lowest]는 5 -> arr[i] 5가됨
    arr[lowest]=temp // arr[lowest]는 19
    }
  }
  return arr
}


selectionSort([19,44,38,5,47,15])

삽입 정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자기 위치에 맞게 삽입해서 정렬시킨다

즉, 2번째 요소부터 시작해서 앞에 원소들과 비교하면서 정렬시킴

[5,3,4,1,2] 3이랑 5를 비교 -> [3,5,4,1,2] 4랑 3,5를 비교 ->[3,4,5,1,2] -> 3,4,5와 1을 비교 -> [1,3,4,5,2] 2와 나머지 비교 ->

[1,2,3,4,5] 

 

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    for (var j = i-1 ; j > -1 && arr[j]>current ; j--) {
        arr[j+1]=arr[j]
    }
    arr[j+1]=current
    console.log(arr);
  }
}

insertionSort([2,1,6,18,5])

 

합볍 정렬

합병 + 정렬

0개 요소,1개 요소 배열이 이미  정렬되있고 그걸 활용해서 배열을 더 작은 배열로 나누는 방식이다(분할 정복)

[8,3,5,4,7,6,1,2]

-> [8,3,5,4] [7,6,1,2] 로 분할하고 이걸을 또 [8,3] [5,4]... -> [8] [3] .. 으로 분할하고 각 값을 비교해서 작은 값이 앞에 오도록 합친다 [3,8] [4,5] ... [1,2] 이후 계속 합쳐나간다 [3,4,5,8] [1,2,6,7] -> [1,2,3,4,5,6,7,8]

 

합병 정렬의 Big O

O(n log n) ?

위에 예시에서 [8,3,5,4,7,6,1,2] 이 배열이 [8],[3].... [1] ,[2]인 단일 요소 배열이 되려면 3번을 나눠야 한다

만약 32개의 배열이 있다면 32 -> 16 16 -> 8 8 8 8 -> 4 4 4 4 4 4 4 4 -> 2 2 2 .... 2 -> 1 1 1 .... 1 1 이런식으로 총 5번 분할

n=8이면 3 => 2*2*2  / n=32 이면 5 => 2*2*2*2*2 즉, O(log n)이라는 것을 알수 있고 합병할 때 숫자 하나씩 큰지 작은지

비교되기에 O(n) 비교가 수행되는 것이다. 만약 n의 길이가 늘어난다면 합병 알고리즘 자체는 O(n)이고 합병 정렬은

O(log n)이기에 O(n log n)이 되는것

 

합병 Helper

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;
}

재귀로 구현하는 합병정렬

위에 작성한 합병정렬 프로그램을 사용해야한다

- 하나의 배열을 두 개로 쪼개고 -> 합병 정렬을 다시 호출하고 다시 반으로 쪼갠다 (계속 재귀) -> 만약 배열 길이가 1보다 작으면 멈추고 배열 반환 -> 다시 합쳐서 합병 정렬을 완료 시킨다

function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

mergeSort([10,24,76,73])

퀵 정렬

합병 정렬과 비슷하게 배열에 0개 , 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식

피벗 포인트(pivot) 라는 단일 요소를 선택해서 정렬된 배열에서 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의

왼쪽으로 옮겨지고 피벗보다 큰 요소들은 오른쪽으로 옮겨진다

피벗을 제외한 왼쪽 배열 / 오른쪽 배열을 똑같은 방식으로 정렬한다

 

Big O는 합병 정렬과 같은 n log n 이지만 가장 나쁜 케이스에서는 O(n²)이다 -> 데이터가 이미 정렬되어 있을 경우

정렬되어 있는 배열에서는 피벗을 각각 한개 씩 선택하고 반환시키면서 오른쪽으로 움직인다고 생각하자

[1,2,3,4,5..9] -> 1 [2,3,4...9] -> 1 2 [3,4,...9] 이런식으로 각각에 대해 수행되니 O(n)이고 각각 분해할때 마다 비교를 수행해서 작은 값과 큰 값을 구분해야하므로 O(n)이 또 생기고 그래서 O(n²)이다.

-> 이 문제는 피벗을 가장자리를 선택했을 때 생기는 문제고 가장자리를 제외한 다른 무작위 위치(무작위 수 , 중간 값)에 피벗을 정하면 정렬된 배열일 경우라도 이 문제를 피할 수 있다. -> 하지만 최솟값이나 최대값을 피벗으로 정하면 O(n²)은 피할 수 없다

 

퀵 Helper

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };


  let pivot = arr[start];
  let swapIdx = start;

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

  
  swap(arr, start, swapIdx);
  return swapIdx;
}

퀵정렬

function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
}

*설명 필요

 

기수 정렬(Radix Sort)

비교를 하지 않고, 정렬을 시키는 알고리즘

숫자로 작동을 하고, 이진수를 이용하면 다른 데이터를 이진수로 변환시켜서 비교하는 것이 가능하다

숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다

버킷을 사용해서 숫자 자릿수별로 분류하는 작업을 먼저한다 분류할때 숫자들중 가장 큰 자릿수를 가진 숫자에 따라서

몇 번 분류될지 결정된다

버킷은 몇진수인지에 따라서 갯수가 달라진다 -> 이진수면 2개, 7진수면 7개 10진수면 10개 

버킷은 0~9 까지 자릿수별로 분류해주는 바구니라고 생각하면 된다

여기 배열에서는 3자리수가 가장 크고 따라서 분류를 3번하게된다

 

1. 숫자의 뒷자리로만 분류하기

배열의 왼쪽에서 시작해서 101의 가장 오른쪽 자리의 수는 1 / 1은 1/ 20은 0

... 899는 9해서 버킷에 맞게 넣고 넣은 0 버킷에서부터 차례대로 숫자를 꺼내서 다시 정렬시킨다

 

2. 가장 오른쪽자리가 정렬됬기 때문에 중간자리로 넘어간다 (자릿수 기준은 항상 가장 큰 자릿수)

20에서는 2 / 50에서는 5 / 101에서는 0 .... 899는 9 이런식으로 정렬한다

 

3. 정렬이 완료된 숫자들은 한쪽에 순서대로 모아두고 남은 숫자(가장 큰 자릿수를 가진 수)들을 정렬시킨 후 그 순서대로

배열을 반환 시킨다

 

기수정렬의 Big O 

O(nk) 인데 n은 배열의 길이, k는 자릿수를 의미한다 /  

기수 정렬 Helper

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

getDigit(12345,3) //4

function digitCount(num){
  if(num===0) return 1;
  // let str=num.toString()
  // console.log(str.length);
  // // 내 답에서 음수가 있을경우는 1자리를 빼줘야하거나 아래 답을 사용
  return Math.floor(Math.log10(Math.abs(num)))+1
}

digitCount(-233);

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

mostDigits([10,1,4,31321,3,3021])

기수정렬

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])