Форум программистов, компьютерный форум CyberForum.ru

Битовая сортировка! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
zewer
 Аватар для zewer
1022 / 713 / 72
Регистрация: 07.01.2011
Сообщений: 5,369
30.03.2012, 02:55     Битовая сортировка! #1
Всем привет. Нужно написать реферат по теме "Битовая сортировка".
Такого в инете, а также Википедиях и прочих джерелах даже примерно не удалось найти.
Находил что то подобное с "Карманная сортировка" или "Поразрядная сортировка".
Но там информация насчет десятичной системы числения, а меня интересует ТОЛЬКО битовая, т.е. двоичная система числения.
Примерный алгоритм: береться два кармана, или что то такое. Все числа из входной последовательности представляем в двоичном виде(проще говоря переводим из СЧ10 в СЧ2).
Потом берем 1 число из входной последовательности, и смотрим на его младший(по другому - самый правый) разряд. Если там 0, то бросаем в 1 карман, если 1 - в второй карман.
И так через всю последовательность, учитывая что ставиться числа в карман должны строго по порядку. В итоге получим два кармана с данными.
Потом в ряд записываем сначало первый(там где местяться числа с 0 вконце), а потом и второй карман(с 1 вконце), но так же строго сохраняем порядок розмещений чисел в карманах.
После этого делаем зсув вправо на 1 символ для ВСЕХ чисел. и начинаем распределять по карманах сначала, но нужно делать распределение уже по числам из полученной последовательности.
и ставить в первый карман числа с 0, во второй - с единицей в младшем розряде, но также надо строго сохранять порядок. и так повторяем столько раз, сколько имеет розрядов самое большой число их входной последовательности

Алгоритм работы я знаю, но мне нужна какая то инфа, и чем больше тем лучше. И лучше что б был какойто пример на С или С++.

P.S. И сразу вопрос: мне препод говорил, что в С/С++ есть команды, которые делают смещения вправо. Но я об таком нигде не слышал, и нигде не находил. Можете подсказать насчет этих команд?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2012, 02:55     Битовая сортировка!
Посмотрите здесь:

C++ битовая маска
Битовая операция -> C++
собрать число , битовая арифметика C++
C++ битовая маска
64-битовая строка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
30.03.2012, 04:54     Битовая сортировка! #2
Один из вариантов реализации:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
int a[100], b[100], n;
 
int digit(int n, int p)
{
    return (n >> p & 1);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int k = sizeof(int);
    for(int i = 0; i < k; i++)
    {
        int c[2] = {0};
        for(int j = 0; j < n; j++)
            c[digit(a[j],i)]++;
        for(int j = 1; j < 2; j++)
            c[j] += c[j - 1];
        for(int j = n - 1; j > -1;j--)
            b[--c[digit(a[j],i)]] = a[j];
        for(int j = 0; j < n; j++)
            a[j] = b[j];
    }
    for(int i = 0; i < n; i++)
        cout << a[i] <<endl;
    return 0;
}

Цитата Сообщение от zewer Посмотреть сообщение
Можете подсказать насчет этих команд
>> - битовый сдвиг вправо. << - битовый сдвиг влево. в функции digit это используется. Мы сдвигаем число вправо что бы нужный нам бит стал первым, а потом получаем его с помощью логического "и" с 1
zewer
 Аватар для zewer
1022 / 713 / 72
Регистрация: 07.01.2011
Сообщений: 5,369
30.03.2012, 18:37  [ТС]     Битовая сортировка! #3
за пример и ф-ию огромное спасибо. А есть какая то инфа в виде теории? ибо на реферат надо хотя би 2 листа А4 по этому методу. Сойдет или книга или на сайте. Искал много часов, но теории в инете не нашел ((

Добавлено через 5 часов 47 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 0; i < k; i++)
    {
        int c[2] = {0};
        for(int j = 0; j < n; j++)
            c[digit(a[j],i)]++;
        for(int j = 1; j < 2; j++)
            c[j] += c[j - 1];
        for(int j = n - 1; j > -1;j--)
            b[--c[digit(a[j],i)]] = a[j];
        for(int j = 0; j < n; j++)
            a[j] = b[j];
    }
можно описать в каждой строке коментарий, а то чтото не очень понятно..., если вам не трудно!)
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
30.03.2012, 19:27     Битовая сортировка! #4
C++
1
2
3
4
5
6
7
8
for(int j = 0; j < n; j++)
    c[digit(a[j],i)]++; // подситываем количсетво каждой из цифр
for(int j = 1; j < 2; j++)
    c[j] += c[j - 1]; // устанавливаем позиции, на которых должны располагаться числа с заданными цифрами
for(int j = n - 1; j > -1;j--)
    b[--c[digit(a[j],i)]] = a[j]; // расставляем в соответствии с цифрой
for(int j = 0; j < n; j++)
    a[j] = b[j];
Если не совсем понятна идея сортировки, то опишу смысл второго for.
Если у нас было x нулей, то они все числа с единицей на рассматриваемом бите будут располагаться на позициях 1..x. Если же у нас есть k единиц, то числа с единицей будут располагаться на позициях x+1..x+k. Таким образом мы ставим правую границу расположения элемента с определенной цифрой. А потом пробегаемся и расставляем на нужную позицию.
Вот ещё пример.
Есть числа в битовом представлении: 101 100 001.
Подсчитаем правые границы - 1, 3(1 + 2).
Текущий бит числа 101 - 1. Поэтому ставим его на позицию 3 и уменьшаем правую границу этой цифры:
. . 101 границы - 1, 2
Далее расставляем 100
100 . 101 границы - 0 2
И наконец 001
100 001 101.
И так далее до самого левого бита.
zewer
 Аватар для zewer
1022 / 713 / 72
Регистрация: 07.01.2011
Сообщений: 5,369
30.03.2012, 23:12  [ТС]     Битовая сортировка! #5
скажи пжл, как и где в проге ты делал перевод из 10 СЧ в двуичную систему числения...
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
31.03.2012, 05:06     Битовая сортировка! #6
digit(x, i) получает i-ый бит числа x(для простоты, будем считать, что нумерация битов с нуля). Вообщем, она работает так:
Пусть есть число 01101(в двоичном виде). Мы выполняем сдвиг вправо на i. Пусть i = 2.
01101 >> 2 = 011(вышло за границу 01, теперь их больше нет). Выполнив логическое "и" с единицей мы можем получить нужный нам бит
011 & 001 = 1
010 & 001 = 0(ещё пример)
Вот таким образом работает digit.
Переводить же руками число в двоичную систему счисления не надо. Потому что мы выполняем битовые операции, которые и так на этой системе счисления выполняются
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2012, 11:47     Битовая сортировка!
Еще ссылки по теме:

C++ Битовая арифметика
С, битовая запись C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
zewer
 Аватар для zewer
1022 / 713 / 72
Регистрация: 07.01.2011
Сообщений: 5,369
31.03.2012, 11:47  [ТС]     Битовая сортировка! #7
спасибо за обяснение, не знал такого!
Yandex
Объявления
31.03.2012, 11:47     Битовая сортировка!
Ответ Создать тему
Опции темы

Текущее время: 02:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru