I need help with modifying my quicksort code. It has to paritition using the mid

Question

I need help with modifying my quicksort code. It has to paritition using the middle of three techinque in Java. I written the quicksort code but I'm having trouble with the technique. I would appreciate any help.

import java.util.*;

public class QuickSort
{
    public static void main(String[] args)
    {
        Integer[] arr = new Integer[] { 1, 3, 5, 7, 11, 2, 8, 24, 6, 99, 32, 4};

       System.out.println("Unsorted: ");
        System.out.println(Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);

       System.out.print(' ');

       System.out.println("Sorted: ");
        System.out.println(Arrays.toString(arr));
    }

    public static <T extends Comparable <T>> void sort(T[] a, int p, int r)
    {
        if(p < r)
        {
            int q = partition(a, p, r);
            sort(a, p, q);
            sort(a, q + 1, r);
        }
    }

    public static <T extends Comparable <T>> T median(T[] a, int p, int r)
    {
        int q = (r+p)/ 2;

        if (a[p].compareTo(a[q]) > 0)
        {
            if (a[q].compareTo(a[r]) > 0)
            {
                return a[q];
            }
            else if (a[p].compareTo(a[r]) > 0)
            {
                return a[r];
            }
            else
            {
                return a[p];
            }
        }

        else
        {
            if(a[p].compareTo(a[r]) > 0)
            {
                return a[r];
            }
            else
            {
                return a[q];
            }
        }
    }

    public static <T extends Comparable<T>> int partition(T[] a, int p, int r)
    {
        T pivot = median(a,p,r);
       int i = p-1;
       int j = r+1;

       while(true)
       {
           do
           {
               i++;
           }

           while(i<=r && a[i].compareTo(pivot) < 0);
           do
           {
               j--;
           }

           while(j>=p && a[j].compareTo(pivot) > 0);

           if(i<j)
           {
               swap(a,i,j);
           }
           else
           {
               return j;
           }
       }
   }

    public static <T extends Comparable<T>> void swap(T[] a, int i, int j)
    {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Explanation / Answer

The above program is quite good for compiling.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.