[알고리즘]-[정렬]-퀵정렬(JAVA)

퀵정렬 (quick sort)

개념 

• 원소를 하나 정하여(여기서는 배열의 맨 앞 요소를 기준으로 정함) 이 원소를 pivot 이라 지칭하고 pivot 보다 작거나 같은 수들과 큰 수들을 좌우로 나누면서 정렬하는 방식
• pivot 의 위치는 정렬 후의 위치로 확정된다.
• pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다.
  왼쪽은 pivot 보다 무조건 작거나 같은 원소들, 오른쪽은 pivot 보다 무조건 큰 원소들이 위치한다.

재귀함수 디자인의 과정

1. 작성하려는 함수의 역할을 말로 명확하게 정의한다.
   
   

       // arr을 start 부터 end 까지 퀵정렬하는 함수
       public void quickSort(int arr[], int start, int end) {
           
       }

2. 함수가 기저조건에서 제대로 동작하게 작성한다.
   
   

       // arr을 start 부터 end 까지 퀵정렬하는 함수
       public void quickSort(int arr[], int start, int end) {
           // start 가 end 보다 클 떄는 숫자가 없을경우
           // start 가 end 와 같으면 숫자가 하나만 존재하는 경우
           if(start >= end) {
               return;
           }
           
       }

3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다
   
   

   // arr을 start 부터 end 까지 퀵정렬하는 함수
       public void quickSort(int arr[], int start, int end) {
           // start 가 end 보다 클 떄는 숫자가 없을경우
           // start 가 end 와 같으면 숫자가 하나만 존재하는 경우
           if(start >= end) {
               return;
           }
           // pivot 을 구한다. -> pivot은 항상 start로 정한다
           int pivot = arr[start];
           
           // 순서 1) pivot을 기준으로 작거나 같은 배열을 left 배열에 구한다.
           // 순서 2) pivot을 기준으로 큰 배열을 right 배열에 구한다.
           // 순서 3) left 배열 + 피벗 + right 배열 순으로 배열을 합친다.
           // 순서 4) pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 퀵정렬 하게 같은 함수를 호출한다.
    
       }

소스 (JAVA)

import java.util.Arrays;
 
public class SortMain {
    
    public static void main(String[] args) {
        int[] intArr01 = { 25, 90, 11, 3, 2, 6, 9, 33, 10, 25 };
        int[] intArr02 = { 90, 111, 2, 2, 44, 5, 3, 222, 1, 2, 30, 50, 222, 10, 20, 66, 3, 30, 10, 250, 243, 565, 31, 10, 200 };
        
        int[] quickSortArr = intArr02.clone();
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(quickSortArr, 0, quickSortArr.length-1);
        
        System.out.println("Quick Sort : " + Arrays.toString(quickSortArr));
    }
}
 
public class QuickSort {
    // arr을 start 부터 end 까지 퀵정렬하는 함수
    public void quickSort(int arr[], int start, int end) {
        // start 가 end 보다 클 떄는 숫자가 없을경우
        // start 가 end 와 같으면 숫자가 하나만 존재하는 경우
        if(start >= end) {
            return;
        }
        // pivot 을 구한다.
        int pivot = arr[start];
        
        // 순서 1) pivot을 기준으로 작거나 같은 배열을 left 배열에 구한다.
        // 순서 2) pivot을 기준으로 큰 배열을 right 배열에 구한다.
        // 순서 3) left 배열 + 피벗 + right 배열 순으로 배열을 합친다.
        // 순서 4) pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 퀵정렬 하게 같은 함수를 호출한다.
 
        int[] left = new int[end-start+1];
        int[] right = new int[end-start+1];
        
        
        int left_cnt = this.getLeft(arr, start+1, end, pivot, left);
        int right_cnt = this.getRight(arr, start+1, end, pivot, right);
        
        for(int i=0; i <left_cnt; i++) {
            arr[start+i] = left[i];
        }
        
        arr[start+left_cnt] = pivot;
        
        for(int i=0; i < right_cnt; i++) {
            arr[start+left_cnt+1+i] = right[i];
        }
        
        this.quickSort(arr, start, start+left_cnt-1);
        this.quickSort(arr, start+left_cnt+1, end);
    }
    
    private int getLeft(int arr[], int start, int end, int pivot, int result[]) {
        // arr의 start 부터 end 까지 숫자들 중에서 
        // pivot 보다 작은 값을 result 에 채우는 함수
        // 작거나 같은 원소의 개수를 반환
        int idx = 0;
        for(int i=start; i <=end; i++) {
            if(arr[i] <= pivot) {
                result[idx++] = arr[i];
            }
        }
        
        return idx;
    }
    
    private int getRight(int arr[], int start, int end, int pivot, int result[]) {
        // arr의 start 부터 end 까지 숫자들 중에서 
        // pivot 보다 큰 값을 result 에 채우는 함수
        // pivot 보다 큰 원소의 개수를 반환한다.
        int idx = 0;
        for(int i=start; i <=end; i++) {
            if(arr[i] > pivot) {
                result[idx++] = arr[i];
            }
        }
        
        return idx;
    }
    
}