퀵정렬

퀵 정렬이란?

- 기준값(pivot)을 정한뒤 기준값(pivot)을 기준으로 데이터를 대소 그룹의 둘로 나누어

두개에 집합을 만든뒤 분할하여 전체 정렬을 만들어 내는 정렬 알고리즘.

 

+ 기존 정렬 알고리즘 들 의 비하여 빠른 실행성능을 가진다.

- 기준값(pivot)을 어떻게 설정하느냐의 따라 실행성능이 좌우된다.

 

 

퀵정렬 처리구조 

1. pivot 정하기 

2. pivot 중심으로 대소관계를 나누어 2개의 집합으로 분할 하는 처리

3.  작은수의 집합에 2번 처리를 반복

4.  높은수의 집합에 2번 처리를 반복

 

코드구현

 public void QuickSort(int[] array, int left, int right){
        
        int i = left + 1;
        int k = right;
        int w = 0;

        while( i < k ){
            
            // 기준값 보다 큰수 찾기 
            while( array[left] > array[i] && i < right){
                i++;
            }
            // 기준값 보다 작은수 찾기 
            while( array[k] >= array[left] && k > left){
                k--;
            }
            
            // 값 자리변경 
            if( i < k ){
            w = array[i];
            array[i] = array[k];
            array[k] = w;
            }
        } // pivot 값 배열 첫번째에서 중간으로 이동 
        w = array[left];
        array[left] = array[k];
        array[k] = w;
        
        // 재귀함수 호출 
        if(left < k-1 ){ //  낮은값 집합의 왼쪽 끝 수 와 pivot 값 까지 실행. 
            QuickSort(array, left, k-1);    //  작은수 집합 만큼 퀵솔트 메소드 실행 
        }
        }
        if(k+1 < right){ // 높은값 집합의 오른쪽 끝 수 와 pivot 값 까지 실행. 
            QuickSort(array, k + 1, right);     // 높은수 집합 만큼 퀵솔트 메소드 실행 
        }
              
       }
    }
    
    
    // Main
    
    public static void main(String[] args) {

      Car c1 = new Car(); // QuickSort 클레스 

      int[] array = {5,4,7,6,8,3,1,2,9};
      int left = 0;
      int right = array.length - 1;
    
        c1.QuickSort(array, left, right);
     
        for(int a=0; a < array.length; a++){
            System.out.print(array[a]+",");
        }
        System.out.println();
            
    }

 

처리순서

배열 초기값 = 5,4,7,6,8,3,1,2,9

 

 

 

쿽정렬의 개념적 이해를 돕기위해서는 나무위키 참고바람

(언어별로 친절하게 알려줌) 

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC