[알고리즘]Vladimir's Algorithm

QuickSort와 Vladimir's Algorithm의 성능을 비교해봄.

 

<소스코드>

import java.util.*;

public class HW3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Random random = new Random();
		int[] n = { 17, 33, 65, 129, 257, 513};
        int[] size= {10000, 100000, 200000, 400000, 800000, 1600000, 3200000, 6400000};
        
        for(int i = 0; i < size.length; i++) {
        	long arr[] = new long[size[i]];
        	   	      
     	    for (int j = 0; j < arr.length; j++) { //난수 발생
     	       arr[j] = random.nextInt(99999);
     	    }
     	    
     	    long startTime, endTime;
     	    
     	    System.out.println("<SIZE : " + size[i] + ">");
     	    
     	    //퀵정렬 시간
     	    System.out.print("QuickSort Time : ");
     	    startTime = System.currentTimeMillis();
	        quickSort(arr, 0, arr.length - 1);
	        endTime = System.currentTimeMillis();
	        System.out.println((endTime - startTime) + "ms");
     	    
	        //vladimir 시간
	        for(int k = 0; k < n.length; k++) {
	        	System.out.print("n = " + n[k] + " vladimir Time : ");
	      	    startTime = System.currentTimeMillis();
	 	        dualquickSort(arr, 0, arr.length - 1, n[k]);
	 	        endTime = System.currentTimeMillis();
	 	        System.out.println((endTime - startTime) + "ms");
	        }
        }
        
	    System.out.println();
	}
	
	public static void swap(long[] arr, int a, int b) {
		long temp;
		temp =  arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	
	public static void insertionSort(long[] A, int n) {
		int i;
		for(i = 1; i < n; i++) {
			int j = 0;
			int m, k;
			for(j = 0; j < i; j++) 
				if(A[j] > A[i])
					break;
			m = (int) A[i];
			
			for(k = i; k > j; k--) 
				A[k] = A[k-1];
					
			A[j] = m;
		}
	}
	
	public static void quickSort(long[] A, int p, int r) {	
		int q = partition(A, p, r);
		if (p < q - 1) 
		    quickSort(A, p, q - 1);
		if (r > q) 
		    quickSort(A, q, r);
	}
	
	
	public static void dualquickSort(long[] A, int p, int r, int n) {
		if (p < r) {
            if(r - p < n) 
            	insertionSort(A, n);

            int[] pivot = dualPartition(A, p, r);
			
            if (p < pivot[0] - 1)
                dualquickSort(A, p, pivot[0] - 1, n);
             if (p > pivot[0] + 1 && r < pivot[1] - 1)
                dualquickSort(A, pivot[0] + 1, pivot[1] - 1, n);
             if (r > pivot[1] + 1)
                dualquickSort(A, pivot[1] + 1, r, n);

		}
	}
	
	public static int partition(long[] A, int p, int r) {
		int q = (int) A[(p + r) / 2];
	    while (p <= r) {
	        while (A[p] < q) p++;
	        while (A[r] > q) r--;
	        if (p <= r) {
	        	swap(A, p, r);
	            p++;
	            r--;
	        }
	    }
	    return p;
	}

	public static int[] dualPartition(long[] A, int p, int r) {
		if (A[p] > A[r]) 
			swap(A, p, r);
		
        long p1= A[p];
        long p2 = A[r];

        int l = p + 1, g = r - 1, k = l;
        while (k <= g) {
           if (A[k] < p1) {
              swap(A, k, l);
              ++l;
           } 
           else if (A[k] >= p2) {
              while (A[g] > p2 && k < g) {
            	  --g;
              }
              swap(A, k, g);
              --g;
              if (A[k] < p1) {
                 swap(A, k, l);
                 ++l;
              }
           }
           ++k;
        }
        --l; 
        ++g;

        swap(A, p, l); 
        swap(A, r, g);
	  
	    return new int[] { l, g };
	}

}

<성능 그래프>

QuickSort와 Vladimir's Algorithm

n의 값에 따른 성능 비교 분석 그래프