Re: быстpая соpтиpовка

From

Oleg I. Khovayko ()

To

Nick Kovaliov

Date

2002-12-26T17:28:16Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Nick Kovaliov wrote:
> 
> Ну может ещё не побитовая, и по 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)