Thuật toán RadixSort Bằng C++

[cò lã]

Thuật toán RadixSort hơi khó. Vì nó không phải dùng danh sách liên kết, mà là trên mảng nên khó hơn. Tuy mình đã hiểu ý tưởng nhưng không biết viết giải thuật bằng C++. Mong các bạn giúp mình với !

[huynguyen]

Nếu theo sách ở VN thì kiểu radix sort thường là sắp xếp dựa trên con số, mình có tìm thấy 1 kiểu sắp xếp dựa trên bit, cũng là radi sort, bạn có thể tham khảo thêm, rất hay và ngắn gọn:

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;
void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for (int i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for (int i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

void radixsort (long *source, long *temp, long N)
{
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
}

void make_random (long *data, long N)
{
  for ( int i=0; i<N; i++ ) data[i]=rand()%32760;
}

long data[10];
long temp[10];

int main()
{
 srand(time(0)); make_random(data, 10);
 for ( int i=0; i<10; i++ ) cout <<setw(6) << data[i];
 cout <<endl;
 radixsort (data, temp, 10);
 for ( int i=0; i<10; i++ ) cout <<setw(6) << data[i];
 getchar(); return 0;
}

[cò lã]

Cậu lại đưa bài này ra rồi huynguyen ! Bài này không đúng tí nào, mình đã thử nhiều rồi xin cậu cho bài khác bằng mảng hợp lí hơn !

[soda_chanhmuoi]

Anh ơi hàm memset (count, 0, sizeof (count)); là j` vậy? chắc trên VC 2005 có hàm này sẵn ah?

[sonhn]

Hàm memset dùng để điền một giá trị vào vùng nhớ cho trước. Ví dụ để điền giá trị 0 vào mảng a có n phần tử kiểu int, thay vì dùng vòng lặp for để làm lần lượt thì mình chỉ cần gọi:

memset(&a[0], 0, n*sizeof(int))

Hàm này có trong ANSI-C xa lơ la lắc, trong thư viện <memory.h>.

[cò lã]

Cảm ơn các bạn đã xem câu hỏi của tôi. Tôi đã xem lại ý tưởng và đã giải được bài này !

[dinhan]

mình cũng đang ko hiểu hàm đó. ai hiểu câu lệnh này giải thích giùm mình với
memset(&g_pxstate,0,sizeof(g_pxstate));