0

Код быстрой сортировки:

void qsort(int l,int r)
{
int i,j;
int t,x;
i=l;
j=r;
x=A[(l+r)/2];
do{
while(A[i]<x) i++;
while(A[j]>x) j--;
if(i<=j)
{
t=A[i]; A[i]=A[j]; A[j]=t;i++;j--;}
}while(i<=j);
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}

Вопрос: что такое pivot.Это то же самое , что и медиана ?

Как найти медиану? pivot = a[(l+ (r-l)/2)]; Это тоже медиана ?

Почему разделяющий элемент иногда выбирают случайно, иногда берут медиану(которую не знаю,как найти)?

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

  Что такое медиана из трёх ключей ?

2 ответа 2

1

Это не "медиана", а тот элемент, по которому выполняется деление (partitioning) элементов массива на две группы. Для идеальной работы алгоритма в качестве pivot-элемента для каждого подмассива надо брать его точную медиану. Но мы не знаем медиану подмассива во время работы алгоритма. А нахождение точной медианы требует времени. Мы не хотим тратить время на поиск точной медианы - это в общем итоге будет нерационально.

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

Популярным трюком для лучшего выбора pivot-элемента является median-of-three, когда берутся три разных элемента массива и из них в качестве pivot-элемента выбирается средний по порядку. Это, разумеется, тоже не обязательно даст нам медиану, но потенциально может приблизить наш выбор к ней.

7
  • Насколько я понимаю, тут имеется в виду так называемая медиана из 3-х ключей. В качестве pivot выбираем средний из первого, последнего и находящегося в середине элементов сортируемого отрезка.
    – avp
    31 янв 2018 в 18:38
  • @avp: Я упомянул "медиану из трех" в своем ответе. Но я не вижу никаких намеков на "медиану из трех" в вопросе. В приведенном коде никакой "медианы из трех" нет и в помине. 31 янв 2018 в 18:39
  • @AnT, про медиану из трех я то же читал , но не понял одну вещь-как её находить . Это типо взять первый , последний и средний элемент и с ними что-то сделать , выбрать кого-то ?
    – Elvin
    31 янв 2018 в 19:16
  • @AnT, а причем тут этот код? Суть в словах вопроса.
    – avp
    31 янв 2018 в 19:33
  • @AnT,что такое медиана трёх ключей, можете про неё рассказать, как находить ?
    – Elvin
    31 янв 2018 в 19:55
0

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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