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

1. 문제 번호 2751

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

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

 

 

 

문제를 먼저 정확히 파악

 

•  

 

 

 

나의 문제풀이 방식 및 순서

 

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

 

문제를 틀리시는 모든 분들은 아마 이러한 이유일 듯 합니다.

1. 출력의 시간도 고려 필요

2. 배열의 경우 주소값을 공유하기 때문에 return 값 불 필요(이건 나만 해당)

3. 퀵 정렬 pivotIndex를 꼭 맨앞부터 할 필요 없음(퀵 정렬일때)

 

 

예시 - > 3 7 8 1 5 9 7 10 2 4 

1. 3 7 8 1 5 9 6 10 2 4 ( 3 이 pivotIndex 시작)(왼쪽에서는 pivotIndex보다 큰 값, 오른쪽에서는 pivotIndex보다 작은 값)
2. 3 2 8 1 5 9 7 10 7 4 ( 7 < - > 2 ) 
3. 3 2 1 8 5 9 6 10 7 4 ( 8 < - > 1 )
4. 1 2 3 8 5 9 6 10 7 4 ( 엇갈릴 경우 왼쪽을 기준으로 값을 교환한다.) (더 이상은 없다는 뜻임)
5. 1 2 3 8 5 9 6 10 7 4 ( 9 < - > 4 )
   ( 1,2 를 그룹1, 8~4까지 그룹2 )
   ( 그룹1 에서는 왼쪽부터 큰값 , 오른쪽부터 작은 값을 고르면 엇갈리니 1은 확정된다. 자동적으로 2도 확정된다 )
   ( 그룹2 에서는 
6. 1 2 3 8 5 4 6 10 7 9 ( 10 < - > 7 )
7. 1 2 3 8 5 4 6 7 10 9 ( 7 < - > 8   )( 엇갈릴 경우 왼쪽을 기준으로 값을 교환한다.) 
8. 1 2 3 7 5 4 6 8 10 9 
   ( 7~6를 그룹1, 10,9까지 그룹2)
   
   
9. 1 2 3 7 5 4 6 8 10 9 ( 7 < - > 6 )
10. 1 2 3 6 5 4 7 8 10 9 

 

예시 - > 7 2 1 6 8 

1. 6 2 1 7 8 (피벗인덱스 1을 설정)
2. 6 2 1 7 8 ( i = 3 (=index) value = 7, j = 2 (=index) value = 1 ) 
3. 1 2 6 7 8 ( pivotIndex < - > j (=index) ) 
4. quickSort(numAry, 0, j-1 ) , quickSort(numAry, j + 1 , end ) 

 

 

---

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   //할당된 버퍼에 값 넣어주기

        int N = Integer.parseInt(br.readLine());
        int [] numAry = new int[N];
        
        for(int i = 0; i < N; i++ ){
            numAry[i] = Integer.parseInt(br.readLine());
        }
        quickSort(numAry, 0, N-1);

        StringBuilder st = new StringBuilder();
        for(int i : numAry){
            st.append(i).append("\n");
        }
        bw.write(st.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static void quickSort(int [] data, int start, int end){ 
        /*start : 분할하려는 부분 집합의 시작
          end   : 분할하려는 부분 집합의 시작*/
        if(start>=end){
            return;
        }

        int pivotIndex = new Random().nextInt(end - start + 1) + start;
        swap(data, start, pivotIndex);
        //start 0 , End 100 = 101 즉 0~100까지 중 하나 생성
        //start 3 , End 80  일때 0~77인데 +start로 인해 3~77 중 하나 생성
        //그 랜덤 값 중 하나(pivotIndex)를 맨 앞자리로 가져온다.
        
        int key = start; //키는 첫 번째 인덱스
        int i = start+1; //왼쪽 출발 인덱스
        int j = end; //오른쪽 출발 인덱스
        int temp;

        while(i <= j){ //1. 전체 배열의 index 엇갈리 여부 확인
            while (i <= end && data[i] <= data[key]) {
                i++;
            }    
            while (j > start && data[j] >= data[key]) {
                j--;
            }
            
            if(i > j){ //1. 내부 배열의 엇갈린 상태일때는 키 값과 교체
            	swap(data, j, key); //j는 작은 값 i는 큰 값이니, pivotIndex를 j와 교체하여 작은 값을 맨 앞자리 확정
                //temp = data[j];
                //data[j] = data[key];
                //data[key] = temp;
            } else { //i의 큰값과 j의 작은값을 교체
            	swap(data, j, i);
                //temp = data[j];
                //data[j] = data[i];
                //data[i] = temp;
            }
        }
        quickSort(data, start, j - 1);
        quickSort(data, j + 1, end);
    }
    
    public static void swap(int[] data, int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
}

 

예시 - > 7 2 1 6 8 

1. 6 2 1 7 8 (피벗인덱스 1을 설정)
2. 6 2 1 7 8 ( i = 3 (=index) value = 7, j = 2 (=index) value = 1 ) 
3. 1 2 6 7 8 ( pivotIndex < - > j (=index) ) 
4. 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