정렬 알고리즘 (Sorting Algorithm) / 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 기수 정렬

 

[정렬 알고리즘]

 

---

 

<STUDY>

 

 

정렬 알고리즘 (Sorting Algorithm)

항목을 재배열 하는 과정

• 일반적으로 배열을 사용
• 트리 등의 데이터 구조의 정렬

 

# 기본적인 정렬 알고리즘

1. 버블 정렬 (Bubble Sort)
2. 선택 정렬 (Selection Sort)
3. 삽입 정렬 (Insertion Sort)

 

# JS 내장 정렬 메소드

console.log([23, 45, 6, 12, 13].sort())

// 예상 : [6, 12, 13, 23, 45]
// 결과 : [12, 13, 23, 45, 6]

 

 

❓예상 출력값과 결과값이 다른 이유

• 자바스크립트에 내장된 정렬 메소드(sort)의 기본 정렬 순서는 문자열 유니코드의 코드 포인트에 따르기 때문
• 속성, 비교 대상을 실제로 지정하여 원하는 방식으로 정렬 가능

 

 

예시1 - 숫자

function numberCompare(num1,num2) {
	return num1 - num2;
}
console.log([23, 45, 6, 12, 13].sort(numberCompare));
// 결과: [6, 12, 13, 23, 45]

 

예시2 - 문자 길이

function compareByLen(str1, str2) {
	return str1.length - str2.length;
}
console.log(["Steele", "Colt", "Data Stuructures", "Algorithms"].sort(compareByLen));
// 결과 : ["Colt", "Steele", "Algorithms", "Data Stuructures"]

 

---

버블 정렬 (Bubble Sort)

배열을 오름차순으로 정렬하는 경우 더 큰 숫자가 한 번에 하나씩 뒤로 이동하는 정렬 방법

• 효율적인 알고리즘은 아님 (빈번하게 사용되지 않음)

 

교환 방법

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

// ES2015
function swap2(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++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}

 

# 최적화 (정렬이 거의 되어 있는 배열인 경우)

function bubbleSortOpt(arr) {
  let noSwaps;

  for (let i = arr.length; i > 0; i--) {
    noSwaps = true;

    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        noSwaps = false;
      }
    }

    if (noSwaps) break;
  }

  return arr;
}

 

Big O

• 일반적인 경우 : O(n^2)
• 데이터가 거의 정렬된 경우 (Best) : O(n)

 

---

 

선택 정렬 (Selection Sort)

최솟값을 찾아 정해진 위치의 값과 교환하는 정렬 방법

• 매우 효율적인 방법은 아님

 

순서

• 정렬의 첫 번째 값을 선택하고 다음 항목과 비교하여 더 작은 값을 최솟값으로 저장
• 마지막까지 비교 후 최솟값의 위치와 첫 번째 위치를 바꿈
• 두 번째 값도 같은 방법으로 교환
• 위 과정을 반복하여 정렬

 

예시

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) min = j;
    }

    if (min !== i) {
      const temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }

  return arr;
}

 

Big O

• O(n^2)

 

💡 스왑 수를 최소화하는 경우 버블 정렬보다 효율적임

 

 

---

 

삽입 정렬 (Insertion Sort)

배열의 과반을 점차적으로 만들어 정렬을 구축하는 정렬 방법

• 버블 정렬, 선택 정렬과 비슷함
• 각 요소를 취하여 정렬되어 있는 절반 속 해당되는 위치에 배치

 

예시

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

 

Big O

• Worst : O(n^2)
• 데이터가 거의 정렬된 경우 (Best) : O(n)

 

💡 들어온 데이터를 즉시 입력해야 하는 상황에 편리함

 

---

 

버블 정렬 vs 선택 정렬 vs 삽입 정렬

• 2차 정렬 알고리즘 (시간 복잡도 Big O = O(n^2))

 

💡한계점

작은 규모의 배열에서 효율적 (규모가 커지면 시간이 오래걸린다!!)

 

 

---

 

합병 정렬 (Merge Sort)

배열을 더 작은 배열로 나누는 정렬 방법

• 분할 정복 알고리즘
• 배열을 계속 분할한 다음 병합시킴
• 배열 길이가 0 / 1이 될 때까지 분할
• 만들 수 있는 가장 작은 배열로 분할 된 경우 병합

 

정렬되어 있는 두 배열 합치기

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

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

  if (i > 0 || j > 0) {
    result = result.concat(arr1.slice(i)).concat(arr2.slice(j));
  }

  return result;
}

console.log(merge([1, 2, 5], [3, 4, 5, 7])); // [ 1, 2, 3, 4, 5, 5, 7 ]

 

예시

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

console.log(mergeSort([33, 1, 8, 83])); // [ 1, 8, 33, 83 ]

 

# 호출 스택

1. mergeSort([33, 1, 8, 83])
2. left = mergeSort([33, 1])
3. left = mergeSort([33]), right = mergeSort([1])
4. left = merge([33], [1]) = [1, 33]
5. right = mergeSort([8, 83])
6. left = mergeSort([8]), right = mergeSort([83])
7. right = merge([8], [83]) = [8, 83]
8. mergeSort([33, 1, 8, 83]) = merge([1, 33], [8, 83]) = [1, 8, 33, 83]

 

Big O

• O(n log n)
• 공간 복잡도 : O(n)

 

💡 특징

⇒ 예외 케이스가 없음! → 데이터의 정렬 여부가 영향을 끼치지 않음
⇒ 효율적인 시간 복잡도 (O(n log n))
⇒ 배열이 클수록 메모리에 더 많은 배열을 저장해야함

 

---

 

퀵 정렬 (Quick Sort)

데이터를 분할하여 개별적으로 정렬하는 방법

• 배열 길이가 0 / 1이 될 때까지 분할
• 피벗 포인트(단일 요소) 선택하여 수행
• 모두 정렬하는 것이 아니라 숫자를 한쪽으로 옮기는 것이 포인트!

 

pivot 함수

function pivot(arr, sp = 0, ep = arr.length + 1) {
  let p = arr[sp];
  let index = sp;

  for (let i = sp + 1; i < arr.length; i++) {
    if (arr[i] < p) {
      index++;
      [arr[i], arr[index]] = [arr[index], arr[i]];
    }
  }

  [arr[sp], arr[index]] = [arr[index], arr[sp]];

  return index;
}

console.log(pivot([4, 8, 2, 1, 5, 7, 6, 3])); // [3, 2, 1, 4, 5, 7, 6, 8]

 

예시

function quickSort(arr, sp = 0, ep = arr.length - 1) {
  if (sp < ep) {
    let pivotIndex = pivot(arr, sp, ep);
    quickSort(arr, sp, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, ep);
  }

  return arr;
}

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

 

# 호출 스택

 

* arr = [4, 8, 2, 1, 5, 7, 6, 3]

1. quickSort(arr, sp = 0, ep = arr.length - 1) → pivotIndex = 3, arr = [3, 2, 1, 4, 5, 7, 6, 8]
2. quickSort([3, 2, 1, 4, 5, 7, 6, 8], 0, 3 - 1) → 1번 sp pivotIndex = 2, arr = [1, 2, 3, 4, 5, 7, 6, 8]
3. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 0, 2 - 1) → 2번 sp pivotIndex = 0, arr = [1, 2, 3, 4, 5, 7, 6, 8]
4. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 0, 0 - 1) → 3번 sp (sp ≥ ep 이므로 배열 반환
5. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 0 + 1, 1) → 3번 ep (sp ≥ ep 이므로 배열 반환)
6. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 2 + 1, 1) → 2번 ep
7. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 3 + 1, 7) → 1번 ep pivotIndex = 4, arr = [1, 2, 3, 4, 5, 7, 6, 8]
8. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 4, 4 - 1) → 7번 sp (sp ≥ ep 이므로 배열 반환)
9. quickSort([1, 2, 3, 4, 5, 7, 6, 8], 4 + 1, 7) → 7번 ep pivotIndex = 6, arr = [1, 2, 3, 4, 5, 6, 7, 8]
10. quickSort([1, 2, 3, 4, 5, 6, 7, 8], 5, 6 - 1) → 9번 sp (sp ≥ ep 이므로 배열 반환)
11. quickSort([1, 2, 3, 4, 5, 6, 7, 8], 6 + 1, 7) → 9번 ep (sp ≥ ep 이므로 배열 반환)
12. 맨 처음 quickSort(arr, sp = 0, ep = arr.length - 1) 배열 반환 // [ 1, 2, 3, 4, 5, 6, 7, 8 ]

 

Big O

• Best, Average : O(n log n)
• Worst : O(n^2)
• 공간 복잡도 : O(log n)

 

💡 특징

이미 정렬되어 있는 경우 최대 O(n^2)의 시간 복잡도가 나타남

⇒ pivot을 고를 때 가장 작은 요소나 가장 큰 요소만 항상 선택하는 경우 발생
⇒ 무작위로 pivot을 고르거나 중간 값을 선택

 

---

 

기수 정렬 (Radix Sort)

이진수를 이용한 정렬 방법

• 정렬할 숫자끼리 비교를 수행하지 않음
• 최대 자릿수만큼 반복
• 반복할 때마다 10개(0 ~ 9 까지의 숫자)의 빈 배열 버킷을 생성하여 분류

 

원하는 자리의 숫자 찾기

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

console.log(getDigit(12345, 4)); // 1

 

자릿수 반환하기

function digitCount(num) {
  if (isNaN(num)) return "Not A Number";
  if (num === 0) return 1;

  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

console.log(digitCount(520)); // 3

 

최대 자릿수 찾기

function mostDigits(arr) {
  return arr.reduce((max, num) => Math.max(max, digitCount(num)), 0);
}

console.log(mostDigits([1234, 56, 7])); // 4

 

예시

function radixSort(arr) {
  const maxDigit = mostDigits(arr);

  for (let i = 0; i < maxDigit; i++) {
    let buckets = Array.from({ length: 10 }, () => []);

    arr.forEach((num) => {
      const digit = getDigit(num, i);
      buckets[digit].push(num);
    });

    arr = buckets.flat();
  }

  return arr;
}

console.log(radixSort([23, 345, 5467, 12, 2345, 9852])); //[ 12, 23, 345, 2345, 5467, 9852 ]

 

Big O

• O(n * k)
• 공간 복잡도 : O(n + k)
• n : 정렬할 항목 수 or 정수의 갯수, k : 수의 최대 길이 (최대 자릿수)

 

💡 이론적으로 모든 비교 정렬보다 빠를 수 있다.

⇒ 메모리 저장 방식의 제한으로 그렇지 않을 수 있음..!

 

---

 

 

보통 정렬을 사용할 때 자바스크립트의 sort() 메소드를 자주 사용했다.

 

버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 지수 정렬 같은 여러 정렬 알고리즘이 있는 것은 알고 있었지만

정확히 어디에 어떤 식으로 사용하는지 잘 알지 못했고 그래서 제대로 사용하지 못했던 것 같다.

 

정렬 알고리즘에 대해 공부하면서 시간 복잡도가 어떻게 다르고 어떤 경우에 사용하면 더 효율적으로 사용할 수 있는지에 대해 알게되었다.

앞으로는 정렬 알고리즘을 사용할 때 더 효율적인 방법을 선택하여 구현하는 연습을 해봐야 겠다👻👻

 

 

 

👉노트 보러가기👈

 

GitHub - ez1n/coding-test: 코딩 테스트가 장애물이 될 순 없다.