정렬 알고리즘

📍정렬

💡정렬(Sorting)이란?
     주어진 데이터를 일정한 기준에 따라 순서대로 나열하는 알고리즘

📍선택 정렬

• 배열에서 아직 정렬하지 않은 부분 중 가장 작은 값을 찾아서, 그 값을 현재 탐색 위치로 옮기는 것을 반복하는 정렬 방식
  → 매번 남은 배열 중 최소값을 찾아 앞으로 보냄

JS 코드

function selectionSort(arr) {
  const n = arr.length;            

  for (let i = 0; i < n - 1; i++) {   
    let minIndex = i;               // 현재 위치를 최소값 위치로 초기화

    // i 이후 구간에서 최소값 위치 찾기
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {  // 현재 저장된 최소값보다 더 작은 값이 있으면
        minIndex = j;               // 최소값 위치 갱신
      }
    }

    // i 위치의 값과 찾은 최소값 위치의 값 교환 (같으면 교환하지 않음)
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;  
}

 

시간복잡도)

• 외부 반복문: n-1
• 내부 반복문: n - i번
• 👉 1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n²)

📍버블 정렬

• 인접한 두 요소를 비교해 순서가 잘못되었으면 서로 교환하는 정렬 방식

JS 코드

function bubbleSort(arr) {
  const n = arr.length;              

  for (let i = 0; i < n - 1; i++) { 
      // 이미 정렬된 뒤쪽 i개 제외함
    for (let j = 0; j < n - 1 - i; j++) { 
        // 현재 요소가 다음 요소보다 크면 두 요소 위치 교환
      if (arr[j] > arr[j + 1]) {    
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;  
}

 

시간복잡도)

• 외부 반복문: n-1
• 내부 반복문: n - i번
• 👉 1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n²)

📍삽입 정렬

• 배열을 앞에서부터 차례대로 보면서 현재 원소를 이미 정렬된 앞부분 배열에 알맞은 위치에 삽입하는 방식
  → like 카드 정렬할 때 새 카드를 이미 정렬된 카드 더미에 끼워 넣는 것

JS 코드

function insertionSort(arr) {
    // 두번째 원소부터 시작함 (첫 번째 원소는 이미 정렬된 상태로 가정됨)
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];       // 현재 삽입할 값
    let j = i - 1;          // key 바로 앞 인덱스부터 비교 시작

    // arr[j]가 key보다 크면 한 칸씩 뒤로 이동
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

        // 빈 자리 만든 뒤 key를 그곳에 삽입
    arr[j + 1] = key;       
  }
  return arr;
}

• key는 배열 내에서 복사해 둔 값이라서 배열에서 원래 arr[i] 위치에 있던 값이 잠시 사라진 상태라고 생각하자.
• 그래서 그 자리부터 왼쪽으로 가면서 큰 값들을 오른쪽으로 밀어내고, 마지막에 비어 있는 자리(j+1)에 key를 넣는 것임!!

시간복잡도)

• 외부 반복문: n-1
• 내부 반복문: n - i번
• 👉 1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n²)

📍퀵 정렬

• 분할 정복(Divide and Conquer) 방식의 정렬
• 피벗(pivot)을 정해
  • 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
  • 왼쪽과 오른쪽 부분 배열에 대해 다시 퀵 정렬 재귀 호출

JS 코드

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 재귀 호출이 끝나는 종료 조건

  const pivot = arr[0];            // 기준점 (첫 번째 값)
  const left = arr.slice(1).filter((x) => x < pivot);
  const right = arr.slice(1).filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

 

 

if) 첫 번째 원소를 피벗으로 고정했을 때, 만약 배열이 이미 거의 정렬된 상태(오름차순이나 내림차순)라면 피벗보다 작은 원소가 거의 없거나 거의 전부가 한쪽에 몰리게 된다.

• [1, 2, 3, 4, 5] 같은 오름차순 배열에 첫 원소 1을 피벗으로 잡으면
• 왼쪽 배열: [] (없음)
• 오른쪽 배열: [2, 3, 4, 5] (대부분)
  → 재귀 깊이가 n 단계까지 깊어짐
  → 이 경우는 시간복잡도가 최악이 됨!!!!!! O(n²)

그럼 랜덤하게 선택하거나 배열의 첫, 중간, 마지막 요소중에서 가운데 값을 뽑아 피벗을 잡자!! 

대체로 균등하게 분할되니까 시간복잡도는
👉 O(n log n)

 

refactor/ 랜덤 피벗 선택하기

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  // 랜덤 인덱스 선택
  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];

  // 피벗 제외한 배열
  const rest = arr.slice(0, pivotIndex).concat(arr.slice(pivotIndex + 1));

  const left = rest.filter(x => x < pivot);
  const right = rest.filter(x => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

 

refactor/median-of-three (3개 중간값) 피벗 선택

function medianOfThree(arr, a, b, c) {
  const vals = [arr[a], arr[b], arr[c]];
  vals.sort((x, y) => x - y);
  return vals[1]; // 중간값 리턴
}

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const first = 0;
  const mid = Math.floor(arr.length / 2);
  const last = arr.length - 1;

  const pivot = medianOfThree(arr, first, mid, last);

  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  const pivots = arr.filter(x => x === pivot); // 같은 값 여러 개일 때 대비

  return [...quickSort(left), ...pivots, ...quickSort(right)];
}

 

📍병합 정렬

• 분할 정복(Divide and Conquer) 방식의 정렬
• 배열을 계속 반으로 나눈 뒤, 정렬하면서 병합하는 방식

JS 코드

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;  // 왼쪽, 오른쪽 배열에서 비교할 현재 인덱스

    // 양쪽 배열의 요소를 끝까지 비교하면서 더 작은 값을 결과에 추가
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      result.push(left[l++]);
    } else {
      result.push(right[r++]);
    }
  }

  return [...result, ...left.slice(l), ...right.slice(r)];
}

 

병합순서

1단계 - mergeSort가 배열을 계속 쪼개기

단계	배열	설명
1	[10, 12, 7, 3, 15, 2, 5]	처음 호출
2	[10, 12, 7] , [3, 15, 2, 5]	중간 기준으로 쪼갬
3	[10] , [12, 7]	[10,12,7] 부분 재귀 쪼갬
4	[12] , [7]	[12,7] 부분 재귀 쪼갬
5	[3, 15] , [2, 5]	[3,15,2,5] 부분 재귀 쪼갬
6	[3], [15]	[3,15] 부분 재귀 쪼갬
7	[2], [5]	[2,5] 부분 재귀 쪼갬

 

2단계 - 쪼갠 배열들이 길이 1 이하가 되어 재귀가 멈춘다.

 

3단계 - merge 함수로 두 배열을 병합하며 정렬한다.

• 병합 1: [12] 와 [7]
  비교: 12 vs 7 → 7이 작으니 결과 [7], 다음으로 12 → 결과 [7, 12]
• 병합 2: [10] 와 [7, 12]
  비교: 10 vs 7 → 7 < 10 → 결과 [7]
  비교: 10 vs 12 → 10 < 12 → 결과 [7, 10]
  오른쪽 배열 12 남음 → 결과 [7, 10, 12]
• 병합 3: [3] 와 [15]
  비교: 3 vs 15 → 3 < 15 → 결과 [3]
  오른쪽 배열 15 남음 → 결과 [3, 15]
• 병합 4: [2] 와 [5]
  비교: 2 vs 5 → 2 < 5 → 결과 [2]
  오른쪽 배열 5 남음 → 결과 [2, 5]
• 병합 5: [3, 15] 와 [2, 5]
  비교: 3 vs 2 → 2 < 3 → 결과 [2]
  비교: 3 vs 5 → 3 < 5 → 결과 [2, 3]
  비교: 15 vs 5 → 5 < 15 → 결과 [2, 3, 5]
  오른쪽 배열 끝, 왼쪽 15 남음 → 결과 [2, 3, 5, 15]
• 병합 6: [7, 10, 12] 와 [2, 3, 5, 15]
  비교: 7 vs 2 → 2 < 7 → 결과 [2]
  비교: 7 vs 3 → 3 < 7 → 결과 [2, 3]
  비교: 7 vs 5 → 5 < 7 → 결과 [2, 3, 5]
  비교: 7 vs 15 → 7 < 15 → 결과 [2, 3, 5, 7]
  비교: 10 vs 15 → 10 < 15 → 결과 [2, 3, 5, 7, 10]
  비교: 12 vs 15 → 12 < 15 → 결과 [2, 3, 5, 7, 10, 12]
  오른쪽 배열 15 남음 → 결과 [2, 3, 5, 7, 10, 12, 15]

시간복잡도)

• 배열 반 나누기 → O(log n)
• 다시 병합 → O(n)
• 👉 O(n) × O(log n) = O(n log n)

📍JavaScript 내장 정렬 (sort)

Array.prototype.sort() - JavaScript | MDN

Array.prototype.sort() - JavaScript | MDN

 

const arr = [10, 2, 5, 1, 9];
arr.sort();
console.log(arr); // ["1", "10", "2", "5", "9"]  <-- 문자열 기준 정렬됨

• 기본 sort()는 문자열 유니코드 순서로 정렬
• 숫자를 제대로 정렬하려면 비교 함수를 넣어야 한다.

arr.sort((a, b) => a - b); // 오름차순 정렬
arr.sort((a, b) => b - a); // 내림차순 정렬

 

---

종류	시간 복잡도 (최선/평균/최악)	안정성	특징
선택 정렬 (Selection Sort)	O(n²) / O(n²) / O(n²)	불안정	항상 O(N2)의 성능을 보이며, 제자리 정렬(in-place sort)이고 데이터 이동 횟수가 적음. 매우 비효율적.
버블 정렬 (Bubble Sort)	O(n) / O(n²) / O(n²)	안정적	구현이 매우 간단하지만 비효율적. 데이터가 거의 정렬되어 있으면 빠를 수 있음.
삽입 정렬 (Insertion Sort)	O(n) / O(n²) / O(n²)	안정적	데이터가 거의 정렬되어 있을 때 효율적이며, 작은 규모의 데이터에 적합.
퀵 정렬 (Quick Sort)	O(n log n) / O(n log n) / O(n²)	불안정	일반적으로 가장 빠른 정렬 알고리즘 중 하나. 평균적으로 우수하지만, 최악의 경우 O(N2)가 될 수 있음.
합병 정렬 (Merge Sort)	O(n log n) / O(n log n) / O(n log n)	안정적	항상 O(NlogN)의 성능을 보장하며 안정적. 추가 공간이 필요하다는 단점이 있음.
JavaScript sort()	브라우저/엔진 구현에 따라 다름 (대부분 O(NlogN))	구현에 따라 다름 (불안정할 수 있음)	ECMAScript 표준에 의해 특정 알고리즘이 강제되지 않으므로, 브라우저 엔진마다 구현이 다름. (Timsort, Quicksort 변형 등). 숫자 정렬 시 비교 함수 필수.

---

프로그래머스 고득점 Kit에 있는 정렬 문제도 3개 풀어봤는데, 생각보다 넘 어려움.. 🥲

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스