Доброго времени суток всем. В данной статье я хотел бы поделиться с вами тем, что мучает меня уже некоторое время. Дело в том, что как то вечером, размышляя на тему алгоритмов сортировки (после удачно написанного Quick Sort для собеседования) я пришел к алгоритму довольно простого и, я бы сказал, даже в некоторой степени забавного в своей простоте, метода сортировки «массивов целых случайных чисел». Сначала я подумал, что кто-нибудь обязательно уже что-то подобное описал. Но поиски в русском сегменте интернета результатов не дали. В довольно обширной статье на Хабре по алгоритмам сортировок и их сравнении я ничего подобного не нашел тоже.
Далее я постараюсь этот алгоритм коротко разобрать.
На самом деле, алгоритм, кажется, будет занимать меньше слов чем вступительное слово. Вся суть сводится к тому, что массив, который нам необходимо отсортировать мы сортировать не будем. Не будем сортировать в привычном понимании этого действа программистами, т.е. никаких перестановок элементов местами, никаких делений массивов на несколько под массивов. Все что нужно сделать — создать еще один массив (только двумерный), длинна которого будет равняться максимальному значению среди всех элементов сортируемого массива, а вторая размерность нужна для хранения повторяющихся найденных чисел:
Далее, проходя в цикле по двумерному массиву (каждый элемент массива определяется по индексу, равному значению i_того элемента в сортируемом массиве) в этот двумерный массив с данным индексом записывается сам i_тый элемент сортируемого массива. Ниже представлено тоже самое только в коде.
Таким образом получается, что по адресу [0][0] лежит значение 0 (по адресу [123][0] лежит число 123 если оно есть в исходном массиве и т.д.):
Значения по адресу [i][0] — сами числа
Значения по адресу [i][1] — количество их повторений
Вот и все. В итоге мы получаем отсортированный массив, в котором если в строке есть отличное от нуля число, значит оно было в первоначальном массиве. А во второй строке хранятся количества повторений. Остается только найденные числа перенести в итоговый массив, если такой необходим.
Наверняка этот алгоритм можно еще усовершенствовать. Это первые выжимки из мыслей на этот счет. Так что строго не судите.
Могу предположить, что алгоритм довольно быстр для массивов с небольшим разбросом данных. И более-менее равномерно использующим числовой ряд. (сложность в лучшем случае 2 прохода: 1 для поиска самого большого числа, 2 копирование элементов массива).
Из явных минусов сразу кидается в глаза то, что имеется необходимость создавать двумерный массив. Соответственно выделение под него дополнительной памяти.
Конечно же для массива из двух элементов {10000, 0} этот алгоритм создаст двумерный массив длинной в 20000 элементов.
P.S.: С удовольствием прочитаю ваши комментарии, а в случае, если у вас имеется информация о подобных реализациях, большая просьба поделиться ссылкой.
Далее я постараюсь этот алгоритм коротко разобрать.
На самом деле, алгоритм, кажется, будет занимать меньше слов чем вступительное слово. Вся суть сводится к тому, что массив, который нам необходимо отсортировать мы сортировать не будем. Не будем сортировать в привычном понимании этого действа программистами, т.е. никаких перестановок элементов местами, никаких делений массивов на несколько под массивов. Все что нужно сделать — создать еще один массив (только двумерный), длинна которого будет равняться максимальному значению среди всех элементов сортируемого массива, а вторая размерность нужна для хранения повторяющихся найденных чисел:
int tempArr [maxValUnsortedArr] [2];
Далее, проходя в цикле по двумерному массиву (каждый элемент массива определяется по индексу, равному значению i_того элемента в сортируемом массиве) в этот двумерный массив с данным индексом записывается сам i_тый элемент сортируемого массива. Ниже представлено тоже самое только в коде.
Таким образом получается, что по адресу [0][0] лежит значение 0 (по адресу [123][0] лежит число 123 если оно есть в исходном массиве и т.д.):
for(int i = 0; i < quantityEl; i++){
tempArr [unsortedArr [i]][1] += 1;
tempArr [unsortedArr [i]][0] = unsortedArr [i];
}
Значения по адресу [i][0] — сами числа
Значения по адресу [i][1] — количество их повторений
Вот и все. В итоге мы получаем отсортированный массив, в котором если в строке есть отличное от нуля число, значит оно было в первоначальном массиве. А во второй строке хранятся количества повторений. Остается только найденные числа перенести в итоговый массив, если такой необходим.
Наверняка этот алгоритм можно еще усовершенствовать. Это первые выжимки из мыслей на этот счет. Так что строго не судите.
Могу предположить, что алгоритм довольно быстр для массивов с небольшим разбросом данных. И более-менее равномерно использующим числовой ряд. (сложность в лучшем случае 2 прохода: 1 для поиска самого большого числа, 2 копирование элементов массива).
Из явных минусов сразу кидается в глаза то, что имеется необходимость создавать двумерный массив. Соответственно выделение под него дополнительной памяти.
Конечно же для массива из двух элементов {10000, 0} этот алгоритм создаст двумерный массив длинной в 20000 элементов.
P.S.: С удовольствием прочитаю ваши комментарии, а в случае, если у вас имеется информация о подобных реализациях, большая просьба поделиться ссылкой.