Median-of-3 quick sort in java

Viewed 1408

I have a task in the university where I need to sort student by their groupnumbers using Median-of-3 quick sort. But my sorting methods are not working properly - only some of the elements are sorted. But a few elements do not change their positions. I have created a Student class with necessary data, Sortings class with Student type array. And I have 4 static methods for this type of sorting in main class, where I create an instance of Sortings and call my static methods for sorting.

public static void manual_Sort(Student[]st, int right, int left)
{
    int size = right - left + 1;
    if(size <= 1)
        return;             
    if(size == 2)
    {
        if(st[left].Group_number > st[right].Group_number)
            swap(st,right,left);
        return;
    }
    else
    {
        if(st[left].Group_number > st[right-1].Group_number)
            swap(st,left, right-1);                                 
        if(st[left].Group_number > st[right].Group_number)
            swap(st,left, right);                                       
        if(st[right-1].Group_number > st[right].Group_number )
            swap(st,right-1, right);                                
    }
}


public static int partitionIt(Student[]st, int left, int right,double pivot)
{
    int leftPtr = left;                 
    int rightPtr = right - 1;       

    while(true)
    {
        while(st[++leftPtr].Group_number < pivot)       
            ;
        while(st[--rightPtr].Group_number > pivot)      
            ;
        if(leftPtr >= rightPtr)         
            break;
        else
            swap(st,leftPtr, rightPtr); 
    }
    swap(st,leftPtr, right-1);              
    return leftPtr;                     
}

public static int median_OfThree(Student[]st, int left, int right)
{
    int center = (left + right)/2;

    if(st[left].Group_number > st[center].Group_number )
        swap(st,left, center);
    if(st[left].Group_number > st[right].Group_number )
        swap(st,left, right);
    if(st[center].Group_number > st[right].Group_number )
        swap(st,center, right);

    swap(st,center, right-1);                   
    return st[right-1].Group_number;                        
}

public static void quick_Sort(Student[] st)
{
    rec_quickSort(st, 0, st.length-1);
}

public static void rec_quickSort(Student[]st, int left, int right)
{
    int size_ = right - left + 1;

    if(size_ <= 3)
        manual_Sort(st, left, right);
    else
    {
        double median = median_OfThree(st, left, right);
        int partition = partitionIt(st, left, right, median);
        rec_quickSort(st, left, partition - 1);
        rec_quickSort(st, partition + 1, right);
    }
}
0 Answers
Related