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

From

Kommander Bomber (2:5059/26.17)

To

Sergey Panfilov

Date

2002-12-24T19:46:10Z

Area

RU.ALGORITHMS

Привет, Alexx!
 AO> помогите плиз, а то вpемени мало. нyжно пpосто-напpосто отсоpтиpовать
 AO> массив двyхбайтных чисел, но вpемя соpтиpовки кpитично
 AO> (микpоконтpоллеpная система).

 Надеюсь, по исходнику поймешь как работает. Основная функция - sort.

=== Здесь начинается src.c ===
typedef unsigned short uint16;
typedef long int32;
typedef short int16;

typedef int16 sizer;
/*typedef int32 sizer;*/

void sort1(uint16 *mas, sizer razm) {
uint16 swp, prefix;
sizer i,j;
sizer Pakety[128];

 if (razm>2/*или не 2, а больше, тогда оставшееся отработать отдельно,
    например использовать quicksort для razm, удовлетворяющих
    условию 256+2*razm>razm*log(2,razm)*/) {
    prefix=mas[0]&0xff80;
    for (i=0; i<128; i++) Pakety[i]=0;
    for (i=0; i<razm; i++) Pakety[mas[i]&0x7f]++;
    j=0;
    for (i=0; i<128; i++)
        while (Pakety[i]--)
              mas[j++]=prefix|((uint16)i);
 } else
   if (mas[0]>mas[1]) {
      swp=mas[0];mas[0]=mas[1];mas[1]=swp;
   }
}

uint16 *sort(uint16 *Massiv, sizer Razmer) {
 sizer Pakety[512],i,t;
 uint16 *Massiv1;


  for (i=0; i<512; i++) Pakety[i]=0;
  for (i=0; i<Razmer; i++) Pakety[Massiv[i]>>7]++;
  for (i=1; i<512; i++) Pakety[i]+=Pakety[i-1];
  Massiv1=(uint16 *)malloc(Razmer*sizeof(uint16));
  for (i=0; i<Razmer; i++)
      Massiv1[--Pakety[Massiv[i]>>7]]=Massiv[i];
  for (i=0; i<511; i++)
      if ((t=Pakety[i+1]-Pakety[i])>1)
         sort1(&Massiv1[Pakety[i]], t);
  if ((t=Razmer-Pakety[511])>1)
     sort1(&Massiv1[Pakety[i]], t);

  return Massiv1;
}
=== А здесь src.c кончается ===

--- GoldED/W32 3.0.1-asa8
 * Origin: -or- (2:5059/26.17)