Обработка дубликатов ключей в быстрой сортировке - PullRequest
Новая
       13

Обработка дубликатов ключей в быстрой сортировке

1 голос
/ 01 августа 2011

Наивной быстрой сортировке потребуется O (n ^ 2) времени для сортировки массива, не содержащего уникальных ключей, потому что все ключи будут разделены либо до, либо после значения pivot Существуют способы обработки дублированных ключей (как описано в Оптимальная сортировка ). Предложенное решение работает только для раздела Hoare, но я реализовал раздел Lomuto. Чтобы иметь дело с дублирующимися ключами, я чередовал перемещение дубликатов слева от центра и перемещение дубликатов справа от центра. Алгоритм работает примерно так: 

//partition array from index start to end
select pivot element and move it to array[start]
boolean dupHandler=true;
int index=start;
for(i from start+1 to end)
     int val=array[start].compareTo(array[i]);
     if(val==0)
          if(dupHandler)
               swap array[++index] and array[i]
          dupHandler=!dupHandler;
     else if(val>0)
          swap array[++index] and array[i]
swap array[start] and array[index]

Есть ли лучший (более эффективный) способ обработки дубликатов ключей?

РЕДАКТИРОВАТЬ: Мой код (как показано) требует, чтобы сравнение было равным (даже если это не является обязательным требованием)

...