6 Replies - 320 Views - Last Post: 20 May 2014 - 04:13 AM Rate Topic: -----

#1 google_interview  Icon User is offline

  • New D.I.C Head

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

Quicksort Implementation with median pivot

Posted 19 May 2014 - 05:18 AM

Attached File  100.txt (390bytes)
Number of downloads: 11Hello everyone! :sorcerer:/>

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? :helpsmilie:/>



import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
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");
				BufferedReader br = new BufferedReader(new InputStreamReader(fstream));
				ArrayList<Integer> intList = new ArrayList<Integer>();
				String line;
				
				
				// read and store numbers from file into array
				while ((line = br.readLine()) != null)
				{
					intList.add(Integer.parseInt(line));
				}
				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)
		{
			add(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

#2 google_interview  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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;
        
    }

Was This Post Helpful? 0
  • +
  • -

#3 ForteGS  Icon User is offline

  • New D.I.C Head

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

Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 09:12 AM

View Postgoogle_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.
Was This Post Helpful? 0
  • +
  • -

#4 google_interview  Icon User is offline

  • New D.I.C Head

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

Re: Quicksort Implementation with median pivot

Posted 19 May 2014 - 09:16 AM

View PostForteGS, 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! :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#5 google_interview  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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. :nottalkingtoyou:

My output: 651
Correct answer: 518

	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;
	}

Was This Post Helpful? 0
  • +
  • -

#6 ForteGS  Icon User is offline

  • New D.I.C Head

Reputation: 6
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#7 google_interview  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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;
	}

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1