[Из песочницы] BitSorting Алгоритм со сложностью О(n)

Предыстория

В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность 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. Смотрим на первую колонку


2. Выбираем все элементы где первый бит равен 1 в один список


3. Выбираем все элементы где первый бит равен 0 во второй список


4. Повторяем действия 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;
}

Результатом метода будет отсортированный массив.

А как же распараллеливание?

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

Каждый поток будет искать единицы и нули в части матрицы:

Сложность

Для сортировки заданного массива нам нужны следующие итерации:

1. Создание битовой матрицы: n


2. Поиск нулей и единиц: 32n


3. Преобразование отсортированной битовой матрицы: n

Итого: 34n, что является O(n)

Интересно Ваше мнение.

Спасибо за внимание.

P.S. http://ift.tt/N3ozcs

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.