Member Avatar for ching

can anyone give me a example of a radix sort

  • 6 Contributors
  • 6 Replies
  • 412 Views
  • 5 Years Discussion Span
  • Latest Post Latest Post by dibilasd
Member Avatar for abu_sager

Hello,
I have done the Radix with queue
here you are an example
But the queue is my own Queue

retrieve: return the first element
serve : delete the first element;
dequeue: insertlast

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <cstdlib>
#include <ctime>
#include "queue.h"
#define MAX 11
void CopyToLast(Queue<int> []);
int main()
{
	Queue<int> q[MAX];
	srand(time(0));
	int res,i,j,digit = 4,passHelper=10,temp,pos;
	cout << "Before Sorting : \n";
	for(i=0;i<100;i++) {
		res = rand() % 10000;
		cout << res << "|";		
		q[MAX-1].append(res);
		
	}
		
	for(i=0;i<digit;i++) {
		
		while(!q[MAX-1].empty()) {
			q[MAX-1].retrieve(temp);
			q[MAX-1].serve();
			pos=temp;
			for(j=0;j<i;j++)
				pos/=10;
			pos %= 10;
			q[pos].append(temp);
		}
		
		
		passHelper *= 10;
		CopyToLast(q);
	}
	
	cout << "\nAfter sorting :\n";
	while(!q[MAX-1].empty()) {
		q[MAX-1].retrieve(temp);
		cout << temp << "|";
		q[MAX-1].serve();
	}
	
	return 0;
}
void CopyToLast(Queue<int> g[])
{
	int i,temp;
	for(i=0;i<MAX-1;i++) {
		while(!g[i].empty()) {
			g[i].retrieve(temp);
			g[MAX-1].append(temp);
			g[i].serve();
		}
	}

}

If you want here you are my own queue class

#ifndef QUEUE_H
#define QUEUE_H
enum Error_code {success,overflow,underflow};
template <typename Queue_entry>
class Queue {
public:
	Queue();
	bool empty()const;
	Error_code append(const Queue_entry &);
	Error_code serve();
	Error_code retrieve(Queue_entry &)const;
	~Queue();
	Queue(const Queue &);
	Queue &operator=(const Queue &);
protected:
	struct Node { 
		Queue_entry data;
		Node *next; 
	};
	Node *front,*rear;
};
template<typename Queue_entry>
Queue<Queue_entry>::Queue() {
	rear = front = NULL;
}
template<typename Queue_entry>
Queue<Queue_entry>::Queue(const Queue &x) {
	rear = front = NULL;
	Node *orginalFront = x.front,*orignalRear = x.rear,*q,*p = NULL;
	if (orginalFront != NULL) {
	front = new Node;
	p = NULL;
	front->data = orginalFront->data;
	front->next = NULL;
	p = front;
	
	while (orginalFront != NULL) {
	
		q= new Node;
		q->data = orginalFront->data;
		q->next = NULL;
		p->next = q;
		
		
		orginalFront = orginalFront->next;
		
	}
	
	rear = q;
	}
}

template<typename Queue_entry>
Error_code Queue<Queue_entry>::append(const Queue_entry &x) {
	Node *p = new Node;
	p->data = x;
	p->next = NULL;
	if (rear != NULL ) rear->next = p;
	
	rear = p;
	if (front == NULL) front = rear;
	return success;
}
template<typename Queue_entry>
Error_code Queue<Queue_entry>::retrieve(Queue_entry &item) const{
	if (!empty() ) {
		item = front->data;
		return success;
	}
	return underflow;
}
template<typename Queue_entry>
Error_code Queue<Queue_entry>::serve() {
	if (!empty() ) {
		Node *q = front;
		front = front->next;
		if (front == NULL) rear = NULL;
		delete q;
		return success;
	}
	return underflow;
}
template<typename Queue_entry>
bool Queue<Queue_entry>::empty() const {
	if (front == NULL) return true;
	return false;
}
template<typename Queue_entry>
Queue<Queue_entry> &Queue<Queue_entry>::operator =(const Queue<Queue_entry> &x)
{
	if (this != &x) {
		Node *p = front;
		while (front != NULL) {
			p = front;
			front = front->next;
			delete p;
		}
	
		rear = front = NULL;
	Node *orginalFront = x.front,*orignalRear = x.rear,*q;
	
	if (orginalFront != NULL) {
	front = new Node;
	p = NULL;
	front->data = orginalFront->data;
	front->next = NULL;
	p = front;
	
	while (orginalFront != NULL) {
	
		q= new Node;
		q->data = orginalFront->data;
		q->next = NULL;
		p->next = q;
		
		
		orginalFront = orginalFront->next;
		
	}
	
	rear = q;
	}
	}

	return *this;
}
template<typename Queue_entry>
Queue<Queue_entry>::~Queue()
{
		Node *p = front;
		while (front != NULL) {
			p = front;
			front = front->next;
			delete p;
		}
}
#endif
Member Avatar for abu_sager

This program is generates 100 random integers and store them in the latest Queue then start sorting

Member Avatar for gusano79

can anyone give me a example of a radix sort

Here's an explanation to complement Abu's code example:

A radix sort works with the digits of a number, working from the least significant digit to the most. Here's a sample set of numbers:
423 586 403 171 92 536 234 243

First, sort the numbers by the least siginificant digit (ones). For this algorithm to work, your buckets have to be order-preserving.
171 92 423 403 243 234 586 536

Then, sort them by the next most significant digit (tens):
403 423 234 536 243 171 586 92

Now hundreds:
92 171 234 243 403 423 536 586

...and they're sorted. Each step doesn't have to be a bucket sort; any order-preserving sort will work.

Member Avatar for Champhero

Can anyone provide me the Radix sorting through other than the Queue.w8ng for the replyyyyyy......

Member Avatar for ithelp

Can anyone provide me the Radix sorting through other than the Queue.w8ng for the replyyyyyy......

You can use buckets to code radix sort.

Member Avatar for dibilasd

dibilu

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.