Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
n0stycat
0 / 0 / 0
Регистрация: 01.10.2015
Сообщений: 3
1

Побитовая сортировка массива

02.12.2016, 03:22. Просмотров 380. Ответов 3
Метки нет (Все метки)

Задача: с клавиатуры ввести массив размера num целых чисел. Используя проверку i-ый бит = 1 и i-ый бит = 0 написать функцию что упорядочивает все числа в массиве.

Как я понимаю эту задачу, нужно ввести маску и проверять по И от старшего бита к младшему, пока у одного из них не еденица а у другого - ноль (или неправильно?).

Вот что пока получилось:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main()
{
    int i, j, num, mask, temp;
    printf("Vvedite kolichestvo chisel\n");
    scanf("%d",&num);
    int mas[num];
    for(i=0;i<num;i++)
    {
        printf("%d)",i+1);
        scanf("%d",&mas[i]);
    }
 
    for(i = 0; i < num; i++)
    {
        mask = pow(2,sizeof(int) * 8);
        for(j = 0; j < sizeof(int) * 8; j++)
        {
            if((mas[j]&mask==1)&&(mas[j+1]&mask==0))
            {
                temp = mas[j];
                mas[j]=mas[j+1];
                mas[j+1]=temp;
                break;
            }
            else if((mas[j]&mask==0)&&(mas[j+1]&mask==1))
            {
                temp = mas[j+1];
                mas[j+1]=mas[j];
                mas[j]=temp;
                break;
            }
            else
                mask=mask>>1;
            if(mask==0)
            {
                continue;
            }
        }
 
    }
    printf("\nMASSIV:");
    for(i=0;i<num;i++)
    {
        printf("%d ",mas[i]);
    }
    getchar();
    return 0;
}
Как я понимаю, выходит переполнение mask, mas[j+1] выходит за пределы масива.
Но самое главное - проверка на бит не являеться правильной, потому что она никогда не выполняеться (нужно не И?).
Что делать и как исправить?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2016, 03:22
Ответы с готовыми решениями:

Побитовая упаковка
При написании одной проги возникла проблема упаковки бит for (int...

Побитовая запись в файл
Здравствуйте, передо мной стоит задача организовать побитовую запись в файл....

Побитовая обработка: в каждом байте переместить все единичные биты в конец
В каждом байте переместить все единичные биты в конец (Без использования строк...

Сортировка массива
Здравствуйте. Второй элемент массива, после сортировки, выводит бред. Что...

Сортировка массива структур
Ребят помогите пожалуйста с сортировкой структуры,не понимаю как ее сделать(...

3
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4848 / 2492 / 696
Регистрация: 18.10.2014
Сообщений: 4,319
02.12.2016, 03:51 2
Цитата Сообщение от n0stycat Посмотреть сообщение
Используя проверку i-ый бит = 1 и i-ый бит = 0 написать функцию что упорядочивает все числа в массиве.
По-видимому речь идет о radix sort - поразрядная сортировка.

Цитата Сообщение от n0stycat Посмотреть сообщение
mask = pow(2,sizeof(int) * 8);
Это что за маска такая? 232? Такое значение даже в типичный int не поместится.

Цитата Сообщение от n0stycat Посмотреть сообщение
потому что она никогда не выполняеться
Если mask - это маска с единственным выставленным единичным бытом, то величина mas[j] & mask будет иметь значения либо mask, либо 0. У вас же в коде делается проверка на либо 1, либо 0. Откуда вдруг взялось 1?
0
n0stycat
0 / 0 / 0
Регистрация: 01.10.2015
Сообщений: 3
02.12.2016, 04:46  [ТС] 3
Простите, я наверняка неправильно написал, но вот моя логика:
Проверка идет по старшему биту, но я не знаю сколько там разрядов, поэтому беру наибольший возможный бит для инта (да, надо было http://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{31}-1) и проверяю, исполняеться ли условие и если не выполняеться то сдвинуть (перейти к следующему).
Допустим будут сравниваться числа 5 и 6 это 101 и 110.
1=1,
0<1 - больше проверять не нужно, второе число больше, сменить их расположения.
Хотелось бы проверить только один бит справа, но не знаю как построить нужное условие.
0
n0stycat
0 / 0 / 0
Регистрация: 01.10.2015
Сообщений: 3
07.12.2016, 14:07  [ТС] 4
Вроде разобрался.
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main()
{
    int i, j, k, num;
    printf("Vvedite kolichestvo chisel\n");
    scanf("%d",&num);
    unsigned int mas[num];
    unsigned int temp;
    unsigned long mask;
 
    for(i=0;i<num;i++)
    {
 
        printf("Vvedite chislo > 0\n");
        scanf("%lu",&mas[i]);
    }
 
    for(i = 0; i < num - 1; i++)
    {
        for(k = 0; k < num - 1; k++)
        {
            mask = 2147483648u;
            for(j = 0; j < 32; j++)
            {
                if(((mas[k]&mask)==mask)&&((mas[k+1]&mask)==0))
                {
                    break;
                }
                if(((mas[k]&mask)==0)&&((mas[k+1]&mask)==mask))
                {
                    temp = mas[k];
                    mas[k]=mas[k+1];
                    mas[k+1]=temp;
                    break;
                }
                else
                    mask=mask>>1;
                if(mask==0)
                {
                    continue;
                }
            }
        }
    }
    printf("\nMASSIV:");
    for(i=0;i<num;i++)
    {
        printf("%lu ",mas[i]);
    }
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2016, 14:07

Сортировка массива выбором
Вот программы на паскале, кто может преобразовать их в си? {Сортировка массива...

Сортировка массива в функции
Дан массив, int ar = {4,7,2,9,12,32,6,74,1,5} необходимо сделать сортировку...

Сортировка массива по возрастанию
Здравствуйте! Помогите пожалуйста! Надо написать код чтобы введенный...


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

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

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