[Teen Idle.]

Зависла с хешированием/сортировкой.
В общем, дан массив длиной n, его нужно отсортировать следующим образом:
- есть хеш-функция, которая в соответствие каждому элементу ставит его индекс в отсортированном массиве
- создается массив Х из n пустых массивов, в каждый подмассив добавляется элемент изначального массива на основе полученных ранее индексов
- на основе предыдущего массиве получаем отсортированный массив
Проблема в том, что мне нужно, чтобы массив Х был заполнен полностью, т.е. в каждом подмассиве один элемент. Если в изначальном массиве есть повторяющиеся элементы, этого не получается, например: [[1], [2], [3], [4], [], [6, 6], [7, 7], [8], [], [10]]. Как это можно решить?
Спасибо!

@темы: Алгоритм

Comments

[A-D-M]

Мне кажется нужно произвести проверку на наличие пустых массивов,
в случае если массив пуст на его место записать слудующее значение, или же просто изменить индексы
А массивы X и n создавать основываясь на количестве непустых массивов.

[Imaginary Unit]

Думаю, на этапе выдаче индексов элементам было бы логично ввести такое условие, что у двух элементов не может быть одного и того же индекса. Другими словами - при совпадении индексов нужно ставить элементы не в одну ячейку, а в соседние. Как-то так)

[Teen Idle.]

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

[A-D-M]

упс извиняюсь, немного неправильно понял задачу.
а проверку на пустые ячейки чтобы не получилось такого - [ ]
произвести в протцессе
- на основе предыдущего массива получаем отсортированный массив

[Teen Idle.]

taburetka91, да, думала об этом, но, опять же, по какому принципу? Не соображается мне что-то(
В моем же примере одной шестерке индекс нужно было бы уменьшить на 1, восьмерке и одной семерке - увеличить

[Imaginary Unit]

ну, если проверять совпадения уже после того, как все индексы выданы, то я это вижу примерно так:
1. ищем внутренний массив с более чем 1 элементом
2. смотрим слева от него и считаем пустые ячейки-массивы, если их >= чем элементов, идем дальше, иначе считаем еще справа.
3. сдвигаем всё что есть между этим массивом и пустой ячейкой так, чтобы освободить место рядом с массивом
4. засандаливаем лишние элементы в освободившиеся места рядом.
5. ну и повторяем с шага 1, пока во всех массивах не будет по 1 элементу))

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

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

[Teen Idle.]

Спасибо большое, попробую

вообще довольно мутный алгоритм получается для сортировки. я бы лучше как-нибудь проще реализовал)
Расскажите об этом моему преподу ))

[Слушатель]

Ния
Вы уверены, что подмассивы необходимы? Достаточно создать вспомогательный массив A из n ячеек. Дальше пройтись по искомому массиву и если для текущего числа k, окажется, что ячейка с индексом h(k) занята - увеличивать h(k) на 1 до тех пор пока не будет свободной ячейки и в свободную ячейку занести k.

Можно и с подмассивами. Тогда каждая ячейка в A хранит указатель на массив состоящий из одной ячейки и проверка идёт похожим образом.

[Teen Idle.]

Я уверена, потому что это требования преподавателя к решению данного задания
И по-моему если просто увеличивать на единицу, не получится отсортированных массив? Или я вас не так поняла?

[Слушатель]

Ния
Возьмём массив 4, 2, 1, 1, 5, 7, 9, 9.
Отсортированный массив: 1, 1, 2, 4, 5, 7, 9, 9

Выделим массив A размером 8, каждая ячейка - хранит указатель на массив размером 1:
[[], [], [], [], [], [], [], []]

h(4) = 4: [[], [], [], [4], [], [], [], []]
h(2) = 3: [[], [], [2], [4], [], [], [], []]
h(1) = 1: [[1], [], [2], [4], [], [], [], []]
h(1) = 1 - ячейка занята - h(1) = 2:[[1], [1], [2], [4], [], [], [], []]
h(5) = 5: [[1], [1], [2], [4], [5], [], [], []]
h(7) = 6: [[1], [1], [2], [4], [5], [7], [], []]
h(9) = 7: [[1], [1], [2], [4], [5], [7], [9], []]
h(9) = 7 - ячейка занята - h(9) = 8:[[1], [1], [2], [4], [5], [7], [9], [9]]

Но это будет работать при условии, что хеш-функция будет возвращать минимальный индекс элемента в отсортированном массиве. Т.е. например для двух единиц h(1) = 1.

Хеш-функция так не работает?

[Teen Idle.]

Да, ваша правда. Кажется, ошибка в хеш-функции. Функция работает так:
[n*a[i]/(M-m)-n*m/(M-m)]
где n=длина массива -минус один, M - макс. элемент, m - мин элемент, [x] - целая часть, на ваш массив возвращает [3, 1, 1, 1, 4, 6, 8, 8], что, очевидно, неверно. Что следует изменить в ней?

[Слушатель]

Прошу прощения, но сейчас у меня нет времени на исправление хеш-функции.

Пока можно сделать следующее:

Использовать ту функцию какая есть, после заполнения массива - починить его по алгоритму taburetka91 (я его не проверял, поэтому не знаю надёжен он или нет).

Либо исправить хеш ф-цию и использовать мой алгоритм. Это по-моему труднее. И так "на лету" я не могу предложить что там надо исправить. Надеюсь, что вам смогут помочь другие участники.

[Teen Idle.]

Да за что прощение просить, спасибо, что вообще ответили Буду разбираться