Нахождения медианы quick sort

@Вованя · Регистрация: 20.02.2014

Студворк — интернет-сервис помощи студентам

При попытке найти медиану процесс начинает грузить процессор.
Деббагер показывает на линию, где выбирается медиана.
Подскажите, в чем проблема-то?
Если сделать просто mid = right, то все работает нормально.

Java

    static public void QuickSort(int[] a, int left, int right)
    {
 
        int l = left, r = right, tmp, mid = (a[left] + a[right] + a[right/2]) / 3;
        do
        {
            while(a[l] < mid) l++;
            while(a[r] > mid) r--;
            
            if(l <= r)
            {
                tmp = a[l];
                a[l] = a[r];
                a[r] = tmp;
                l++; r--;
            }
        }while(l <= r);
        if(r > left) QuickSort(a, left, r);
        if(l < right) QuickSort(a, l, right);       
    }

@turbanoff · 04.04.2014, 14:57

mid = (a[left] + a[right] + a[right/2]) / 3;

Откуда вы взяли эту формулу вообще?
Опорный элемент должен быть элементом массива, а у вас какая-то странная формула вычисляющая непонятное значение.
right/2 вообще может быть меньше left.

@Вованя · 04.04.2014, 15:47 **[ТС]**

Сообщение от turbanoff

Откуда вы взяли эту формулу вообще?

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

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

@turbanoff · 04.04.2014, 15:47

Сообщение от Вованя

он обязательно должен входить в ранж от минимального до максимального значения.

Так у вас массив не отсортирован же еще. Про какие максимальные и минимальные значения может идти речь.

Сообщение от Вованя

Опорный элемент не обязательно должен быть элементом массива

Это очень рекомендуется.

Попробуйте сделать нормальный выбор опорного элемента. Я уверен, что проблема в нём.

@Вованя · 04.04.2014, 17:58 **[ТС]**

Сообщение от turbanoff

Про какие максимальные и минимальные значения может идти речь

Мы берем первый элемент, средний элемент и последний элемент и находим среднее арифметическое этих элементов. Это значит, что полученное число очевидно входит в ренж массива, даже если он не отсортирован. Основываясь на этом элементе делим массив на 2 части ну и так далее.
Конечно, что может получится, что все 3 элемента окажутся максимальными\минимальными элементами, но это меньше шансов, чем это произойдет с 1 элементом.

Добавлено через 2 часа 1 минуту
Да, в общем, проблема оказалась в том, что левый указатель никогда не поднимается до значения right, так как он становится больше медианы и инкремент его не происходит. Именно для такой реализации быстрой сортировки нужно использовать либо рандомно выбранный элемент, либо мин\макс\средний элемент.

@turbanoff · 04.04.2014, 22:30

Сообщение от Вованя

средний элемент

right/2 - это не средний. Средний элемент будет иметь индекс (right - left) / 2

Добавлено через 1 час 56 минут
я напутал. Средний элемент, всё же будет иметь индекс left + (right - left) / 2

@Вованя · 05.04.2014, 01:05 **[ТС]**

Сообщение от turbanoff

Средний элемент, всё же будет иметь индекс left + (right - left) / 2

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

Java

1	int mid = (a[l] + a[r] + a[(r-l)/2 + l]) / 3;

@bigwhitefish · 06.04.2014, 00:31

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

Добавлено через 1 минуту
посмотрите сортировку в jdk 1.6

@Вованя · 06.04.2014, 07:32 **[ТС]**

Сообщение от bigwhitefish

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

Не понял, что конкретно вы имеете ввиду? Значения, равные образцу остаются на своих местах, зачем их переносить к краям и каким образом из-за этого зацикливается алгоритм? В коде, приведенном мною выше проблема была в том, что опорный элемент для каждого рекурсивного вызова определялся не конкретно из той части массива, который сортировался в данный момент, а из всего массива целиком, что приводило к тому, что опорный элемент мог иметь значение ниже, чем самый крайний(левый) элемент сортируемого подмассива, из-за чего левый указатель никогда не доходил до конца массива им метод рекурсивно вызывался согласно последнему условию if(l < right) QuickSort(a, l, right);

@turbanoff 4090 / 3824 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	04.04.2014, 14:57	2
	mid = (a[left] + a[right] + a[right/2]) / 3; Откуда вы взяли эту формулу вообще? Опорный элемент должен быть элементом массива, а у вас какая-то странная формула вычисляющая непонятное значение. right/2 вообще может быть меньше left. 0

@Вованя 153 / 148 / 66 Регистрация: 20.02.2014 Сообщений: 556
	04.04.2014, 15:47 [ТС]	3
	Сообщение от turbanoff Откуда вы взяли эту формулу вообще? Ну это один из вариантов выбора опорного элемента, для уменьшения вероятности худшего случая. Опорный элемент не обязательно должен быть элементом массива, но он обязательно должен входить в ранж от минимального до максимального значения. Но вопрос не в этом же. Добавлено через 20 минут Да уж, действительно, при таком способе реализации метода проблема в выборе опорного элемента, снимаю вопрос. 0

@turbanoff 4090 / 3824 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	04.04.2014, 15:47	4
	Сообщение от Вованя он обязательно должен входить в ранж от минимального до максимального значения. Так у вас массив не отсортирован же еще. Про какие максимальные и минимальные значения может идти речь. Сообщение от Вованя Опорный элемент не обязательно должен быть элементом массива Это очень рекомендуется. Попробуйте сделать нормальный выбор опорного элемента. Я уверен, что проблема в нём. 0

@Вованя 153 / 148 / 66 Регистрация: 20.02.2014 Сообщений: 556
	04.04.2014, 17:58 [ТС]	5
	Сообщение от turbanoff Про какие максимальные и минимальные значения может идти речь Мы берем первый элемент, средний элемент и последний элемент и находим среднее арифметическое этих элементов. Это значит, что полученное число очевидно входит в ренж массива, даже если он не отсортирован. Основываясь на этом элементе делим массив на 2 части ну и так далее. Конечно, что может получится, что все 3 элемента окажутся максимальными\минимальными элементами, но это меньше шансов, чем это произойдет с 1 элементом. Добавлено через 2 часа 1 минуту Да, в общем, проблема оказалась в том, что левый указатель никогда не поднимается до значения right, так как он становится больше медианы и инкремент его не происходит. Именно для такой реализации быстрой сортировки нужно использовать либо рандомно выбранный элемент, либо мин\макс\средний элемент. 0

@turbanoff 4090 / 3824 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	04.04.2014, 22:30	6
	Сообщение от Вованя средний элемент right/2 - это не средний. Средний элемент будет иметь индекс (right - left) / 2 Добавлено через 1 час 56 минут я напутал. Средний элемент, всё же будет иметь индекс left + (right - left) / 2 1

@bigwhitefish 53 / 53 / 14 Регистрация: 26.02.2014 Сообщений: 150
	06.04.2014, 00:31	8
	Вованя, проблема в том, что вы не обрабатываете значения, равные образцу. Их надо группировать (переносить к краям) и исключать из рекурсии, иначе алгоритм зацикливается. Добавлено через 1 минуту посмотрите сортировку в jdk 1.6 0

@Вованя 153 / 148 / 66 Регистрация: 20.02.2014 Сообщений: 556
	06.04.2014, 07:32 [ТС]	9
	Сообщение от bigwhitefish проблема в том, что вы не обрабатываете значения, равные образцу. Их надо группировать (переносить к краям) и исключать из рекурсии, иначе алгоритм зацикливается. Не понял, что конкретно вы имеете ввиду? Значения, равные образцу остаются на своих местах, зачем их переносить к краям и каким образом из-за этого зацикливается алгоритм? В коде, приведенном мною выше проблема была в том, что опорный элемент для каждого рекурсивного вызова определялся не конкретно из той части массива, который сортировался в данный момент, а из всего массива целиком, что приводило к тому, что опорный элемент мог иметь значение ниже, чем самый крайний(левый) элемент сортируемого подмассива, из-за чего левый указатель никогда не доходил до конца массива им метод рекурсивно вызывался согласно последнему условию if(l < right) QuickSort(a, l, right); 0

Опции темы