С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
zewer
1369 / 1058 / 111
Регистрация: 07.01.2011
Сообщений: 6,934
#1

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

30.03.2012, 02:55. Просмотров 2294. Ответов 6
Метки нет (Все метки)

Всем привет. Нужно написать реферат по теме "Битовая сортировка".
Такого в инете, а также Википедиях и прочих джерелах даже примерно не удалось найти.
Находил что то подобное с "Карманная сортировка" или "Поразрядная сортировка".
Но там информация насчет десятичной системы числения, а меня интересует ТОЛЬКО битовая, т.е. двоичная система числения.
Примерный алгоритм: береться два кармана, или что то такое. Все числа из входной последовательности представляем в двоичном виде(проще говоря переводим из СЧ10 в СЧ2).
Потом берем 1 число из входной последовательности, и смотрим на его младший(по другому - самый правый) разряд. Если там 0, то бросаем в 1 карман, если 1 - в второй карман.
И так через всю последовательность, учитывая что ставиться числа в карман должны строго по порядку. В итоге получим два кармана с данными.
Потом в ряд записываем сначало первый(там где местяться числа с 0 вконце), а потом и второй карман(с 1 вконце), но так же строго сохраняем порядок розмещений чисел в карманах.
После этого делаем зсув вправо на 1 символ для ВСЕХ чисел. и начинаем распределять по карманах сначала, но нужно делать распределение уже по числам из полученной последовательности.
и ставить в первый карман числа с 0, во второй - с единицей в младшем розряде, но также надо строго сохранять порядок. и так повторяем столько раз, сколько имеет розрядов самое большой число их входной последовательности

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

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

битовая маска - C++
как использовать битовую маску? за пример можно взять выделение k-того разряда из n-разрядного числа (в пофиг какой системе исчесления).

Битовая арифметика - C++
Почему при: int myVar = 15, mask = 0x00 00 00 01; //выделил разряды printf("%d", myVar & mask); Я получаю -1? Конечно, я мог бы...

Битовая маска - C++
Как в шифровании битовыми перестановками применить маску?

Битовая операция -> - C++
Что делает операция -> К примеру, есть структура: struct BIT{ unsigned int cod1:3; :1;...

С, битовая запись - C++
Всем доброго времени суток, после 3 дней поиска информации решил попытать счастье, задав вопрос у форумчан. так же читал много подобных...

Битовая инверсия - C++
Доброго времени суток! Я что-то запутался с побитовой инверсией. В коде прописываю int a=5; cout<<~a<<endl; Это же...

6
Duha666
51 / 51 / 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
1
zewer
1369 / 1058 / 111
Регистрация: 07.01.2011
Сообщений: 6,934
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];
    }
можно описать в каждой строке коментарий, а то чтото не очень понятно..., если вам не трудно!)
0
Duha666
51 / 51 / 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.
И так далее до самого левого бита.
1
zewer
1369 / 1058 / 111
Регистрация: 07.01.2011
Сообщений: 6,934
30.03.2012, 23:12  [ТС] #5
скажи пжл, как и где в проге ты делал перевод из 10 СЧ в двуичную систему числения...
0
Duha666
51 / 51 / 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.
Переводить же руками число в двоичную систему счисления не надо. Потому что мы выполняем битовые операции, которые и так на этой системе счисления выполняются
1
zewer
1369 / 1058 / 111
Регистрация: 07.01.2011
Сообщений: 6,934
31.03.2012, 11:47  [ТС] #7
спасибо за обяснение, не знал такого!
0
31.03.2012, 11:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2012, 11:47
Привет! Вот еще темы с ответами:

64-битовая строка - C++
Необходимо реализовать структуру 64-битовой строки состоящей из двух unsigned long полей, с последующей возможностью использования битовых...

битовая маска - C++
надо разработать функцию проверки правильности битовой маски. 32-х битная “маска” считается действительной, если ее двоичное...

Битовая операция с отрицательным числом - C++
Есть такой код int main() { int k = 12; cout &lt;&lt; (k &amp; -k); return 0; } Выводит этот код

собрать число , битовая арифметика - C++
Помогите пожалуйста, а то с битовой арифметикой проблемы, получаю из color числа его каналы по следующей формуле R = (color &gt;&gt; 16) &amp;...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.