Мы должны сделать оптимизированную быструю сортировку для нашего собственного базового класса Comparable.За свою жизнь я не могу заставить это работать.Алгоритм кажется прямым, но я не вижу, чтобы мой код работал.У меня есть класс DateTime, который расширяет Comparable, который я использую для тестирования, и сортировка, кажется, работает, но один из каждых 20 или около того запускает одно значение неуместно, и когда я использую сортировку вставкой на куски массива, которые меньшечем 8, весь вид теряется.
В моем методе разбиения это работает, когда я перемещаю шарнир до конца и запускаю указатели в начале и в конце - 1. Я хочу переместитьpivot to end - 1, потому что первый и последний уже отсортированы и запускают указатели с первого + 1 и с конца -2, но, если я пытаюсь это сделать, все разваливается, и я не понимаю, почему.
Итак, у меня естьто, что работает сейчас.Это становится немного спастическим, когда я не использую сортировку вставки на меньших подмассивах, что надоедает, но я в конце концов не пойму это.Спасибо Бен j за то, что он указал на выпадение из массива ... это вызвало проблему сортировки вставкой.:)
Мой текущий код ниже
Comparable** partition(Comparable** from, Comparable** to)
{
Comparable** pivot = from + (to - from) / 2;
SortFirstMiddleLast(from, pivot, to - 1);
swap(*pivot, *to);
pivot = to;
++from; to -= 2;
while (from <= to)
{
while (**from <= **pivot && from <= to) ++from;
while (**to >= **pivot && from <= to) --to;
if (from < to)
{
swap(*from, *to);
++from; --to;
}
}
swap(*from, *pivot);
return from;
}