Здравствуйте!
Возникла ошибка при рекурсивном вызове быстрой сортировки для частей массива, на этом примере. В последней итераций, массив еще не отсортирован, и не получается определить новые границы, так как ни одно из условий if(j>first), quicksort(first,j), if(i<last), quicksort(i,last) не выполнилось.
0 1 2 3 4 5 6 7 8 9 10 11
5|2|6|-78|45|/11/|0|7|2|1|1|1
Найдем позицию пивота по формуле (начальный индекс массива + конечный индекс массива)/2, берем целую часть. (0+11)/2=5, пивот равен 11 (M[pivotindex]).
Начинаем двигать указатели i(левый указатель, начинается от 0, j правый указатель, начинается от M.Length-1). Двигаем левый укзатель до тех пор, пока не будет найден элемент >= пивота. В данном случае это 45. Теперь начнем двигать правый указатель, пока не будет найден элемент <= пивота. В данном случае это 1. Далее, если i<=j меняем найденные значения, даже если любой из указателей будет указывать на позицию (индекс) пивота, пивот не поменяет значение, но будет иметь новый индекс. После этого увеличиваем i на 1, j уменьшаем на 1. Повторяем шаги. Если условие i<=j не выполняется, процедура деления не выполняется и таким образом элементы от пивота до границы first меньше пивота, элементы от пивота до границы last, больше пивота. Изначально first=0, last=M.length-1.
Продолжим пример:
0 1 2 3 4 5 6 7 8 9 10 11
5|2|6|-78|45|/11/|0|7|2|1|1|1
i j
4<11 (45>=11,1<=11) i<j, меняем элементы
0 1 2 3 4 5 6 7 8 9 10 11
5|2|6|-78|1|/11/|0|7|2|1|1|45
i j
5<10 (11>=11,1<=1) i<j, меняем элементы
0 1 2 3 4 5 6 7 8 9 10 11
5|2|6|-78|1|1|0|7|2|1|/11/|45
j i
10>9 (1<=11,11>=11) i>j, процедура деления завершена
Так как мы видим, что массив еще не отсортирован надо вызвать функцию деления еще раз, но как я понял если в левой или правой части есть более 2 элементов, то нужно вызвать процедуру деления именно для этой части.
По правилу if(j>first) quicksort(first,j), где first это first, то есть начальная граница массива и j крайняя граница массива.
if(i<last) quicksort(i,last), где i это first,, то есть начальная граница массива и last это last крайняя граница массива
Продолжим пример.
Последние значения i,j,first,last на которых мы закончили делить массив это
i=10, j=9, first=0, last=9.
9>0 условие верно, от 0 до 9 болбше одного элемента, а справа только один элемент(45)
10<9 условие неверно, по-этому вызваем функцию деления со значениями quicksort(0,9).
0 1 2 3 4 5 6 7 8 9 10 11
5|2|6|-78|/1/|1|0|7|2|1|11|45
i j
пивот 1, позиция пивота 4. Помним что границы от 0 до 9.
5>=1, 1<=1, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
1|2|6|-78|/1/|1|0|7|2|5|11|45
i j
2>=1, 0<=1, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
1|0|6|-78|/1/|1|2|7|2|5|11|45
i j
6>=1, 1<=1, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
1|0|1|-78|/1/|6|2|7|2|5|11|45
ij
1>=1, 1<=1, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
1|0|1|-78|/1/|6|2|7|2|5|11|45
j i
6>=1, -78<=1, i=5, j=3 i>j, процедура деления завершена, необходимо выбрать ноаые границы и запустить сортировку заново, так как массив еще не отсортирован.
i=5, j=3, first=0, last=9
3>0 верно
5<9 верно
Видно что слева от пивота и справа от пивота больше 2 элементов. Так как сперва в коде написано if(j>first), quicksort(first,j), то условие if(i<last), quicksort(i,last) не воплнится, так как после входа в if(j>first) запустится quicksort(first,j).
Продолжим деление.
Новые значения границ first=0, last=3
0 1 2 3 4 5 6 7 8 9 10 11
1|/0/|1|-78|1|6|2|7|2|5|11|45
i j
пивот 0, позиция пивота 1
1>=0, -78<=0, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
-78|/0/|1|1|1|6|2|7|2|5|11|45
ij
0>=0, 0<=0, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
-78|/0/|1|1|1|6|2|7|2|5|11|45
j i
1>=0, -78<=0, i=2, j=0, i>j процедура деления завершена
Найдем новые границы и запустим деление дальше.
0>0 неверно
2<3 верно
Новые границы first=2, last=3
пивот 1, позиция пивота 2
0 1 2 3 4 5 6 7 8 9 10 11
-78|0|/1/|1|1|6|2|7|2|5|11|45
i j
1>=1, 1<=1, меняем позиции
0 1 2 3 4 5 6 7 8 9 10 11
-78|0|1|/1/|1|6|2|7|2|5|11|45
j i
i=3, j=2 i>j процедура деления завершена
найдем новые границы
2>2 неверно
3<3 неверно
Вот здесь у меня возникла ошибка, казалось бы если не выполнилось ни одно из условий
if(j>first), quicksort(first,j), if(i<last), quicksort(i,last), то сортировка звершена, но видно, что массив еще не отсортирован. Вроде следовал описанию Алгоритма Быстрой сортировки, но на этом шаге не получилось выбрать новые границы. Пожалуйста, подскажите, в чем моя ошибка. Заранее вам спасибо!
