(С++) Сортировка распределением

[[DarkNet]Alpha]

Зацените реализацию. Критика приветствуется.

(Нажмите, чтобы показать/скрыть)

Код: [Выделить]

void DistributionSort(int *_array, int _size)
{
int min = _array[0], max = _array[0];
for(int i = 1; i < _size; i++)
{
if(_array[i] < min)
min = _array[i];
if(_array[i] > max)
max = _array[i];
}
int amountSize = abs(max - min) + 1;
int *amount = new int[amountSize] ();

for(int i = 0; i < _size; i++)
amount[_array[i]-min]++;

int k = 0;
for(int i = 0; i < _size; i++)
{
while(amount[k] == 0)
k++;

_array[i] = k + min;
amount[k]--;
}
delete [] amount;
}

[Señor_Gaga]

Отличная реализация (правда не тестировал).
 
Вот еще вариант:

(Нажмите, чтобы показать/скрыть)

Код: [Выделить]

void DistributionSort(int *_array, int _size)
{
int *amount = new int[_size] ();

for(int i = 0; i < _size; i++) amount[k] = 0;

        for(int i = 1; != amount[_array[i]]; i++) amount[_array[i]] += 1;

        int k = 1;
        for(int i = 0; i < _size; i++)
           for(int j = 0; j != amount[i]; j++) _array[k++] = i;

delete [] amount;
}

// Используйте тег код.

[Красноглазый]

Зацените реализацию. Критика приветствуется.

(Нажмите, чтобы показать/скрыть)

Код: [Выделить]

void DistributionSort(int *_array, int _size)
{
int min = _array[0], max = _array[0];
for(int i = 1; i < _size; i++)
{
if(_array[i] < min)
min = _array[i];
if(_array[i] > max)
max = _array[i];
}
int amountSize = abs(max - min) + 1;
int *amount = new int[amountSize] ();

for(int i = 0; i < _size; i++)
amount[_array[i]-min]++;

int k = 0;
for(int i = 0; i < _size; i++)
{
while(amount[k] == 0)
k++;

_array[i] = k + min;
amount[k]--;
}
delete [] amount;
}

Хреновый код.
Во-первых, нет проверки входных параметров, например, if(!_array || (_size < 1)) return;
Во-вторых, функция abs - лишняя, поскольку (max - min) всегда неотрицательно.
В-третьих, массив amount неинициализирован и строго говоря там может оказаться "мусор".

P.S. И еще посмотри, каков будет размер массива amount при входном массиве [10000, 1, -10000].

[Señor_Gaga]

>>Во-первых, нет проверки входных параметров, например, if(!_array || (_size < 1)) return;
Входные параметры можно проверить перед вызовом.
>>Во-вторых, функция abs - лишняя, поскольку (max - min) всегда неотрицательно.
Не критично
>>В-третьих,
Согласен

// не стоит злоупотреблять цветами текста

[RazrFalcon]

Зацените реализацию. Критика приветствуется.

А что оно делает то?

[Красноглазый]

Проверять параметры надо именно в процедуре, чтобы не проверять каждый раз перед вызовом. Тем более, что без проверки код потенциально опасен.
Если уж использовать именно такой алгоритм, то я бы сделал как-то так:

(Нажмите, чтобы показать/скрыть)

Код: [Выделить]

void DistributionSort(int *_array, int _size)
{
if(!_array || (_size < 1)) return;
int min = _array[0], max = _array[0];
int i;
for(i = 1; i < _size; i++){
int vl = _array[i];
if(vl < min) min = vl; else if(vl > max) max = vl;
}
int amountSize = max - min + 1;
int *amount = new int[amountSize] ();
for(i = 0; i < amountSize; i++) amount[i] = 0;
for(i = 0; i < _size; i++) amount[_array[i] - min]++;
for(int k = 0, i = 0; k < amountSize; k++)
while(amount[k]--) _array[i++] = k + min;
delete [] amount;
}


Пользователь решил продолжить мысль 25 Октября 2011, 13:31:00:

А что оно делает то?

Сортирует массив через статистический массив попаданий.

[Señor_Gaga]

>>Проверять параметры надо именно в процедуре, чтобы не проверять каждый раз перед вызовом. Тем более, что без проверки код потенциально опасен.

Надо смотреть контекст вызова. Возможно вызов уже с гарантированно правильными
параметрами.

[RazrFalcon]

Сортировка числового массива? 
Что-то не въезжаю...

[[DarkNet]Alpha]

Во-первых, нет проверки входных параметров, например, if(!_array || (_size < 1)) return;
Во-вторых, функция abs - лишняя, поскольку (max - min) всегда неотрицательно.

Вы таки правы.

В-третьих, массив amount неинициализирован и строго говоря там может оказаться "мусор".

А вот здесь нет. Волшебные скобки в конце строки int *amount = new int[amountSize] (); заполняют массив нулями.

P.S. И еще посмотри, каков будет размер массива amount при входном массиве [10000, 1, -10000].

А вот тут не знаю, как поправить. Есть идеи?

[Красноглазый]

Волшебные скобки в конце строки int *amount = new int[amountSize] (); заполняют массив нулями.

А пруф привести можно? Что-то я такого нигде не видел...

P.S. И еще посмотри, каков будет размер массива amount при входном массиве [10000, 1, -10000].

А вот тут не знаю, как поправить. Есть идеи?

Это проблема алгоритма. Можно использовать двойной массив 2 x _size. Первый элемент - индекс, второй - значение. Но тогда поиск в массиве будет перебором, а не смещением. Выигрыш в памяти за счет использования процессора.
А чем пузырьковая сортировка не устраивала?

[Señor_Gaga]

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

[[DarkNet]Alpha]

Пруф дать пока не могу, это мне товарищ подсказал. Можете проверить.
Интересно узнать разные методы.

[Красноглазый]

С двойным массивом как-то так:

(Нажмите, чтобы показать/скрыть)

Код: [Выделить]

struct _int_2{
int idx, val;
};

void DistributionSort(int *_array, int _size)
{
if(!_array || (_size < 2)) return;
int min = _array[0], max = _array[0];
int i;
for(i = 1; i < _size; i++){
int vl = _array[i];
if(vl < min) min = vl; else if(vl > max) max = vl;
}
_int_2 *amount = new _int_2[_size] ();
for(i = 0; i < _size; i++){ amount[i].idx = 0; amount[i].val = 0; }
amount[0].idx = min;
amount[1].idx = max;
for(i = 0; i < _size; i++){
int vl = _array[i];
for(int j = 0; j < _size; j++){
if(amount[j].idx < vl) continue;
if(amount[j].idx == vl) amount[j].val++;
else{
for(int k = _size - 1; k > j; k--) amount[k] = amount[k - 1];
amount[j].idx = vl;
amount[j].val = 1;
}
break;
}
}
for(int j = 0, i = 0; j < _size; j++)
while(amount[j].val--) _array[i++] = amount[j].idx;
delete [] amount;
}