Java Quick 정렬

알고리즘은 언제나 개념을 이해한 뒤에 정답을 보지 않고 직접 코딩을 해 보아야 실력이 되는 것 같습니다.
단순히 개념만 이해하고 넘어가면 개념만 남을 뿐 실제 코딩이 되지 않기 때문 입니다.

퀵정렬은 피봇(pivot)을 기준으로 기준값보다 크고 작음을 판별한 뒤에 서로의 위치를 바꾸어주는 알고리즘 입니다.
피봇(pivot)의 개념은 비교할 기준을 의미 합니다.

int data [] = {6,7,1,4,5,3,2};

 

위 처럼 숫자형 배열이 존재하는 경우에 기준을 6번값으로 한 뒤에 본인보다 크고 작은 숫자를 골라냅니다.
여기서 정렬방법은 오름차순 입니다.
크고 작은 숫자를 고르는 방법은 아래 사진처럼 진행합니다.

기준은 가장 첫번째에 있는 숫자 6인 경우의 방향 입니다.

숫자6을 기준으로 작은 값은 좌에서 우측으로 이동하며 찾습니다.
큰 값은 맨 마지막에서 이동하며 찾습니다.
해당 조건의 값을 찾을 때 까지 이동하다 해당 값을 찾으면 자리를 바꾸어 줍니다.

큰수와 작은수를 교체하는 방법 입니다.

 

이러한 내용을 반복하여 자리를 계속 바꾸어 정렬하는 방법이 퀵정렬 입니다.

 

 

#1. 나를 기준으로 데이터를 왼쪽 오른쪽 바꾸기

나를 기준으로 왼쪽과 오른쪽을 바꾸는 방법입니다.
그리고 우측 출발점은 배열의 길이의 -1 값 입니다.
나를 기준으로 크고 작은 값을 반복문을 통해서 찾은 뒤에 교체를 해 주면 됩니다.

{
    int me = 0;  //기준점(나중에 피봇으로 불립니다)
    int left = me;  //좌측 시작점
    int right = data.length-1; // 우측 시작점

    while (data[me] > data[left]){  //나보다 값이 클 때 까지 값을 증가하며 찾습니다.
        left++;
    }

    while (data[me] < data[right]){  //나보다 값이 작을 때 까지 값을 증가하며 찾습니다.
        right--;
    }
    change(data, left, right);  //해당 값의 위치를 바꿉니다.
    System.out.println(Arrays.toString(data));
}

public void change (int data [] , int left, int right){
    int tmp = data[left];
    data[left] = data[right];
    data[right] = tmp;
}

 

데이터의 위치를 찾아서 바꾸는 방법은 어렵지가 않습니다.
위 방법이 퀵정렬의 주요 구조라 볼 수 있습니다.

 

 

#2. 좌측, 우측에 대한 기준
#1에서 새운 기준에 의하면 딱 한번만 동작하기 때문에 데이터는 한번만 바뀌게 됩니다.
그러므로 이를 기준값을 대상으로 끝까지 동작하게 해야 합니다.
왼쪽에서의 순서(인덱스) 값이 우측에서의 순서(인덱스)보다 작으면 멈추는 반복문을 추가하여 보겠습니다.

int index = 0;  //최초 인덱스
int me = data[index];  //기준 값(맨 처음 값을 기준으로 비교 합니다)
int left = index;  //왼쪽 출발지점
int right = data.length-1;  //오른쪽 출발 지점

while(left < right){
    while (me > data[left]){
        left++;
    }
    while (me < data[right]){
        right--;
    }
    change(data, left, right);
    System.out.println("순회중 : "+Arrays.toString(data));     
}
System.out.printf("내 기준값 : %d, 마지막 왼쪽 data[%d] : %d, 마지막 오른쪽 data[%d] : %d\n",me,left,data[left], right, data[right]);
System.out.println("다 동작하고 나서 : "+Arrays.toString(data));     

이렇게 동작하게 하면 둘은 인덱스 4(숫자 5)의 지점에서 멈추게 됩니다.
자세히 데이터를 보면 멈춘 지점으로부터의 왼쪽 값들은 기준값인 5보다 작으며, 우측에 있는 값은 5보다 큰 것을 알 수 있습니다.
이것이 바로 좌측이 우측보다 작을 때 까지 반복문을 돌려야 하는 개념 입니다.
퀵정렬에서의 핵심 부분은,
좌측에서의 인덱스가 우측인덱스보다 작을 때 까지 바꾸기를 계속하는 것 입니다.

5는 4번째 위치합니다.

 

#3. 재귀 호출
#2의 방법을 토대로 유추 할 수 있는 것은 끝난 왼쪽 값, 끝난 오른쪽 값 입니다.
끝난 왼쪽 순서와 끝난 오른쪽 순서를 가지고 왼쪽의 시작점, 오른쪽의 시작점으로 다시 정렬해 주도록 메소드를 작성 합니다.

    public static void todo(int data [] , int left, int right){
        int pivot = data[left];  //기준값
        int originL = left;  //시작 왼쪽점 기록
        int originR = right; //시작 오른쪽점 기록
        
        while(left < right){  //왼쪽과 오른쪽 값이 만나면 멈춥니다. 
            while (left < right && pivot > data[left]){
                left++;
            }
            while (left < right && pivot < data[right]){
                right--;
            }
            change(data, left, right);
        }
        
        //두 값이 일치하지 않다는 것은 바꿀 대상이 존재함을 의미 합니다.
        if(left > originL){  
            todo(data, originL, left);
        }
        if(left == right){  //두 값이 일치하다는 것은 동일한 지점에서 만났다는 뜻 입니다.
            right++;
        }
        if(originR > right){
            todo(data, right, originR);
        }
    }
    

    public static void change (int data [] , int left, int right){
        int tmp = data[left];
        data[left] = data[right];
        data[right] = tmp;
    }

 

난이도가 역시 마지막에는 급하게(?) 올라가는 것 같습니다.
#2의 개념에 의해서 좌측의 시작 - 종료 인덱스 값을 알 수 있습니다.
마찬가지로 우측의 시작 - 종료 인덱스를 알 수 있습니다.
그러므로 해당 인덱스 범위만큼 반복문을 통해 좌우 내용을 교체해 주면 배열의 모든 값이 #1을 만족하게 되므로 데이터가 정렬되게 됩니다.

정렬!

 

위 코드처럼 재귀호출을 통해서 깔끔하게 코드가 작성되는 것을 볼 수 있습니다.
이상으로 퀵정렬에 대해서 살펴 보았습니다.

익숙치 않는 부분이라 역시 틀린부분이 있을수도 있겠습니다..;ㅁ;

궁금한 점이나 문의사항은 언제든 연락주세요!