quick sort algorithm and median of three partitioning

[gate13]

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.

 

[Sensei]

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

[fiveworlds]

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");

}

}

[gate13]

well i gave an example,

what part of my question you don't understand...?

[fiveworlds]

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??

[gate13]

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...

[fiveworlds]

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