Предыстория
В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.
Представим, что у нас есть следующий набор чисел:
- 123
- 12345
- 22345
- 12345678
- 1
Как мы, будучи людьми будем сортировать этот массив данных? Правильно, будем выбирать самое, визуально длинное, число.
А если длина одинаковая, то будем сравнивать цифры в одном разряде. Я подумал, что можно точно также заставить работать компьютер.
Алгоритм
Итак, имеем на входе массив чисел размером N:
int[] array = new int[n]
Далее, каждый элемент массива представляем в двоичном виде и сохраняем в новом списке:
bool[][] bitMatrix = new bool[n][]; //битовая матрица нашего массива for (int i = 0; i < array.Length; i++) { BitArray bitArray = new BitArray (new int[1]{ array [i] }); bool[] bits = new bool[bitArray.Length]; bitArray.CopyTo (bits, 0); Array.Reverse (bits); bitMatrix [i] = bits; }
Мы получили следующую матрицу:
Затем следует самая интересная часть: рекурсивная сортировка.
Для начала, давайте посмотрим на то, как бы мы сортировали эту битовую матрицу:
- Смотрим на первую колонку
- Выбираем все элементы где первый бит равен 1 в один список
- Выбираем все элементы где первый бит равен 0 во второй список
- Повторяем действия 2 и 3 для первого и второго списков, но уже для колонки номер два
Код будет выглядеть следующим образом:
private void SortAlgorithm(bool[][] bitMatrix, int columnNumber) { List<bool[]> ones = new List<bool[]> (); List<bool[]> zeros = new List<bool[]> (); for (int i = 0; i < bitMatrix.Length; i++) { if (bitMatrix[i][columnNumber]) ones.Add(bitMatrix[i]); else zeros.Add(bitMatrix[i]); } columnNumber++; if (columnNumber == MAX_COLUMN_COUNT)//MAX_COLUMN_COUNT = sizeof(int)*8 { sortedBitMatrix.AddRange(ones); sortedBitMatrix.AddRange(zeros); return; } if (ones.Count != 0) SortAlgorithm (ones.ToArray(), columnNumber); if (zeros.Count != 0) SortAlgorithm (zeros.ToArray(), columnNumber); }
sortedBitMatrix используется для хранения отсортированной битовой матрицы.
Для преобразования битовой матрицы обратно в массив воспользуемся следующим методом:
private int[] ConvertBitMatrixToArray(List<bool[]> bitMatrix) { int[] resultArray = new int[bitMatrix.Count]; int count = 0; for (int i = 0; i < bitMatrix.Count; i++) { bool[] bits = bitMatrix [i]; Array.Reverse(bits); BitArray bitArray = new BitArray(bits); int[] tmpArray = new int[1]; bitArray.CopyTo(tmpArray, 0); resultArray [count] = tmpArray [0]; count++; } return resultArray; }
Результатом метода будет отсортированный массив.
А как же распараллеливание?
Так как основная часть времени тратится на прохождение по каждой колонке битовой матрицы в поиске единиц и нулей, то этот процесс можно запустить в нескольких потоках.
Каждый поток будет искать единицы и нули в части матрицы:
Сложность
Для сортировки заданного массива нам нужны следующие итерации:
- Создание битовой матрицы: n
- Поиск нулей и единиц: 32n
- Преобразование отсортированной битовой матрицы: n
Итого: 34n, что является O(n)
Интересно Ваше мнение.
Спасибо за внимание.
ссылка на оригинал статьи http://habrahabr.ru/post/215357/
Добавить комментарий