Быстрая сортировка. Пара моментов

Привет. Сорри,что по пустякам,но нужно кое-что уточнить, по быстрой сортирвке.
Почему уменьшаются правое и левое,во втором и третьем цикле-еще понятно,но почему в if одновременно уменьшается левое и правое?(гонял по дебагеру,но это пока не приблизило меня к пониманию.) Подскажите.

0

Сообщение от Павел133 но почему в if одновременно уменьшается левое и правое?

- потому, что когда найдена пара элементов, стоящая в неверном порядке, их нужно поменять местами и искать пары элементов, стоящих в неверном порядке и расположенных между только что найденными.

0

Вообще,конечно,головоломка этот код ,та еще)
Можете рассказать,почему так? Почему цикл,например,котрый отвечает за левое значение,проходит по массиву только два элемента, останавливается и выходит, на значении arr[leftindex] = 2, pivot = 5? Ведь условия цикла выполняются. 5<6,но он выскакивает именно на этом значении,а не идет дальше. Why?

Миниатюры

 

0

Сообщение от Павел133 Ведь условия цикла выполняются

arr[2]=5, arr[2]<5 ????

0

Два меньше пяти же,правильно.)Тогда почему цикл прерывается на этом?

0

leftIndex=2, а пять не меньше пяти

0

То есть,берется значение 5,из массива под индексом 2,и сравнивается с пивот=5? Получается 5=5?Порой,просто путаешь значение массива и индекс. В голове каша)

0

Сообщение от Павел133 Порой,просто путаешь значение массива и индекс

Возьмите массив букв. Работает точно так же, а спутать индекс с содержимым нельзя.

Сообщение от Павел133 В голове каша)

Если у вас абстрактное мышление прихрамывает, то попробуйте зрительные образы. Сначала на бумаге рисуйте массив в виде кучи клеточек со значениями внутри и индексами снаружи. Потом можно будет мысленно рисовать.

0

Павел133, Хоар боль. Проще схема через 3 указателя.

0

Arsegg, да я все виды сортирвоки стараюсь проработать дебагом,чтобы понимание появилось,о работе циклов,массивов итд,но это самая хардовая.)

Добавлено через 13 минут
Ewlampiy, массив чар сделать?)

0

Сообщение от Павел133 я все виды сортирвоки стараюсь проработать дебагом,чтобы понимание появилось,о работе циклов,массивов итд

Это очень плохая идея - не зная заранее сам алгоритм пытаться понять его по реализации на каком то языке. Даже человеку с огромным опытом бывает крайне сложно понять алгоритм по исходнику.

Вот когда вы уже знаете алгоритм и у вас в голове крутятся идеи а как бы его реализовать - тогда вы уже можете посмотреть как он реализован на конкретном примере с целью разобраться уже не с алгоритмом, а приемами программирования на конкретном языке.

Допустим вам нужно взять большую книгу с текстом и отсортировать все буквы в ней. То есть получить одну длинную строку начинающуюся c "АААААААА....", которые потом где то дальше сменяются на "АААААБББББББ..." и так далее. Для этого идеально подходит алгоритм сортировки пересчетом - нужно просто за первый проход пересчитать сколько раз встречается каждая буква в книге, а на втором проходе (уже не заглядывая в книгу) просто используя полученные числа количества букв "А встречается 817 раз, Б встречается 312 раз, В встречается..." cгенерить требуемую строку, вписав в нее нужное количество "А" и так далее. Вот теперь, ПОСЛЕ того как алгоритм сортировки пересчетом вы узнали, вы уже свободно сможете прочитать исходник, который его реализует, поймете что делает каждый из циклов. А ДО этого вы просто будете сидеть и два часа недоумевать "а чего это за уличная магия counts[str[i]]++, зачем это все нужно, почему это так а не иначе".

0

Почему не знаю,я много теории изучал,перед тем,как анализировать алгоритм в иде)Вот этот код,кстати, я взял из видеоролика,предварительно его посмотрев(Не все поняв,естественно).

0

Откуда тогда возник вопрос зачем в цикле сначала перемещается левый индекс, потом аналогично правый?

Если вы этот алгоритм предварительно действительно изучили и теперь словами попытаетесь его пересказать, то у вас эти циклы сразу же в явном виде и возникнут в рассказе "до тех пор пока элемент слева меньше выбранного..."

0

Изучал,не занчит понял до конца,вот в чем дело.

0

Изучить - это возможность воспроизвести вручную без всяких компьютеров на бумажке или на детских кубиках с буквами.

Вот у вас в ряд составлены кубики с буквами. Вы выбираете первый попавшийся из них и запоминаете что на нем написано, сам кубик не трогаете и оставляете на месте. В идеале нужно бы взять медианное значение, но если у вас нет никакой дополнительной информации о статистике распределения значений по кубиках, то просто любое. В коде берется из центра, но это совершенно не обязательно.

Теперь вам нужно поделить кубики на две кучки. В левой кучке должны остаться все кубики с буквами меньше выбранной, а в правой больше выбранной. (Интересный призовой вопрос куда деть кубики с буквами равной выбранной)

Повторить над каждой каждой из кучек предыдущие два шага

0

Они уберутся?)(Не знаю,если честно)

0

Вы про кубики равные выбранному?

Можно сложить все влево, но тогда правая кучка может оказаться пустой и алгоритм зациклится. Аналогично если сложить их все вправо. То есть так делать нельзя

Можно положить их все в ту кучку которая оказалась меньше размером, тогда точно ни одна не окажется пустой.

Можно их вообще никуда не складывать, а оставить в третьей "центральной" кучке которая вообще из дальнейшей обработки выкидывается потому-что уже лежит "там где надо". В этом случае левая или правая опять могут оказаться пустыми, но зацикливания это не вызовет.

Ну а в данном конкретном коде просто делается такой трюк, чтобы эти кубики, равные выбранному, раскидались рандомно и в ту и в другую кучку НО таким образом что ни одна не могла бы оказаться пустой.

2