퀵 정렬 예시 & 버블 정렬과 속도 비교

목차

---

1. 퀵 정렬 개념

2. JAVA를 통한 퀵 정렬 구현 예시

3. 버블 정렬과 속도 비교

 

---

 

 1. 퀵 정렬 개념

퀵 정렬은 이름 그대로 정렬 알고리즘 중 빠른 속도를 내기 때문에 붙여진 이름이다.

간단한 구조를 가지고 있는 버블 정렬과 선택 정렬등과는 방식이 확연히 다르고 학습에 대한 난이도가 확 뛰는 게 느껴졌다.정렬하는 대략적인 방식은 아래와 같다. (자세한 방식은 아래 코드 참조)

 

 

1. 중앙값을 기준으로 왼쪽 숫자의 오른쪽 숫자를 중앙값과 비교한 뒤 조건에 따라 스왑 한다.

2. 그 후 인덱스를 위의 그림과 같이 개념적으로 쪼개며 같은 행위를 반복한다.

3. 위의 반복은 재귀함수와 스택을 이용한 반복문으로 구현한다. 

---

 2. JAVA를 통한  퀵 정렬 구현 예시

 

public static void quickSort(int arr[], int left, int right){

    int pl = left; // 왼쪽 커서
    int pr = right; // 오른쪽 커서
    int center = arr[(pl+pr)/2]; // 중앙 값

    for(int i = 0; i < arr.length; i++){
        if(i == left) System.out.print("|");
        System.out.print(arr[i]+",");

        if(i == right) System.out.print("|");
    }
    do {

        while (arr[pl] < center) pl++;
        while (arr[pr] > center) pr--;

        comCnt++;
        if(pl <= pr){
            swap(arr,pl++,pr--); // 교환을 했으니 다음 인덱스로 이동해야 함.
        }
    }while (pl <= pr);

    System.out.println();
    System.out.println("================== : left:"+left+" right:"+right+" 중앙값:"+center);

    if(pr > left ) quickSort(arr,left, pr);
    if(pl < right ) quickSort(arr,pl, right);
}

 

결과

|7,4,2,5,3,1,6,|
================== : left:0 right:6 중앙값:5
|1,4,2,3,|5,7,6,
================== : left:0 right:3 중앙값:4
|1,3,2,|4,5,7,6,
================== : left:0 right:2 중앙값:3
|1,2,|3,4,5,7,6,
================== : left:0 right:1 중앙값:1
1,2,3,4,|5,7,6,|
================== : left:4 right:6 중앙값:7
1,2,3,4,|5,6,|7,
================== : left:4 right:5 중앙값:5

 

로직

1. do while 문 내부에서 중앙값과 pl, pr을 비교하며 작은 값이 왼쪽 큰 값이 오른쪽에 있으면 다음 위치로 이동.
2. 이후 양측의 값들을 교환하면 배열의 값들을 중앙값 기준 작은 것은 왼쪽, 큰 것은 오른쪽으로 배치가 된다.
3. 마지막으로 위의 1,2번 행위를 재귀함수를 통해 반복해 주면 정렬이 끝나는 것이며, 시작 인덱스와 마지막 인덱스 값을 
   다시 세팅해 준 뒤 재귀 호출을 해야 한다.

가장 이해하기 어려웠던 부분이 재귀 호출 부분의 if 조건과 인덱스 재설정 부분인데 이해가 되었다 안되었다 해서 
학습이 더 필요해 보인다..

 

 3. 버블 정렬과 속도 비교

 

힘들게 구현했으니 실제 성능 차이가 어떻게 나는지 눈으로 확인해보고 싶어 5만 건의 데이터를 가지고 
버블 정렬과 비교를 해보았다.

 

3-1. 버블 정렬 속도 (5만 건)

public class BubbleSort {

    static long comCnt = 0; // 비교 횟수
    public static void main(String[] args){

        int no = 50000;
        int arr [] = new int[no];

        for(int i = 0; i < no; i++){
            arr[i] = (int) (Math.random() * no);
        }
        int count = no;

        System.err.println("=========== 연산 시작 ==============");
        long startTime = System.currentTimeMillis();
        bubbleSort(arr,count);
        long endTime = System.currentTimeMillis();

        long elapsedTime = endTime - startTime;
        System.err.println("비교 횟수 : "+ comCnt);
        System.err.println("알고리즘 실행 시간 : "+ elapsedTime*0.001 +"초");

        for(int elem : arr){
            System.out.print(elem+",");
        }
    }
    static void bubbleSort(int [] arr, int n){

        for(int i = 1; i <= n; i++){
            for(int j = n-1; j > 0; j--){
                comCnt++;
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }

    }

    static void swap(int [] arr, int idx1, int idx2){
        int t = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = t;
    }
}

 

결과

=========== 연산 시작 ==============
비교 횟수 : 2499950000
알고리즘 실행 시간 : 5.143초

 

 

3-2. 퀵 정렬 속도 (5만 건)

 

실행 코드는 위와 동일

=========== 연산 시작 ==============
비교 횟수 : 212914
알고리즘 실행 시간 : 0.006초

 

비교 횟수와 처리 시간에 대해 비교가 안될 정도로 차이가 난다.

퀵 정렬이라고 무조건 O(n log n) 의 시간 복잡도를 가지는 것은 아니므로 상황에 맞춰
적절한 알고리즘을 사용하여 O(n^2)의 시간 복잡도가 나오는 것은 피하도록 하자.