Median-3 quick sort in java

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

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);
    }
}
+4
source share

No one has answered this question yet.


All Articles