Посоветуйте алгоритм сортировки

yolki

сортируем целые числа
требуется из одного массива перелить в другой - отсортированный
по ходу сортировки нужно построить обратный индекс.
хорошо бы опционально иметь возможность отсечь дубликаты.
хорошо бы он был stable

procenkotanya

в каких пределах числа и сколько их?
а так, похоже что старый добрый mergesort вполне подойдёт

yolki

чисел около 100 тыс. значения от 0 до 100 тыс.
максимум - до миллиона где-то

Maurog

сортируй указатели любым алгоритмом сортировки (std::sort)
можно сортировать пары <число, указатель>
зы: вопрос бы уточнил: тебе быстро надо или хоть как-нибудь? что уже попробовал?
зы2: какой язык? bash сойдет?

istran

Мне кажется ixSort подойдет - stable, линейный. Отсечение дублей и обратный индекс можно после сортировки сделать тоже за линейку.

tokuchu

сортируй указатели любым алгоритмом сортировки (std::sort)
можно сортировать пары <число, указатель>

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

tokuchu

Я тоже за сортировку чем-либо одного массива и дальше мержить со 2-м.
Если значения чисел не очень разнообразные и нужно дубли исключать (да даже и с дублями можно то можно битовую маску сделать или подсчёт. Будет почти линейная сложность, только при малом размере массива оверхед будет.

yolki

сортировать нужно массив структур типа такого:



var Source: array of record

  Magic : Integer

  Data : ...;

 end;

язык - Pascal/Delphi.
конечная цель:
1. получить массив полей Magic, отсортированный
2. получить индекс Index, такой что Source[Index[...]] будет отсортирован по Magic;
3. желательно убрать дубликаты из Magic (Index будет содержать дубликаты)

Andbar

хорошо бы опционально иметь возможность отсечь дубликаты.
хорошо бы он был stable

если отсекаются дубликаты, то какая разница, стабильный ли алгоритм?

pitrik2

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

ну ему же индекс надо

pitrik2

обратный индекс можно после сортировки сделать

бррр
как это?
и главное зачем?

tokuchu

ну ему же индекс надо

Мне показалось из его сообщения, что у него только числа. Оказалось нет.

Sebasten

Сортировка подсчётом, наверное всё сделает.

 

function CountSort(cont A : array of Records, B: array of Records, 

                                  size: integer, removeDuplicates: boolean) : array of integer

begin

    C := array of integer[MAX_VALUE + 1];

    for i := 1 to MAX_VALUE; i := i + 1 do

        C[i] = 0;

     for j  := 1 to size; j := j + 1 do

     begin

        C[A[j].Magic] := C[A[j].Magic] + 1;

        if removeDuplicates and C[A[j].Magic] > 1 then

                C[A[j].Magic] = 1;

     end;

     for i := 2 to MAX_VALUE; i := i + 1 do

         C[i] := C[i-1] + C[i];

     for j := 1 to size; j := j + 1; do

     begin

         if C[A[j].Magic] > 0 then

         begin

              B[C[A[j].Magic]] = A[j];

              C[A[j].Magic] := 0;

         end

    end

    ret := C;

end

Untested

Оставить комментарий