[BOJ/백준] 정렬_ 25305번_ 퀵정렬(Quick Sort)

1. 문제 번호 25305

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

•   퀵 정렬(Quick Sort) : 대규모 데이터의 경우 적절하며 분할정복법을 사용하여 피벗인덱스를 활용

 

 

 

문제를 먼저 정확히 파악

 

•  

 

 

 

나의 문제풀이 방식 및 순서

 

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

 

 

 

---

3. 소스 인증

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int [] numAry = new int[N];
        
        for(int i = 0; i < N; i++){
            numAry[i] = Integer.parseInt(st2.nextToken());
        }

        quickSort(numAry, 0, N -1 );
        
        System.out.println(numAry[N - (k)]);

        
    }
    public static void quickSort(int [] numAry, int start, int end){
        if(start >= end){
            return;
        }
        
        int key = numAry[start];
        int i = start + 1;
        int j = end;

        /*
        ex) 40, 60, 20, 30, 50
        첫 번째 ipvot은 40, i = 1, j = 3

        i = 1 j = 4 일때 if(i < j)로 swap => 40 30 20 60 50
        i = 3 j = 2 일때 swap(num, start, j) => 20 30 40 60 50 

        i = 3 j = 2 일때 아래 실행
        quickSort(numAry, start, j-1);
        quickSort(numAry, j+1, end);

        quickSort(numAry, start, j-1); 
            => start = 0, j = 1 로 실행된다.
            => int i = start +1 이기 때문에 i = 1, j = 1 
            => while(i <= end && key >= numAry[i]){}  는 종료됌
            => while(j > start && key <= numAry[j]){} 는 종료됌

            => quickSort(numAry, 0, -1);
            => quickSort(numAry, 1, 1);
            
        quickSort(numAry, 3, 4);
            => 
        */
        
        while(i <= j){
            while(i <= end && key >= numAry[i]){
                i++;
            }
            while(j > start && key <= numAry[j]){
                j--;
            }

            if(i < j){ 
                swap(numAry, i, j);
            }
        }
        swap(numAry, start, j);
        
        quickSort(numAry, start, j-1);
        quickSort(numAry, j+1, end);
    }
    
    public static void swap(int [] numAry, int a, int b){
        int temp = numAry[a];
        numAry[a] = numAry[b];
        numAry[b] = temp;
    }
}

 

예시 - > 40 60 20 30 50

1. 40 60 20 30 50 (피벗인덱스 start로 설정)
2. 40 30 20 60 50 ( i = 1 (=index) value = 60, j = 4 (=index) value = 50 ) 
3. 역전 발생!!!  ( i = 3 (=index) value = 60, j = 2 (=index) value = 20 )
4. 20 30 40 60 50 
5. quickSort(numAry, 0, j-1 ) , quickSort(numAry, j + 1 , end )

 

 

 

- 실패 소스코드 -

 

 

 

 

 

 

 

---

4.추가 개념

 

1. 알고리즘 개요:

•  퀵 정렬은 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 정렬 알고리즘입니다.
•  배열을 피벗(pivot) 기준으로 두 부분으로 나누고, 각 부분을 재귀적으로 정렬합니다.

2. 작동 방식:

• 피벗 선택: 배열에서 임의의 요소를 피벗으로 선택합니다.
• 분할: 피벗을 기준으로 작은 값과 큰 값으로 배열을 분할합니다.
• 재귀 호출: 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 적용합니다.

3. 시간 복잡도:

• 평균: O(n log n)
• 최악: O(n^2) (피벗 선택이 매번 최악일 경우)
• 평균은 2^10000 은 상수 10000과 같기 때문에 매우 빠름.
• 최악은 선택,버블,삽입과 동일하다.(난 이번 문제를 pivotIndex를 랜덤하게 뽑았다.)

4. 공간 복잡도:

• O(log n) (재귀 호출의 스택 공간)

5. 특징:

• 평균적으로 빠른 정렬 알고리즘.
• 제자리 정렬(In-place Sort)로 추가적인 메모리 사용이 적음.
• 불안정 정렬(Unstable Sort).

 

---

 

 

1. 빅 오 표기법 개요:

• 데이터 원소 N개에 대한 알고리즘 단계 수 
  • O(1), O(2), O(3), O(4) 는 모두 데이터 원소가 증가하더라도 1,2,3,4 단계로 고정된 알고리즘 유형
• 데이터가 늘어날 때 단계 수가 어떻게 증가하는가?
  • O(N)은 데이터 원소가 증가할 때 단계 수가 비례(N개) 로 증가하는 알고리즘 유형
• 최악의 시나리오

 

2. 로그 log :

• 2를 몇 번 곱해야 N이 나올까? = log₂N
  
  • 2를 3번 곱하면 8이 나온다. log₂8 = 3
• 1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log₂N

 

3. O(logN) == O(log₂N)

• 데이터가 두 배로 증가할 때마다 한 단계씩 증가하는 알고리즘
• 데이터 원소 N개가 있을때 알고리즘에서는 log₂단계가 걸린다.
  • 8개의 원소가 있을때 log₂8 는 3번의 단계를 거쳐야 한다. 

출처 : welloff_jj님의 hyeojung.log블로그

 

 

 

---

5. 참조 블로그

---

 

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

 

---

 

 

 

https://youtu.be/O-O-90zX-U4?si=xzvKx12A-w_10F8u

 

https://velog.io/@on-n-on-turtle/%EB%88%84%EA%B5%AC%EB%82%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4%ED%91%9C%EA%B8%B0%EB%B2%95