알고리즘) 퀵소트 시간복잡도

 

이진검색 귀납법으로 증명[  ]

 

partion코드부분[  ]

 

 

---

 

 

 

 

[오름차순 (Ascending)]

"내 왼쪽 구역에는 피벗보다 작은( < ) 놈들을 모을 거야!"

if (arr[k] < pivot) { // 피벗보다 작으면!
    j++;
    swap(arr, j, k);  // 왼쪽 구역(j)으로 보내라
}

• 결과: [작은 놈들] [피벗] [큰 놈들]  작은 게 앞이니까 오름차순

[내림차순 (Descending)]

"내 왼쪽 구역에는 피벗보다 큰( > ) 놈들을 모을 거야!"

if (arr[k] > pivot) { // 피벗보다 크면! (부등호 변경)
    j++;
    swap(arr, j, k);  // 왼쪽 구역(j)으로 보내라
}

• 결과: [큰 놈들] [피벗] [작은 놈들]  큰 게 앞이니까 내림차순

---

2. 왜 부등호 하나로 해결되나요?

첫 번째 코드에서 j의 역할을 다시 떠올려보세요.
j는 **"내가 인정한 놈들만 들어올 수 있는 땅의 경계선"**입니다.

• 오름차순일 때는 "나보다 작은 놈"만 입국 허가를 내준 것이고,
• 내림차순일 때는 "나보다 큰 놈"만 입국 허가를 내준 것입니다.

 

 

 

 

분할 정복법 (Divide and Conquer)

• 어원: 나폴레옹의 전략에서 유래. 5만 명의 연합군을 한꺼번에 상대하기 어려우니, 2만 5천 명씩 둘로 나누어(Divide) 각각 격파(Conquer)했다는 원리.
• 3단계 구조:
  1. 분할(Divide): 문제를 더 작은 사례로 나눔.
  2. 정복(Conquer): 작은 문제를 해결 (보통 재귀 호출).
  3. 통합(Combine): 작은 문제의 답을 모아 원래 문제의 답을 구함.
• 특징: 본질적으로 재귀(Recursion) 구조를 가짐.

 

 

 

 

 

 

 

 

 

 

 

sort를 담당하는 전체적인 큰 틀(재귀 함수 부분)은 어떤 파티션(Partition) 방식을 쓰든 거의 똑같

 

void quickSort(int[] S, int low, int high) {
    if (low < high) {
        // [1] 어떤 파티션 방법을 쓰든, 결국 기준점(pivotPoint)의 위치를 반환함
        int pivotPoint = partition(S, low, high); 

        // [2] 기준점을 제외하고 왼쪽 정렬 (동일)
        quickSort(S, low, pivotPoint - 1); 

        // [3] 기준점을 제외하고 오른쪽 정렬 (동일)
        quickSort(S, pivotPoint + 1, high);
    }
}

 

 

 

 

1

int partition(int[] S, int low, int high) {
    int pivot = S[low]; // 제일 왼쪽을 피벗으로 설정
    int j = low;        // j는 피벗보다 작은 값들의 "경계선"

    // i가 low+1부터 high까지 쭉 전진
    for (int i = low + 1; i <= high; i++) {
        if (S[i] < pivot) { // 피벗보다 작은 놈을 발견하면!
            j++;            // 경계선을 한 칸 넓히고
            swap(S, i, j);  // 그 자리에 작은 값을 갖다 놓음
        }
    }
    
    // 마지막으로 피벗을 경계선 위치(j)와 바꿈
    int pivotPoint = j;
    swap(S, low, pivotPoint);
    
    return pivotPoint;
}

 

 

 

int partition(int[] S, int low, int high) {
    int pivot = S[low];
    int i = low;
    int j = high + 1; // 끝에서 하나 더 간 위치

    do {
        // i는 피벗보다 큰 걸 찾을 때까지 오른쪽으로!
        do { i++; } while (i <= high && S[i] < pivot);
        
        // j는 피벗보다 작은 걸 찾을 때까지 왼쪽으로!
        do { j--; } while (S[j] > pivot);
        
        // 아직 둘이 안 만났으면, 큰 놈과 작은 놈을 서로 맞교환!
        if (i < j) {
            swap(S, i, j);
        }
    } while (i < j); // 둘이 만날 때까지 반복

    // 마지막으로 피벗을 중간 지점(j)과 바꿈
    int pivotPoint = j;
    swap(S, low, pivotPoint);
    
    return pivotPoint;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

high > low

원소가 최소 2개 이상일 때만 정렬을 수행하겠다

 

 

 

int pivotpoint = j;
exch(a, low, pivotpoint);

 

 

루프가 끝났을 때 피벗은 아직 맨 앞(low)에 혼자 있기 때문입니다

 

 

 

*피벗은 한 판(한 번의 partition 함수 호출)이 끝날 때까지 절대 바뀌지 않는 '절대 기준'