CODEWITHSUNDEEP
javasortingmedian
unknow person
unknow person

Reputation: 1

Choosing the median as the pivot

I am trying to select the median as the pivot in this app but seems like I am doing something wrong. Any help will be greatly appreciated.

I get the first few numbers in order and then towards the end. 

    public class QuickSort {

    public static void main(String[] args) {
    int [] list = {1,3,2,4,6,5,8,7,9,0};
    quickSort (list);

    for (int i=0; i < list.length; i++)
        System.out.print(list[i] + " ");
}
public static void quickSort(int [] list)
{
    quickSort(list, 0, list.length - 1);
}

public static void quickSort (int[] list, int first, int last)
{
    int size = last - first + 1;
    if (size > 3){
        int median1 = median(list, first, last);
        int partition1 = partition(list, first, last, median1);
        quickSort(list, first, partition1 - 1);
        quickSort(list, partition1 + 1, last);
    }
}
    public static int median(int [] list, int first1, int last1){
        int middle = (first1 + last1)/2;
        if (list[first1] > list[middle])
            swap(list, first1, middle);
        if (list[first1] > list[last1])
            swap(list, first1, last1);
        if (list[middle] > list[last1])
            swap(list, middle, last1);
        swap(list, middle, last1 - 1);
        return list[last1 - 1 ];
    }
    public static int partition(int [] list, int left, int right, long pivot) {
        int leftPtr = left;
        int rightPtr = right - 1; 

        while (true) {
          while (list[++leftPtr] < pivot);

          while (list[--rightPtr] > pivot);
          if (leftPtr >= rightPtr) 
            break;
          else
            swap(list, leftPtr, rightPtr); 
        }
        swap(list, leftPtr, right - 1);
        return leftPtr; 
    }
       public static void swap(int []list, int dex1, int dex2) {
         int temp = list[dex1];
         list[dex1] = list[dex2];
          list[dex2] = temp;
            }

I get some numbers in order, but not all of them.

Upvotes: 0

Views: 945

Answers (1)

Grothaar
Grothaar

Reputation: 206

There are usually two approaches you can use to computer programming. You can either a) Take something that works and start removing/changing stuff until you get what you like. or b) Take the smallest case you can -- make it work -- and then keep on adding more complexicity. In this case I suggest b) (FYI b) is usuall the best approach)

If you start with int[] list = { 3, 1, }, you can see that your list doesn't get sorted correctly. This is because your quickSort function is only sorting lists of size greater than 3. In your case this condition should probably be "size > 1" -- though there may be some more things you need to do in order to get things working.

There's lot of info about QuickSort on wikipedia: http://en.wikipedia.org/wiki/Quicksort

Upvotes: 1

Related Questions