ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Quick Sort (퀵정렬, 퀵소트)
    algorithm 2013. 6. 5. 10:34
    반응형

    참조
    1. http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
    2. http://en.wikipedia.org/wiki/Quicksort
    3. http://codereview.stackexchange.com/questions/4022/java-implementation-of-quick-sort


    시간복잡도
    가장 나쁜 경우 : O(n^2)
    가장 좋은 경우 : O(n log n)
    평균 성능 : O(n log n)


    장점
    대부분의 경우에 빠르게 정렬이 가능.

    단점

    운이 없을때는 O(n^2) 만큼의 정렬 시간이 걸림.

    알고리즘

    1. 리스트에서 피봇(pivot)으로 사용할 원소를 선택
    2. 리스트를 재정렬함. 이때 피봇보다 작은 값은 피봇 이전에 오게하고 피봇보다 큰 값은 피봇다음에 오게함.
        피봇하고 같은 값은 앞이나 뒤 어디에 와도 됨.
        이과정이 끝나면 사용된 피봇의 위치는 고정됨.
        이 과정을 피봇연산이라고 함.
    3. 2번 과정을 원소들의 하위 리스트(각각 큰값과 작은값으로 정렬된 목록에 대해서)들에 재귀적으로 적용함.

    소스

    import java.util.*;
    
    public class QuickSort {
    
    	private static double TargetDataList[] = null;
    	private static boolean pivotList[] = null;
    	
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    
    		int nData = 10; // 정렬할 데이터 개수 설정.
    		TargetDataList = new double[nData];
    		double DataForRecursive[] = new double[nData];
    		
    		// 데이터 생성
    		for (int i = 0; i < nData; i++) {
    			TargetDataList[i] = Math.random();
    			DataForRecursive[i] = TargetDataList[i];
    //			System.out.print(TargetDataList[i] + " "); // 데이터 출력
    		}
    //		System.out.println();
    		
    		pivotList = new boolean[nData];
    
    //		비재귀(Non-Recursive) Quick Sort
    		for(int i = 0; i < TargetDataList.length; i++){
    			if(executeNonRecursiveQuickSort()){
    				break;	//정렬이 완료되면 중간에라도 루프를 빠져나옴.
    			}
    		}
    		
    //             재귀(recursive) Quick Sort
    		recursiveQuickSort(DataForRecursive, 0, DataForRecursive.length - 1 );
    		
    //		// 정렬된 데이터 출력
    //		for (int i = 0; i < nData; i++) {
    //			System.out.print(TargetDataList[i] + " "); // 데이터 출력
    //		}
    //		System.out.println();		
    //		for (int i = 0; i < nData; i++) {
    //			System.out.print(DataForRecursive[i] + " "); // 데이터 출력
    //		}
    //		System.out.println();
    	
    	}
    
    	
    	private static boolean executeNonRecursiveQuickSort() {
    		
    		boolean isSorted = false;	//모든 원소가 정렬되었으면 true, 아니면 false
    		
    		List sortedPivotIdx = new ArrayList();
    		
    		//정렬된 pivot 위치를 확인
    		for(int i = 0; i < pivotList.length; i++){
    			if(pivotList[i] == true){
    				sortedPivotIdx.add(i);
    			}
    		}
    		
    		if(sortedPivotIdx.size() == TargetDataList.length){
    			return isSorted = true; 
    		}
    		
    		if(sortedPivotIdx.size() == 0){
    			intervalSort(0, TargetDataList.length - 1);
    		} else if (sortedPivotIdx.size() > 0) {
    
    			int startPosition = 0;
    			int endPosition = 0;
    
    			// 첫번째 원소부터 첫번째 pivot까지 처리
    			startPosition = 0;
    			endPosition = sortedPivotIdx.get(0) - 1;
    			
    			if(sortedPivotIdx.get(0) == 0 && sortedPivotIdx.size() > 1){	//정렬된 Pivot값이 0번 인덱스일때는 1번 인덱스부터 처리
    				startPosition = 1;
    				endPosition = sortedPivotIdx.get(1) - 1;
    			}
    			intervalSort(startPosition, endPosition);
    
    			
    			// 정렬된 pivot 사이에 추가 정렬할 원소가 있는지 확인.
    			for (int i = 1; i < sortedPivotIdx.size() - 1; i++) {
    				if ((sortedPivotIdx.get(i + 1) - sortedPivotIdx.get(i)) > 0) {
    
    					/* 정렬할 원소가 있는 구간은 정렬수행 */
    					startPosition = sortedPivotIdx.get(i) + 1;
    					endPosition = sortedPivotIdx.get(i + 1) - 1;
    
    					intervalSort(startPosition, endPosition);
    
    				}
    			}
    
    			// 마지막 pivot부터 행렬끝까지 부분에 대한 처리
    			startPosition = sortedPivotIdx.get(sortedPivotIdx.size() - 1) + 1;
    			if(startPosition >= TargetDataList.length){startPosition = TargetDataList.length - 1;}
    			
    			endPosition = TargetDataList.length - 1;
    			intervalSort(startPosition, endPosition);
    		}
    		
    		return isSorted;
    	}
    
    	//개별 구간에서 pivot값에 대한 좌우정렬 실행.
    	static void intervalSort(int startPosition, int endPosition){
    		double pivotValue = TargetDataList[startPosition];
    		int pivotIdx = startPosition;
    		
    		List lowerList = new ArrayList();
    		List upperList = new ArrayList();
    		List equalList = new ArrayList();
    		
    		//pivot 값을 기준대비 크고 작은 값을 분류함.
    		for(int dataIdx = startPosition; dataIdx <= endPosition; dataIdx++){
    			if(TargetDataList[dataIdx] > pivotValue){
    				upperList.add(TargetDataList[dataIdx]);
    			}else if(TargetDataList[dataIdx] < pivotValue){
    				lowerList.add(TargetDataList[dataIdx]);
    			}else{
    				equalList.add(TargetDataList[dataIdx]);
    			}
    		}
    		
    		//pivot 값 대비 분류된 값을 작은 값은 왼쪽, 큰값은 오른쪽에 배치함.
    		for(int dataIdx = 0; dataIdx < lowerList.size(); dataIdx++){
    			TargetDataList[startPosition + dataIdx] = lowerList.get(dataIdx); 
    		}
    		for(int dataIdx = 0; dataIdx < upperList.size(); dataIdx++){
    			TargetDataList[endPosition - dataIdx] = upperList.get(dataIdx); 
    		}
    		
    		//pivot값과 같은 값은 pivot값으로 인식해서 값을 배치한 다음 정렬된 pivot 인덱스에 저장함.
    		for(int dataIdx = 0; dataIdx < equalList.size(); dataIdx++){
    			TargetDataList[startPosition + lowerList.size() + dataIdx] = pivotValue;
    			pivotList[startPosition + lowerList.size() + dataIdx] = true;
    		}
    		
    	}
    	
    	
    	
    	public static void recursiveQuickSort(double[] a, int p, int r)
        {
            if(pp && a[j] > x)
                    j--;
    
                if (i < j)
                    swap(a, i, j);
                else
                    return j;
            }
        }
    
        private static void swap(double[] a, int i, int j) {
            double temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
    }
    
    
    



    반응형

    댓글

Designed by Tistory.