Radix Sort (مرتب سازي مبنا)

[mohadese77]

كسي سورس مرتب سازي مبنا رو داره؟؟؟؟؟؟؟؟؟؟

 

[iaidin]

كسي سورس مرتب سازي مبنا رو داره؟؟؟؟؟؟؟؟؟؟

------------------------------------------------------------------------------------------------
Example in C
------------------------------------------------------------------------------------------------
#include <stdio.h>
#define MAX 5
#define SHOWPASS
void print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d\t", a);
}

void radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 0; i < n; i++)
{
if (a > m)
m = a;
}

while (m / exp > 0)
{
int bucket[10] =
{ 0 };
for (i = 0; i < n; i++)
bucket[a / exp % 10]++;
for (i = 1; i < 10; i++)
bucket += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[a / exp % 10]] = a;
for (i = 0; i < n; i++)
a = b;
exp *= 10;

#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}


int main()
{
int arr[MAX];
int i, n;

printf("Enter total elements (n < %d) : ", MAX);
scanf("%d", &n);

printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++)
scanf("%d", &arr);


printf("\nARRAY : ");
print(&arr[0], n);

radixsort(&arr[0], n);

printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");

return 0;
}
------------------------------------------------------------------------------------------------
Example in C++
------------------------------------------------------------------------------------------------
#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

typedef std::vector<unsigned int> input_type;

void radix_sort(input_type & x)
{
if ( x.empty() ) return; // at least one element

typedef std::vector< std::vector< input_type::value_type > > buckets_type;
buckets_type buckets(10); // allocate buckets
// for sorting decimal numbers

int pow10 = 1; // pow10 holds powers of 10 (1, 10, 100, ...)

// find maximum in the array to limit the main loop below
input_type::value_type max = *std::max_element(x.begin(), x.end());

//begin radix sort
for(; max != 0 ; max/=10, pow10*=10)
{
// 1. determine which bucket each element should enter
// for each element in 'x':
for(input_type::const_iterator elem = x.begin(); elem != x.end(); ++elem)
{
// calculate the bucket number:
size_t const bucket_num = ( *elem / pow10 ) % 10;
// add the element to the list in the bucket:
buckets[ bucket_num ].push_back( *elem );
}

// 2. transfer results of buckets back into main array
input_type::iterator store_pos = x.begin();
// for each bucket:
for(buckets_type::iterator bucket = buckets.begin(); bucket != buckets.end(); ++bucket)
{
// for each element in the bucket:
for(buckets_type::value_type::const_iterator bucket_elem = bucket->begin();
bucket_elem != bucket->end(); ++bucket_elem)
{
// copy the element into next position in the main array
*store_pos++ = *bucket_elem;
}
bucket->clear(); // forget the current bucket's list
}
}
}

int main(){

input_type input;

// read numbers from standard input (ends with end-of-file: ^Z / ^D, or
// with a new line that contains something that's not a number)
std::cout << "Enter positive numbers to sort:" << std::endl;
std::copy(std::istream_iterator<unsigned int>(std::cin),
std::istream_iterator<unsigned int>(), std::back_inserter(input));

if ( input.end() != std::find(input.begin(), input.end(), 0) )
{
std::cerr << "Zero isn't positive" << std::endl;
return 1;
}

std::cout << " ** Elements before sorting: " << std::endl;
std::copy(input.begin(), input.end(),
std:stream_iterator<unsigned int>(std::cout, " "));

radix_sort(input);

std::cout << std::endl << " ** Elements after sorting: " << std::endl;
std::copy(input.begin(), input.end(),
std:stream_iterator<unsigned int>(std::cout, " "));
std::cout << std::endl;

return 0;
}​