Поразрядная сортировка целых чисел с плавающей точкой

@flop · Регистрация: 03.05.2009

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

помогите пожалуйста решить задачу

@Gravity · 09.05.2009, 19:37

целых чисел с плавоющей точкой

Ты сам понял что написал?

@flop · 09.05.2009, 19:43 **[ТС]**

у меня тема методы сортировок
а задача так и наз поразрядная сортировка целых чисел с плавоющей точкой

@BasicMan · 09.05.2009, 19:52

Держи, студент, учись

Поразрядная сортировка целых чисел с плавающей точкой
У рассмотренного представления есть одна интересная особенность. А именно, если значение поля [Порядок] у одного числа больше соответствующего значения у другого, то первое число обязательно больше второго. Это следует непосредственно из формул перевода (1) и (2) и верно для неотрицательных чисел.
Если порядки равны, то сравниваются мантиссы. Это полностью соответствует обычной системе для целых чисел, когда сравниваются сначала старшие двоичные цифры, затем младшие.

Таким образом, можно интерпретировать числа стандарта IEEE-754 как целые соответствующей длины:

a > b равносильно (ulong)a > (ulong)b, если a, b > 0.
Неприятности начинаются с отрицательными числами. Первый бит равен единице, так что это число будет, как и в случае беззнаковых целых, очень большим положительным. Больше любого по-настоящему положительного.
Если a>0, b<0, то всегда (ulong)a < (ulong)b
С другой стороны, никакого инвертирования битов, как в случае целых чисел со знаком, не производится. Поэтому большее по модулю отрицательное число дает большее в беззнаковой целочисленной интерпретации.

a > b равносильно (ulong)a < (ulong)b, если a, b < 0.

Если запустить RadixSort на массиве: -302 -249 1258 2330 -2948 -543 2398 3263
после сортировки получим: 1258 2330 2398 3263 -249 -302 -543 -2948.
Сначала идут положительные числа, которые отсортировались абсолютно правильно. Затем идут отрицательные, но в обратном порядке!

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

Отрицательные числа расположены в обратном порядке, поэтому при вычислении их расположения необходимо идти от count[255]=0, соответствующего наименьшему отрицательному числу до count[128]. При этом в массив нужно записывать сумму всех чисел после текущего, включая само текущее.

C++
1
2
3
4
5
6
s = count[255] = 0;         // отрицательные числа располагаются от нуля
cp = count+254;
for (i = 254; i >= 128; --i, --cp) {
    *cp += s;
    s = *cp; 
}

Теперь можно написать окончательную реализацию.

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
55
56
57
58
// Функция для последнего прохода при поразрядной сортировке чисел с плавающей точкой
template<class T>
void floatRadixLastPass (short Offset, long N, T *source, T *dest, long *count) {
    T *sp;
    long s, c, i, *cp;
    uchar *bp;
 
    long numNeg=0;
    for(i=128;i<256;i++) numNeg += count[i];
 
    s=numNeg;
    cp = count;
    for (i = 0; i < 128; ++i, ++cp) {
        c = *cp;
        *cp = s;
        s += c;
    }
 
    // изменения, касающиеся обратного расположения отрицательных чисел.
    s = count[255] = 0;                 //
    cp = count+254;                     //
    for (i = 254; i >= 128; --i, --cp) {//
        *cp += s;                       // остальное - то же, что и в
        s = *cp;                        // signedRadixLastPass
    }   
 
    bp = (uchar *)source + Offset;
    sp = source;
    for (i = N; i > 0; --i, bp += sizeof(T) , ++sp) {
        cp = count + *bp;
        if (*bp<128) dest[ (*cp)++ ] = *sp;
        else dest[ --(*cp) ] = *sp;
    }
}
 
 
// поразрядная сортировка чисел с плавающей точкой
template<class T>
void floatRadixSort (T* &in, long N) {
    T *out = new T[N];
    ushort i;   
 
    long *counters = new long[sizeof(T)*256], *count;
    createCounters(in, counters, N);
 
    for (i=0; i<sizeof(T)-1; i++) {
        count = counters + 256*i;
        if ( count[0] == N ) continue;
        radixPass (i, N, in, out,count);
        swap(in, out);
    }
    count = counters + 256*i;
    floatRadixLastPass (i, N, in, out,count);
 
    delete in;
    in = out;
    delete counters;
}

Для большего удобства можно объединить все полученные сортировки в одну функцию с дополнительным параметром type = {FLOAT, SIGNED, UNSIGNED}, в зависимости от входного типа данных.

Не по теме:

"спосиба" можешь не нажимать, т.к. нашел случайно на этом сайте

@flop · 09.05.2009, 19:55 **[ТС]**

не все ровно спасибо а незнаешь кто может помочь с переводом на паскаль
то я в с не бум бум

@Puporev · 09.05.2009, 19:58

целых чисел с плавоющей точкой

Это запись целого числа с точкой, например 1321=1.3*10^3

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114

@flop 0 / 0 / 0 Регистрация: 03.05.2009 Сообщений: 6

	Поразрядная сортировка целых чисел с плавающей точкой 09.05.2009, 19:35. Показов 2742. Ответов 5 Метки нет (Все метки) помогите пожалуйста решить задачу 0

@flop 0 / 0 / 0 Регистрация: 03.05.2009 Сообщений: 6
	09.05.2009, 19:43 [ТС]
	у меня тема методы сортировок а задача так и наз поразрядная сортировка целых чисел с плавоющей точкой 0

@flop 0 / 0 / 0 Регистрация: 03.05.2009 Сообщений: 6
	09.05.2009, 19:55 [ТС]
	не все ровно спасибо а незнаешь кто может помочь с переводом на паскаль то я в с не бум бум 0