Question 3c Finding Smallest K Numbers

A even more effective way dealing with this problem is to use linear time selection. The major idea of linear time selection is to recursively invoke the partition subroutine like a qucik sort which use a pivot to partition the array. After it finds the kth smallest element, all the elements less than or equals to it are relocated to the left of the pivot and those bigger than it are relocated to the right. So the solution to the original problem is to output all left elements to the kth smallest element and including itself.

 

The process of utilizing the partition subroutine to find the kth smallest element is like below :

    1) Choose a pivot to partition the whole array, after partion all elements less than or equals to the pivot are relocated to the left of the pivot and those bigger than the pivot are relocated to the right.

    2) Suppose the position of the pivot after partition is p, if p == k , then you find the kth smallest element otherwise,

        a)  if p < k , then kth smallest element is to the right of the pivot , then recursively to find the ( k-p ) th smallest element in the right subarray which is the kth smallest element in the whole array.

        b)  If p < k , then kth smallest element is to the left of the pivot , then recursively to find the kth smallest element in the left subarray which is the kth smallest element in the whole array.

 

Like quick sort, the performance depends on how you choose the pivot. For details , you can refer to : http://seanzhou.iteye.com/blog/1820426.  The following codes implement the randomized pivot choosing whose expected time is O(n) and the medium of medium pivot choosing whose worst time is O(n).

 

The suffle method in the following codes is to do a random suffle of the orginal array, you can refer to :http://seanzhou.iteye.com/blog/1770403

 

public class KSmallestC {

	
	
	public static void main(String[] args) {
		assertEquals(new int[]{1,2,3,4}, getKSmallestByRandomPivot(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4));
        assertEquals(new int[]{1,2,3,4}, getKSmallestByRandomPivot(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 4));
        assertEquals(new int[]{21,22,14,18,9}, getKSmallestByRandomPivot(new int[]{27, 14, 18, 22, 21, 91, 33, 36, 42, 78 , 9, 65, 101, 29}, 5));
        
        assertEquals(new int[]{1,2,3,4}, getKSmallestByMediumPivot(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4));
        assertEquals(new int[]{1,2,3,4}, getKSmallestByMediumPivot(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 4));
        assertEquals(new int[]{21,22,14,18,9}, getKSmallestByMediumPivot(new int[]{27, 14, 18, 22, 21, 91, 33, 36, 42, 78 , 9, 65, 101, 29}, 5));
	}
	
	private static int[] getKSmallestByRandomPivot(int[] arr, int k ) {
		Selector s = new PartitionSelector(arr, new RandomPivotChooser());
		s.select(k);
		int[] result = new int[k];
		System.arraycopy(arr, 0, result, 0, k);
		return result;
	}
	
	private static int[] getKSmallestByMediumPivot(int[] arr, int k ) {
		Selector s = new PartitionSelector(arr, new MediumOfMediumChooser());
		s.select(k);
		int[] result = new int[k];
		System.arraycopy(arr, 0, result, 0, k);
		return result;
	}

	private static void assertEquals(int[] standard, int[] result) {
		Arrays.sort(standard);
		Arrays.sort(result);
		assert Arrays.equals(standard, result);
		
	}
	
    public interface Selector {
    	int select( int index );
    }
    
    public static class PartitionSelector implements Selector{
    	private int[] arr;
		private PivotChooser chooser;

		public PartitionSelector (int[] arr , PivotChooser chooser){
    		this.arr = arr;
    		this.chooser = chooser;
    		chooser.initialize(arr);
    				
    		
    	}

		@Override
		public int select(int index) {
			if (index < 0 && index >= arr.length) throw new IllegalArgumentException("Index out of boundary");
			int end = arr.length;
			int start = 0;
			int pivotIndex = chooser.choosePivot(start, end);
			pivotIndex = partition(start, end, pivotIndex);
			while (pivotIndex != index) {
				if( pivotIndex > index ) {
					end = pivotIndex;
					pivotIndex = chooser.choosePivot(start, end);
					pivotIndex = partition(start, end, pivotIndex);
					
				} else {
					start = pivotIndex + 1;
					pivotIndex = chooser.choosePivot(start, end);
					pivotIndex = partition(start, end, pivotIndex);
				}
			}
			
			return arr[index];
		}
		
		private int partition(int start, int end , int pivotIndex){
			//swap with the partition element with the first one
			int temp = arr[start];
			arr[start] = arr[pivotIndex];
			arr[pivotIndex] = temp;
			int pivot = arr[start];
			int i=start+1,j=end-1;
			while( i <= j ) {
				while ( i <= j && arr[i] <= pivot ) i ++;
				if (i > j) break;
				while (arr[j] > pivot ) j--;
				if ( i > j) break;
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
			i--;
			arr[start] = arr[i];
			arr[i] = pivot;
			return i;
			
		}
		
		
    }
	
	
	
	
	public static class RandomPivotChooser implements PivotChooser{

		private int[] arr;
		private boolean init;

		
		private void shuffle() {
			Random random = new Random();
			int temp, j;
			for ( int i = 1 ; i < arr.length ; i ++ ) {
				j = random.nextInt(i+1);
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
		@Override
		public int choosePivot(int start, int end) {
			if (! init )  throw new IllegalStateException("Pivot Chooser not initialized!");
			if ( start >= end ) throw new IllegalArgumentException("end should bigger than start!");
			if ( end > arr.length ) throw new IllegalArgumentException("end should not bigger than arry length!");
			return start;
		}

		@Override
		public void initialize(int[] arr) {
			this.arr = arr;
			shuffle();
			this.init = true;
			
		}
		
	}
	
	public static class MediumOfMediumChooser implements PivotChooser{

		private int[] arr;
		private boolean init;
		
		@Override
		public int choosePivot(int start, int end) {
			if ( start >= end ) throw new IllegalArgumentException("end should bigger than start!");
			if ( end > arr.length ) throw new IllegalArgumentException("end should not bigger than arry length!");
			if (! init )  throw new IllegalStateException("Pivot Chooser not initialized!");
            if ( end - start <= 2) {
            	return start;
            }
			
			// sort elements in each block
			int BLOCK_SIZE = 5;
			int i = BLOCK_SIZE;
			int num = 1;
			for ( ; i < end ; i += BLOCK_SIZE , num ++) {
				insertionSort(i - BLOCK_SIZE, i);
			}
			i -= BLOCK_SIZE;
			insertionSort(i, end);

			// choose medium of each group
			int medium = BLOCK_SIZE/2;
			int[] mediums = new int[num];
			int r = ( i + end ) / 2; // medium item in last block
			i = 0 ;
			for ( int j = medium; i < num - 1 ; j += BLOCK_SIZE, i ++ ) {
				mediums[i] = arr[j];
			}
			mediums[i] = arr[r];
			
			
			
			Selector selector = new PartitionSelector(mediums, new MediumOfMediumChooser());
			int pivot = selector.select(num/2);
			for ( i = start; i < end; i ++) {
				if ( arr[i] == pivot) return i;
			}
			
			throw new IllegalStateException("Medium of Medium didn't find a correct pivot!");
		}


		@Override
		public void initialize(int[] arr) {
			this.arr = arr;
			this.init = true;
			
		}
		
		private void insertionSort(int start, int end) {
			int temp;
			for ( int i = start + 1; i < end ; i ++ ) {
		       for ( int j = i ; j > 0 ; j --) {
		    	   if ( arr[j] < arr[j-1] ) {
		    		  temp = arr[j];
		    		  arr[j] = arr[j-1];
		    		  arr[j-1] = temp;
		    	   } else {
		    		   break;
		    	   }
		       }
			}
		}
		
	}
	
	public interface PivotChooser{
		//return the index of the new pivot
		int choosePivot(int start, int end);
		void initialize(int[] arr);
	}

}