|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 26 Dec 2002 18:28:16
To : Nick Kovaliov
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
Nick Kovaliov wrote:
>
> Hу может ещё не побитовая, и по 2-4 бита, например.
> Всё же быстрее будет уже во сколько раз.
Я что-то не представляю, как можно сделать сортировку
по группе бит без использования значительной дополнительной памяти
для сортируемых данных. Простого обмена здесь не выйдет.
А вот с памятью у "заказчика" как раз напряженка.
Или я ошибаюсь, и такой алгоритм есть? Если так - кинь в эху
свою реализацию групповой побитивой сортировки, не требующей
значительной дополнительной памяти под данные.
Вот моя реализация побитивой обменной сортировки,
использующая только одно дополнительное слово
под данные (переменная tmp). Кстати, при желании переменную
tmp можно сделать статической (общей для всех уровней рекурсии),
а то и вообще обойтись без нее, обменивая данные тремя XOR-ами.
Итак, мой исходник тут:
#include <stdio.h>
#include <stdlib.h>
void bitsort(int *begin, int *end, unsigned int mask) {
int *p1 = begin, *p2 = end, tmp;
if(p1 < p2 && mask) {
do {
if((*p1 & mask) == 0) { p1++; continue; }
if((*p2 & mask) != 0) { p2--; continue; }
tmp = *p1; *p1++ = *p2; *p2-- = tmp;
} while(p1 <= p2);
/* "<=" above need for correct recursive call below */
mask >>= 1;
bitsort(begin, p2, mask);
bitsort(p1, end, mask);
} /* if mask & ptrs */
} /* bitsort */
#define LEN 150
main() {
int mas[LEN];
int i;
for(i = 0; i < LEN; i++)
mas[i] = i ^ 53;
printf("start sortir...\n");
bitsort(mas, mas+LEN-1, 1 << 15);
printf("end sortir\n");
for(i = 0; i < 15; ++i) printf(" %d", mas[i]); printf("...");
for(i = LEN-15; i < LEN; ++i) printf(" %d", mas[i]); printf("\n");
}
Теперь ваш исходник -- в студию!
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
