# Quicksort Implementation with median pivot

Page 1 of 1

## 6 Replies - 587 Views - Last Post: 20 May 2014 - 04:13 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=347195&amp;s=2e157920c9174ee22d3a68017e3142b0&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

• New D.I.C Head

Reputation: 1
• Posts: 49
• Joined: 27-December 13

# Quicksort Implementation with median pivot

Posted 19 May 2014 - 05:18 AM

100.txt (390bytes)

I am currently writing the Quick Sort implementation where the pivot is chosen to be the medianOf3 element in the sub array. The program should output the total number of comparisons (excluding the ones needed to compute the median itself).

I cannot spot any mistake anywhere - yet I am getting the wrong output in the end.

Input file (100.txt) attached.
Current output: 513. Correct output: 518. Where are the missing 5 comparisons? />

```
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;

import org.apache.commons.lang3.ArrayUtils;

public class MedianElementAsPivot	{

static long noOfComparisons;

public static void main(String args[]) throws IOException
{

// Open the file
FileInputStream fstream;

try {

fstream = new FileInputStream("100.txt");
ArrayList<Integer> intList = new ArrayList<Integer>();
String line;

// read and store numbers from file into array
while ((line = br.readLine()) != null)
{
}
br.close();
int[] A = ArrayUtils.toPrimitive(intList.toArray(new Integer[intList.size()]));

// count comparisons and print output
QuickSort(A, 0, A.length-1);
System.out.println("Total number of comparisons (median pivot): " + noOfComparisons);

} catch (FileNotFoundException e) {
e.printStackTrace();
}

}

private static void QuickSort(int[] a, int l, int r)
{

int pivot;
if (r > l)
{
pivot = Partition(a, l, r);

QuickSort(a, l, pivot-1);
QuickSort(a, pivot+1, r);
}

}

private static void add(int i) {
noOfComparisons += i;
}

private static int Partition(int[] a, int l, int r)
{

// swap median and first before getting started
int median = medianOf3(a, l, r);
Swap(a, l, median);

int p = a[l];
int i = l+1;

for (int j = l+1; j <= r; j++)
{
if (a[j] < p)
{
Swap(a, j, i);
i++;
}
}

Swap(a, l, i-1);
return (i-1);

}

private static void Swap(int[] a, int i, int j)
{

int temp = a[j];
a[j] = a[i];
a[i] = temp;

}

private static int medianOf3(int[] a, int low, int high)
{

// define default median
int middleElement = (int) Math.floor((low+high)/2);
int median = middleElement;

// ensure correct order
if (a[low] > a[high])
{
int tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}

// anomaly cases
if (a[middleElement] > a[high])	median = high;
else if (a[middleElement] < a[low])	median = low;

// else (everything okay!): a[low] < a[middleElement] < a[high]
return median;

}

}

```

Is This A Good Question/Topic? 0

## Replies To: Quicksort Implementation with median pivot

• New D.I.C Head

Reputation: 1
• Posts: 49
• Joined: 27-December 13

## Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 07:09 AM

Okay - I rewrote medianOf3 now because I had the impression that swapping elements was having a global effect (how is that even possible - aren't function arguments supposed to have local scope??)

And now I am getting the following output: 544.
I don't understand what is wrong here!!

```    private static int medianOf3(int[] a, int low, int high)
{

// define default median
int middleElement = (int) Math.floor((low+high)/2);
int median = middleElement;
int top = a[high], bottom = a[low], tmp;

// bring top and botton in correct order
if (top < bottom)
{
tmp =  top;
top = bottom;
bottom = tmp;
}

// anomaly cases (when median NOT in the middle)
if (a[middleElement] > top)	median = high;
else if (a[middleElement] < bottom)	median = low;

// else (everything okay!): a[low] < a[middleElement] < a[high]
return median;

}
```

### #3 ForteGS

• New D.I.C Head

Reputation: 6
• Posts: 21
• Joined: 06-January 14

## Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 09:12 AM

google_interview, on 19 May 2014 - 07:09 AM, said:

Okay - I rewrote medianOf3 now because I had the impression that swapping elements was having a global effect (how is that even possible - aren't function arguments supposed to have local scope??)

And now I am getting the following output: 544.
I don't understand what is wrong here!!

```    private static int medianOf3(int[] a, int low, int high)
{

// define default median
int middleElement = (int) Math.floor((low+high)/2);
int median = middleElement;
int top = a[high], bottom = a[low], tmp;

// bring top and botton in correct order
if (top < bottom)
{
tmp =  top;
top = bottom;
bottom = tmp;
}

// anomaly cases (when median NOT in the middle)
if (a[middleElement] > top)	median = high;
else if (a[middleElement] < bottom)	median = low;

// else (everything okay!): a[low] < a[middleElement] < a[high]
return median;

}
```

"Okay - I rewrote medianOf3 now because I had the impression that swapping elements was having a global effect (how is that even possible - aren't function arguments supposed to have local scope??)"

Because array is a reference type.

• New D.I.C Head

Reputation: 1
• Posts: 49
• Joined: 27-December 13

## Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 09:16 AM

ForteGS, on 19 May 2014 - 09:12 AM, said:

"Okay - I rewrote medianOf3 now because I had the impression that swapping elements was having a global effect (how is that even possible - aren't function arguments supposed to have local scope??)"

Because array is a reference type.

Got a confirmation here !

Thanks for the hint!

• New D.I.C Head

Reputation: 1
• Posts: 49
• Joined: 27-December 13

## Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 10:34 AM

I have just rewritten the medianOf3 function. The programming logic makes sense now.
Yet - I am getting the wrong answer.

My output: 651

```	private static int findMedianOf3(int[] array, int leftIndex, int rightIndex) {

int t, medianIndex = (int) Math.floor((leftIndex + rightIndex)/2);

// ensure correct order of values
if (array[rightIndex] > array[leftIndex])
{
t = leftIndex;
leftIndex = rightIndex;
rightIndex = t;
}

if (array[medianIndex] > array[rightIndex])	medianIndex = rightIndex;
else if (array[medianIndex] < array[leftIndex])	medianIndex = leftIndex;

return medianIndex;
}
```

### #6 ForteGS

• New D.I.C Head

Reputation: 6
• Posts: 21
• Joined: 06-January 14

## Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 01:34 PM

You are using recursion here. Something is wrong with the QuickSort method, especially the value of adding to noOfComparisons.
Moreover, try with small input and try to see if the array is actually sort or not.
Can you figure that out?

• New D.I.C Head

Reputation: 1
• Posts: 49
• Joined: 27-December 13

## Re: Quicksort Implementation with median pivot

Posted 20 May 2014 - 04:13 AM

Damn!
I finally figured it out!
There was a silly silly mistake in the medianOf3() function!!

The very first if-loop takes care of having the the higher value on the top and the lower value on the bottom, so the correct condition would be if (array[rightIndex] < array[leftIndex]) instead of if (array[rightIndex] > array[leftIndex]) (error from before!).

If anyone has any further questions on the code - feel free to ask. Rest is all fine. I've experimented with test cases and they all gave correct results!

```	private static int findMedianOf3(int[] array, int leftIndex, int rightIndex) {

int t, medianIndex = (int) Math.floor((leftIndex + rightIndex)/2);

// ensure correct order of values
if (array[rightIndex] < array[leftIndex])
{
t = leftIndex;
leftIndex = rightIndex;
rightIndex = t;
}

if (array[medianIndex] > array[rightIndex])	medianIndex = rightIndex;
else if (array[medianIndex] < array[leftIndex])	medianIndex = leftIndex;

return medianIndex;
}
```