You cannot copy content of this page.

Monthly Archive December 2012

Sorting – Radix Sort

Sorting – Radix Sort

Radix Sort sorts the number in scans equal to the number of digits of maximum number.

eg.  45, 3, 235, 89, 150, then maximum scans = 3.

Thus radix sort operates three times.

Radix sort uses 10 queues to sort the given numbers.

  • Begin with least significant digit, ending with most significant digit.
  • Fetch a number from the array and place it in one of the queues depending upon its value say 2 means it is placed in node[2].  If a number already exists at that position than the correct ordered position for the new number is determined.
  • Retrieve these elements from the queue from 0 to n back into array.
  • Repeat this process till most significant bit.
  • Display the array which is finally sorted.

Program to implement Radix Sort:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5

struct queue
{int info;
struct queue *next;
}*node[10]={NULL};

struct queue *front=NULL,*rear=NULL;
struct queue *create()
{
struct queue *temp=(struct queue*)malloc(sizeof(struct queue));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct queue *makenode(int num)
{
struct queue *temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}
struct queue *insert(struct queue *s,int num)
{
struct queue *ptr=s;
struct queue *temp=makenode(num);
if(s==NULL)
s=temp;
else
{while((ptr->next->info<=num) && (ptr->next!=NULL))
ptr=ptr->next;
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

int digits_count(int num)
{
int rmdr,quot,ct=0;
quot=num/10;
rmdr=num%10;
ct++;
while(quot!=0)
{
num=quot;
quot=num/10;
rmdr=num%10;
ct++;
}
return ct;
}

int max_element(int arr[],int n)
{
int max,i;
max=arr[0];
for(i=1;i<n;i++)
{if(arr[i]>max)
max=arr[i];
}
return max;
}

int return_ith_digit(int num,int pos)
{
int i, ndigits, rmdr;
ndigits = digits_count(num);
if(pos>ndigits)
return 0;
rmdr=num%10;
for(i=0;i<pos;i++)
{
num=num/10;
rmdr=num%10;
}
return rmdr;
}

void radixsort(int arr[], int n)
{
int i,j,digits,max,y;
int k=0,p=0;
max=max_element(arr,n);
digits = digits_count(max);
for(i=0;i<digits;i++)
{
for(j=0;j<n;j++)
{
y=return_ith_digit(arr[j],i);
node[y]=insert(node[y],arr[j]);
}
for(p=0;p<10;p++)
{
while(node[p]!=NULL)
{
arr[k++]=node[p]->info;
printf(“%d->”,node[p]->info);
node[p]=node[p]->next;
}
}
printf(“\b\b “);
}
}
void main()
{
int arr[MAX],i,n;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
radixsort(arr,n);
getch();
}

 

Tags,

Sorting – Straight Selection Sort

Sorting – Straight Selection Sort

  • Begin from the first element, taking i=0 to n-1.
  • Find the minimum number in the first scan.
  • Interchange ith element with the minimum number.
  • Start searching minimum element again from i+1 to n.
  • The number of scans is equal to the number of elements.
  • Stop scan when the last element remains to be replaced with min.
  • Display the output which is now sorted.
Example:

Though this method requires only half the number of comparisons required by simple selection sort, but the time complexity is still O(n2).

Program to implement Straight Selection Sort:

#include <stdio.h>
#include <conio.h>

#define MAX 5

void straightselectionsort(int arr[],int n)
{
int i,j,k;
float min,temp;
for(i=0;i<n-1;i++)
{
min=arr[i];
k=i;
for(j=i+1;j<n;j++)
{if(arr[j]<min)
{min=arr[j];
k=j;
}
}
arr[k]=arr[i];
arr[i]=min;
}
}

void main()
{
int arr[MAX];
int i,n;
clrscr();
printf(“\nEnter the value of n?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter the value of x?”);
scanf(“%d”,&arr[i]);
}
printf(“\n\nArray you have entered is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
straightselectionsort(arr,n);
printf(“\n\nSorted Array is: \n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}

 

Tags,

Sorting – General Selection Sort

Sorting – General Selection Sort

Steps: 

  1. Fetch the numbers to be sorted in an array.
  2. Push these numbers one by one to a priority queue.  (Any priority-lower or higher may be considered).

Case 1:  Lower values with high priority for ascending order.

Case 2:  Higher values with high priority for descending order.

3. Pop all the elements from the priority queue to the array one by one.

4. Display the array, which is now in sorted order.

Example:  Let us consider that lower values are given high priority.

Program to implement General Selection Sort:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 5

struct queue
{
int arr[MAX];
int front,rear;
};

void push(struct queue *q,int x)
{int f,r,j;
if(q->front==-1)
{
q->arr[0]=x;
q->front=q->rear=0;
return;
}
f=q->front;
r=q->rear;
if(q->rear==MAX-1)
{
printf(“\nQueue full! Overflow.”);
exit(1);
}
while(f<=r && q->arr[f]<x)
{f++;
}
for(j=r;j>=f;j–)
q->arr[j+1]=q->arr[j];
q->arr[f]=x;
q->rear++;
}

int pop(struct queue *q)
{
if(q->front==-1)
{printf(“\nQueue empty! Underflow.”);
exit(1);
}
return(q->arr[(q->front)++]);
}

void display(struct queue *q)
{
int f,r;
if(q->front == -1)
{
printf(“\nQueue empty…!”);
exit(1);
}
f=q->front;
r=q->rear;
while(f!=r)
printf(“%d\t”,q->arr[f++]);
printf(“%d\t”,q->arr[f]);
}

void main()
{
int arr[MAX], i;
struct queue q;
q.front=q.rear=-1;
clrscr();
for(i=0;i<MAX;i++)
{
printf(“\nEnter array elements?”);
scanf(“%d”,&arr[i]);
}
for(i=0;i<MAX;i++)
{push(&q,arr[i]);
}
printf(“\n\nDisplaying queue elements…!\n\t”);
display(&q);
printf(“\n\nSorted Array is:”);
for(i=0;i<MAX;i++)
{
arr[i]=pop(&q);
printf(“%d\t”,arr[i]);
}
getch();
}

 

Tags,

x Close

Like Us On Facebook