2024 동계 모각코 6회

2025/02/10

6회차 목표

1) Udemy 강의:
- 섹션 15: 퀵 정렬

2) 실습:
- 강의의 문제 구현
- 프로그래머스 문제

---

TIL

1️⃣ 퀵 정렬 (Quick Sort)

 

 

📌 작동 원리

1.  분할 정복(Divide and Conquer) 방식을 사용하여 배열을 정렬
2.  기준이 되는 피벗(pivot)을 선택하고, 이를 기준으로 작은 값과 큰 값으로 분할하여 정렬을 수행

 

📌 알고리즘 동작 과정

1. 배열에서 하나의 요소를 피벗으로 선택한다.
2. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다.
3. 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다.
4. 모든 부분 배열이 정렬되면 최종적으로 정렬된 배열이 완성된다.

 

📌 구현 코드

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter((num) => num < pivot);
    const middle = arr.filter((num) => num === pivot);
    const right = arr.filter((num) => num > pivot);
    
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

// 실행 예제
let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(quickSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

 

📌 시간 복잡도

최악의 경우 (역순 정렬)	O(n^2)
평균적인 경우	O(nlogn)
최선의 경우 (이미 정렬된 상태)	O(nlogn)

 

 

📌 공간 복잡도 O(n)

O(n) (재귀 호출에 따른 추가적인 메모리 사용)

 

📌 특징

- 일반적으로 정렬 속도가 빠르고 효율적인 정렬 알고리즘 중 하나이다.
- 불균형한 피벗 선택 시 성능이 저하될 수 있으므로 랜덤 피벗을 선택하는 방식도 존재한다.

---

느낀 점

파이팅