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