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