13 Sept 2013

QuickSort


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Arrays;

/**
 * 3way quick sort in order to improve performance in case of too many duplicates , where normal 
 * Quicksort subrouites averages to quadratic performance
 * @author Prateek
 *
 */
public class ModifiedQuickSort {

 private int arr[];
 private int size;

 public static void main(String[] args) {
  int []testInput={6,3,6,4,2,6,8,2};
  ModifiedQuickSort mdqs=new ModifiedQuickSort();
  mdqs.sort(testInput);
 }

 
 public void sort(int input[]) {
  arr=input;
  size=input.length;

  modified3wayQsort(0,size-1);

  System.out.println(Arrays.toString(arr));

 }

 /**
  * 3 WayQuick Sort
  * @param low
  * @param high
  */
 void modified3wayQsort(int low,int high)
 {
  if(high <= low)
   return ;
  int l=low,r=high;
  int v=arr[low]; // Partioning element 1st element
  int pivot=l+1;   
  while(pivot<=r)
  {
   if(arr[pivot] < v)
   {
    swap(pivot++,l++);
   }
   else if(arr[pivot] > v)
   {
    swap(pivot,r--);
   }
   else
    pivot++;
  }

  modified3wayQsort(low, l-1);
  modified3wayQsort(r+1, high);
 }

 /**
  * Swapping content
  * @param i
  * @param j
  */
 private void swap(int i,int j)
 {
  int temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }

}

No comments:

Post a Comment