Let’s start with the output-
Array to sort: [80, 30, 10, 5, 7, 40, 0]
Mid: 3
Pivot: 5
Left Array: [5, 0]
Right Array: [80, 30, 10, 7, 40]
Mid: 1
Pivot: 0
Left Array: [0]
Right Array: [5]
Inter list: (can u see that ? it's getting better)
0 5
Mid: 2
Pivot: 10
Left Array: [10, 7]
Right Array: [80, 30, 40]
Mid: 1
Pivot: 7
Left Array: [7]
Right Array: [10]
Inter list: (can u see that ? it's getting better)
7 10
Mid: 1
Pivot: 30
Left Array: [30]
Right Array: [80, 40]
Mid: 1
Pivot: 40
Left Array: [40]
Right Array: [80]
Inter list: (can u see that ? it's getting better)
40 80
Inter list: (can u see that ? it's getting better)
30 40 80
Inter list: (can u see that ? it's getting better)
7 10 30 40 80
Inter list: (can u see that ? it's getting better)
0 5 7 10 30 40 80
Huh...I'm done. It's quite a logic.
Sorted Array: [0 5 7 10 30 40 80 ]
partition(int[] list)divides the list and sort it. So to sort any array of randomly ordered elements, pass the unsorted array to this method and it will return back the sorted array.
/**
* It is a recursive function which will make partition and sort.
*
* @param list- unsorted list
* @return
*/
public int[] partition(int[] list){
if(list.length == 1 || list.length == 0){
/*
* Only one element in the list or no element.
* Come on! You are still testing me?
*/
return list;
}
/*
* Get the mid position of the list and consider that as the
* Pivot element
*/
int mid = list.length/2;
int pivot = list[mid];
System.out.println("Mid: "+ mid);
System.out.println("Pivot: "+ pivot);
/*
* Use some dynamic structure, as you still don't know how many can
* come in the Left and Right partition. I guess ArrayList will be
* good as you can quickly get the Array back...
*/
ArrayList leftList = new ArrayList();
ArrayList rightList = new ArrayList();
for(int i=0; i length; i++){
if(list[i] <= pivot){
/*
* Put all smaller and equals in the Left Partition
*/
leftList.add(new Integer(list[i]));
}
else
/*
* This is for big boys...all values greater than Pivot
*/
rightList.add(new Integer(list[i]));
}
System.out.println("Left Array: "+ leftList);
System.out.println("right Array: "+ rightList);
/*
* Return back my arrays.
* Create the arrays which will keep the recursive processing rational
*/
int[] leftArray = new int[leftList.size()];
int[] rightArray = new int[rightList.size()];
for(int i=0; i
leftArray[i] = leftList.get(i).intValue();
for(int i=0; i
rightArray[i] = rightList.get(i).intValue();
/*
* Repeat the same logic with Left and Right partition
*/
leftArray = partition(leftArray);
rightArray = partition(rightArray);
int li = 0;
int ri = 0;
/*
* As the individual partitions get sorted, put them back in the
* main list
*/
for(int i=0; i<list.length; i++){
if(li < leftArray.length){
list[i] = leftArray[li++];
continue;
}
if(ri < rightArray.length){
list[i] = rightArray[ri++];
}
}
/*
* You can check how the sorting is progressing in
* intermediate stages-
*/
System.out.println("Inter list:(can u see that? it's getting better) ");
int x = 0;
while(x < list.length)
System.out.print(list[x++]+" ");
System.out.println();
return list;
}
Please feel free to share any error cases in the above implementation.
No comments:
Post a Comment