Quick sort

2025. 5. 7. 10:53·📚 STUDY/📈 알고리즘

Divide-and-conquer를 기반으로 하는 정렬 알고리즘으로, 방식은 아래와 같다.

1. Pivot 선택 : 배열에서 하나의 원소를 pivot으로 선택한다. 

2. 분할 : pivot을 기준으로 pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 배열한다.

3. 재귀 호출 : 왼/오른쪽 부분 배열에 quick sort를 재귀적으로 수행한다.

 

💡 이상적인 경우

pivot이 항상 배열을 거의 절반으로 나누는 경우, T(n) = 2T(n/2)+O(n) 재귀식을 따른다.

마스터 정리를 이용하면, T(n)=O(nlogn)이 된다.

 

💡 최악의 경우

pivot이 항상 가장 작거나 or 큰 원소를 선택하는 경우이다.

(= 배열이 거의 정렬되어 있거나 역순일 때 잘못된 pivot을 선택한다는 말)

이때, partition은 배열을 거의 한 쪽으로만 나누어, 분할 결과 크기가 (n-1)인 부분과 0인 두 부분 배열로 나뉘게 된다.

이런 상황이 반복되면, 정렬해야 할 배열의 크기가 한 번에 1씩 줄어들게 된다.

따라서, T(n) = T(n-1)+O(n)이다.

* T(n-1) : 크기가 (n-1)인 부분 배열에 대해 다시 quick sort를 수행하는 시간

* O(n) : 현재 단계에서 pivot을 기준으로 분할하는데 드는 시간

 

T(n) = T(n-1)+cn

        = (T(n-2)+c(n-1)) + cn 

        = ((T(n-3)+c(n-2))+c(n-1)) + cn 

        = ...

        = T(1) + c(2+3+4+...+(n-1)+n)

T(1)은 상수시간 O(1)이라고 가정할 수 있어 무시하면, T(n) = c(2+3+...+n) = (n-1)(n-2)/2

즉, T(n) = O(n²)

 

✅ 제일 중요한 건, pivot을 선택하고 left, right를 판단하는 과정은 ⭐pivot의 위치를 찾는 것이라는 것.

 

 

(정렬하기 전, pivot을 기준으로 left, right를 나누고 언제 바꿀지 판단할 때 L > R로 두거나 L >= R로 두거나에 따라 방법이 있더라고요..)

(처음 들어봤는데 일단 정리를 해보겠습니다)

 

💡 Quick sort의 파티션 방식은 2가지가 있다.

1. Hoare Partition Scheme (호어 분할 방식)

✔ 조건 : left < right 일 때 계속 진행

✔ 교차 조건 : left >= right 이면 종료

- pivot 기준으로 좌/우에서 이동하며 엇갈리는 값을 교환

- pivot이 항상 중간으로 오진 않음

- 효율적이고, 평균적으로 교환 횟수가 적음.

while True:
    while arr[left] < pivot:
        left += 1
    while arr[right] > pivot:
        right -= 1
    if left >= right:
        return right
    swap(arr[left], arr[right])
    left += 1
    right -= 1

 

 

2. Lomuto Partition Scheme (로무토 분할 방식)

✔ 조건 : 보통 left <= right 형태

✔ 교차 조건 : left > right 이면 종료

- pivot은 보통 마지막 우너소

- pivot보다 작은 값들을 왼쪽으로 몰아넣고, 마지막에 pivot을 적절 위치로 옮김

- 단순하지만, 교환 횟수가 많아질 수 있음.

pivot = arr[high]
i = low - 1
for j in range(low, high):
    if arr[j] <= pivot:
        i += 1
        swap(arr[i], arr[j])
swap(arr[i+1], arr[high])
return i + 1
저작자표시 (새창열림)

'📚 STUDY > 📈 알고리즘' 카테고리의 다른 글

BFS (너비 우선 탐색)  (0) 2025.05.07
DFS (깊이 우선 탐색)  (0) 2025.05.07
Merge sort  (0) 2025.05.07
Divide-and-Conquer Algorithm  (0) 2025.04.15
Algorithm & Time Complexity  (0) 2025.04.15
'📚 STUDY/📈 알고리즘' 카테고리의 다른 글
  • BFS (너비 우선 탐색)
  • DFS (깊이 우선 탐색)
  • Merge sort
  • Divide-and-Conquer Algorithm
엄지잉
엄지잉
공부하는거 올림
  • 엄지잉
    엄지잉의 이것저것
    엄지잉
  • 전체
    오늘
    어제
    • 분류 전체보기 (94)
      • 🏫 학교 (2)
        • 👩‍🏫 교직 (1)
        • 🏢 USG (1)
      • 🌱 탐구 (17)
        • 📷 SLAM (7)
        • 💡 연구 (8)
        • 🌐 BOJ (2)
      • 📚 STUDY (47)
        • 🔥 C (32)
        • 📈 알고리즘 (9)
        • 👀 컴퓨터비전 (5)
        • 🔆 UNITY (1)
      • 🏆 자격증 (23)
        • ⚡ 정처기 (17)
        • 🔠 TOEIC (6)
      • 🎈 활동 (4)
        • 🎁 CJ 리모트 인턴십 (2)
        • 😶 기타 (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    Slam
    프언 활용
    C
    azurekinect
    SW 설계
    c기초
    모션캡처
    Unity
    2022년
    mocopi
    식별자
    Azure Kinect
    2021년
    Body Tracking
    토익
    DB 구축
    SW 개발
    실기
    컴퓨터비전
    RC
    정처기
    정보처리기사
    BOJ
    opencv
    필기
    C++
    알고리즘
    정보시스템 구축관리
    C언어
    Remote Internship
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
엄지잉
Quick sort
상단으로

티스토리툴바