Битовая сортировка!

@zewer · Регистрация: 07.01.2011

Студворк — интернет-сервис помощи студентам

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

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

P.S. И сразу вопрос: мне препод говорил, что в С/С++ есть команды, которые делают смещения вправо. Но я об таком нигде не слышал, и нигде не находил. Можете подсказать насчет этих команд?

@Duha666 · 30.03.2012, 04:54

Один из вариантов реализации:

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 · 30.03.2012, 18:37 **[ТС]**

за пример и ф-ию огромное спасибо. А есть какая то инфа в виде теории? ибо на реферат надо хотя би 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 · 30.03.2012, 19:27

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 · 30.03.2012, 23:12 **[ТС]**

скажи пжл, как и где в проге ты делал перевод из 10 СЧ в двуичную систему числения...

@Duha666 · 31.03.2012, 05:06

digit(x, i) получает i-ый бит числа x(для простоты, будем считать, что нумерация битов с нуля). Вообщем, она работает так:
Пусть есть число 01101(в двоичном виде). Мы выполняем сдвиг вправо на i. Пусть i = 2.
01101 >> 2 = 011(вышло за границу 01, теперь их больше нет). Выполнив логическое "и" с единицей мы можем получить нужный нам бит
011 & 001 = 1
010 & 001 = 0(ещё пример)
Вот таким образом работает digit.
Переводить же руками число в двоичную систему счисления не надо. Потому что мы выполняем битовые операции, которые и так на этой системе счисления выполняются

@zewer · 31.03.2012, 11:47 **[ТС]**

спасибо за обяснение, не знал такого!

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@zewer 2356 / 1774 / 212 Регистрация: 07.01.2011 Сообщений: 10,342

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

@zewer 2356 / 1774 / 212 Регистрация: 07.01.2011 Сообщений: 10,342
	30.03.2012, 23:12 [ТС]
	скажи пжл, как и где в проге ты делал перевод из 10 СЧ в двуичную систему числения... 0

@Duha666 53 / 53 / 19 Регистрация: 10.03.2012 Сообщений: 138
	31.03.2012, 05:06
	digit(x, i) получает i-ый бит числа x(для простоты, будем считать, что нумерация битов с нуля). Вообщем, она работает так: Пусть есть число 01101(в двоичном виде). Мы выполняем сдвиг вправо на i. Пусть i = 2. 01101 >> 2 = 011(вышло за границу 01, теперь их больше нет). Выполнив логическое "и" с единицей мы можем получить нужный нам бит 011 & 001 = 1 010 & 001 = 0(ещё пример) Вот таким образом работает digit. Переводить же руками число в двоичную систему счисления не надо. Потому что мы выполняем битовые операции, которые и так на этой системе счисления выполняются 1

@zewer 2356 / 1774 / 212 Регистрация: 07.01.2011 Сообщений: 10,342
	31.03.2012, 11:47 [ТС]
	спасибо за обяснение, не знал такого! 0