gate13 Posted February 22, 2015 Share Posted February 22, 2015 Hi. I have a small sequence of 4 elements that i need to apply the median of three partitioning quick sort algorithm I know how to do it with long sequences but here is my problem. the sequence is { 7, 17, 15, 19} the pivot is 15 what the i and what the j is? I am so confused. with many elements is easy to do the quick sort and the method of median of three but what about this case? can i and j be 15 at the same time? so confused. Link to comment Share on other sites More sharing options...
Sensei Posted February 22, 2015 Share Posted February 22, 2015 (edited) i & j are typical names of variables for counters f.e. for( int i = 0; i < 100; i++ ) {} Otherwise I don't know about what i & j, you're talking about. You didn't provide any sample code. Edited February 22, 2015 by Sensei Link to comment Share on other sites More sharing options...
fiveworlds Posted February 22, 2015 Share Posted February 22, 2015 public class QuickSort{ public static void main(String args[]){ int[] x={547,23,523,2378,243,7855,14,23,310}; System.out.println("Unsorted List:"); display(x); quickSort(x,0,x.length-1); } public static void quickSort(int x[], int lb, int ub){ int j=0; if(lb>=ub) return; j = partition(x, lb, ub); System.out.println("After partitioning array from index"+(lb+1)+" to "+(ub+1)+":"); display(x); quickSort(x,lb,j-1); quickSort(x,j+1,ub); } public static int partition(int x[], int lb, int ub){ int a, down, temp, up; a=x[lb]; up=ub; down=lb; while(down<up){ while(x[down]<=a && down<up) down++; while(x[up]>a) up--; if(down<up){ temp=x[down]; x[down]=x[up]; x[up]=temp; } } x[lb]=x[up]; x[up]=a; return up; } public static void display(int x[]){ for(int i=0; i<x.length; i++) System.out.print(x+""); System.out.println("\n"); } } Link to comment Share on other sites More sharing options...
gate13 Posted February 23, 2015 Author Share Posted February 23, 2015 well i gave an example, what part of my question you don't understand...? Link to comment Share on other sites More sharing options...
fiveworlds Posted February 23, 2015 Share Posted February 23, 2015 I have a small sequence of 4 elements that i need to apply the median of three partitioning quick sort algorithm I know how to do it with long sequences but here is my problem. the sequence is { 7, 17, 15, 19} the pivot is 15 There is little point with such a small sequence in fact it is the worst way of ordering them for instance 7,17|15,19 - two partition splits the numbers into two distinct groups then sorts those groups 7|17|15,19 - three partition splits the numbers into three distinct groups But for such a small set why not just sort the numbers?? Link to comment Share on other sites More sharing options...
gate13 Posted February 23, 2015 Author Share Posted February 23, 2015 thank you for your answer actually the sequence was very large these 4 elements is what is left.. i have a cutoff of three (so 3 or less items will not use the method) But this last sequence of 4 elements gives me so many problems because i don't know where the i starts and where the j starts after moving the pivot 15 to the second to the last position bit fiveworlds, I think you answered my question and this how i processed it... Thank you... Link to comment Share on other sites More sharing options...
fiveworlds Posted February 23, 2015 Share Posted February 23, 2015 (edited) I am making this too easy for you <script> var a = [7,17]; var b = [15,9,10,12,17]; function quicksort(arr) { if (arr.length == 0) return []; var left = new Array(); var right = new Array(); var pivot = arr[0]; for (var i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quicksort(left).concat(pivot, quicksort(right)); } var d=quicksort(b); var e=a.concat(d); document.write(quicksort(e)); </script> <p id="demo"></p> Edited February 23, 2015 by fiveworlds Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now