Ребята, помогите, объясните в чем ошибка.

Пытаюсь реализовать метод быстрой сортировки.



Пример: имеем массив:
7 3 9 2 10 4 8 1 5 6

Для наглядности: 
число x выделено жирным
числа, которые надо поменять местами подчеркнуты
числа после перемены курсивом

выбираем в качестве x   4:
7 3 9 2 10 4 8 1 5 6
Находим слева 7  справа  1
7 3 9 2 10 4 8 1 5 6
Меняем их местами:
1 3 9 2 10 4 8 7 5 6
далее: справа нет чисел, меньше 4, значит двигаем саму 4
1 3 9 2 10 4 8 7 5 6

Разбиваем на 2 массива:
1 3 4 2 10 9
8 7 5 6

Начнем работать со вторым:
8 7 5 6

получаем 2 массива
5 7 8
6

В итоге получается, что 6 стоит после 8 и 7

Почему так получается, подскажите где ошибка в алгоритме.

Для этого выбирается для сравнения один элемент X  (опорный элемент), отыскивается слева первый элемент, который не меньше X, а справа - первый элемент, который не больше X. Найденные элементы меняются местами. Далее процесс продолжается, пока не пройден весь массив. 
После первого же прохода все элементы, которые меньше X, будут стоять слева от X, а все элементы, которые больше X, - справа от X. Далее сортируем левую и правую половину рекурсивно.
7 3 9 2 10 -4 8 1 5 6
1 3 9 2 10 -4 8 7 5 6 
но 4 не должна сдвигаться... 


есть исходник этой сортировки на Pascal'е, если нужно

А если не двигать 4, то получается, что слева от нее стоят 9 и 10.

можно представить массив в виде 3-х частей:
--- все числа меньше x
--- всякие числа (т.е. какие-то больше, какие-то меньше)
--- все числа больше или равны x
наша задача - расширять две крайние области, чтобы средняя пропала

для начала смотрим, что за число стоит сразу после первой области, если оно меньше x, то можно смело удлинить первую область на 1

потом - на число сразу перед третьей областью, если оно больше или равно - аналогично

если же ни то, ни другое не верно, то просто меняем эти элементы местами и получается, что можно удлинить обе области

пример:
(жирным показаны первая и третья области)
7 3 9 2 10 4 8 1 5 6 (x=4)
7 3 9 2 10 4 8 1 5 6 (заметили, что 6-ка стоит в правильной части)
7 3 9 2 10 4 8 1 5 6 (5-ка тоже)
1 3 9 2 10 4 8 7 5 6 (и 7, и 1 выбиваются, значит меняем, и они переходят в свои части)
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6 (т.к. 4>=x)
1 3 9 2 10 4 6 7 5 6
1 3 2 9 10 4 6 7 5 6
1 3 2 9 10 4 6 7 5 6



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

Это сообщение отредактировал(а) maxim1000 - 6.1.2007, 22:14

Всем спасибо я разобрался.

Опишу результат, может кому пригодится...

Ошибки:
1. Раньше я разбивал массив как только опрный элемент менял свое положение.
2. Разбивал массив я (как верно подметил maxim1000) по индексу, а надо было по значению.

Вернемся к моему примеру:

7 3 9 2 10 4 8 1 5 6

1 3 9 2 10 4 8 7 5 6

1 3 4 2 10 9 8 7 5 6

1 3 2 4 10 9 8 7 5 6    --- теперь все нормально, все числа меньше 4 слева, больше - справа

Разбиваем относительно 4 на 2 массива:

1 3 2

и

10 9 8 7 5 6

С каждым из них повторяем то же самое. 
Начнем со второго:

10 9 8 7 5 6
6 9 8 7 5 10
6 5 8 7 9 10
6 5 7 8 9 10

Опять разбиваем на 2 части:
6 5
и
8 9 10

Первую часть мы уже не трогаем, т.к. там всего 2 элемента.
Разбираемся со второй:
8 9 10
Все нормально, поэтому разбиваем на 2 части
8 
и
10
Т.к. в них меньше 3-х элементов,  то больше их не трогаем.

Остался один неразобранный массив:

1 3 2
1 2 3

Получаем :
1 2

Все, сортировка окончена.