0

Добрый день!

Ничего не могу поять. Я уже делал быструю сортировку на джаве, сейчас читаю Вирта, попробовал ТОЧЬ-В-ТОЧЬ реализовать его алгоритм (такой же, кстати, и на википедии), и у меня ничего не получается на этапе разделения массива на 2 подмассива. Набор чисел такой, например: 6 39 5 33 9 18 40 42 49 23

Алгоритм (взято с вики):

введите код здесь

procedure sort(var ar: array of real; low, high: integer);

  var i, j: integer;

      m, wsp: real;

  begin

      i:=low; //начальный индекс для итерации, 0 в нашем случае

 j:=high; //конечный индекс, 9 в нашем случае

m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента, в нашем случае это 9, индекс - 4
      repeat
        while ar[i]<m do Inc(i);    //увеличиваем начальный итератор, прекратится while когда индекс будет 1 (значение 39)
        while ar[j]>m do Dec(j);    //уменьшаем конечный итератор, получаем индекс опорного элемента 4 (значение 9)
        if i<=j then begin //условие соблюдено, далее -
          wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp; //меняем их местами, массив теперь выглядит так: 6 9 5 33 39 18 40 42 49 23,
          Inc(i); Dec(j); // а индексы 2 и 3 соответственно
         end;
      until i>j;
 /// условие соблюдено, идем на следующий шаг внешнего цикла - 
//while ar[i]<m do Inc(i); - увеличиваем начальный итератор до индекса 3 (значение 33)
//while ar[j]>m do Dec(j); уменьшаем конечный индекс до 2 (значение 5)
// if i<=j -все, условие не выполнено, конец
//В результате мы получили массив 6 9 5 33 39 18 40 42 49 23, в котором нет никакого смысла - и слева, и справа от 9 есть элементы со значением ниже
//Если смотреть относительно конечных индексов и начального индекса опорной точки - то же самое.

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

9
  • 2
    > ничего не получается на этапе разделения массива на 2 подмассива Объясните подробнее, что именно значит «не получается». Считайте нас коллективным котом.
    – VladD
    26 июн 2014 в 9:57
  • Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом — «меньшие опорного», «равные» и «большие». [1] массив обычно делят не на три, а на две части, например, «меньшие опорного» и «равные и большие». Так вот, где здесь получилось разбиение на 2 массива,в первом из которых все значения меньше 9, а во втором, больше или равны например? 26 июн 2014 в 10:05
  • @Awe4k: Угу, так и есть. Одна часть — те, которые меньше строго, другая — те, которые больше или равны. Но разбить так массив не перемещая элементов нельзя. Те, которые меньше 9, «соскальзывают» влево, а остальные — вправо. То есть представьте, что вы удалили из массива все элементы, которые >= 9. В массиве образовались «дыры», и вы уплотнили его влево. Потом то же для остальных элементов. Вот только эта операция проводится без фактического удаления, «на месте». Есть?
    – VladD
    26 июн 2014 в 11:10
  • 1
    Да, сам алгоритм мне понятен, у меня вопрос собственно по реализации - код, который я привел с википедии, работает не так как быть должно, отсюда и вопрос - либо я что-то не так понимаю в этом коде, либо там ошибка (что маловероятно, т.к. алгоритм "слизан" из книги Вирта полностью) 26 июн 2014 в 12:53
  • @Awe4k: Снова, а что значит «не работает как должно»? Какая именно операция приводит не к тому результату, который вы ожидаете?
    – VladD
    26 июн 2014 в 13:19

1 ответ 1

2

//В результате мы получили массив 6 9 5 33 39 18 40 42 49 23, в котором нет никакого смысла - и слева, и справа от 9 есть элементы со значением ниже

//Если смотреть относительно конечных индексов и начального индекса опорной точки - то же самое.

Вы получили массив где с 0(low) по 2(j), лежат числа меньше либо равны опорному числу 9, а справа с 3(i) по 9(high) лежат больше либо равны опорного числа 9. Теперь мы можем вызвать снова эту функцию для куска (low,j) это отсортирует числа 6 9 5 и для куска (i, high) и отсортируем вот эти числа 33 39 18 40 42 49 23. Т.е. мы не пытались отсортировать массив относительно опорного элемента, мы всего лишь пытались разбить отрезок (low,high) на два отрезка (low,j) и (i,high) так чтобы все элементы из первого отрезка были меньше либо равны элементов из правого отрезка, и теперь эти два отрезка можно сортировать дальше уже независимо друг от друга, тем же методом, пока все отрезки не превратятся в один элемент.

2
  • Вот спасибо, теперь понятно, я как раз делал именно по опорному числу когда-то, вот и не понял смысла. 26 июн 2014 в 13:22
  • @Awe4k Да, тут можно немного запутаться :) Я подкорректировал ответ, в данной реализации при делении на два отрезка между элементами сохраняется соотношение меньше либо равны, а не строго меньше, но это суть дела не меняет. Одинаковые элементы все равно в дальнейшем прибьются к границам в этих отрезках :)
    – vinnie
    26 июн 2014 в 13:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.