RSS

COUNTING SORT: ASCENDING ORDER

//PROGRAM TO SORT AN ARRAY IN ASCENDING ORDER USING COUNTING SORT

#include <iostream>
#include <cstring>

using namespace std;

void countingsort(int arr[], int size, int);

int main()
{
	int size, upper;
	
	cout<<"\nEnter the size of the array \n";
	cin>>size;
	cout<<"\nEnter the upper limit\n";
	cin>>upper;
	
	int *arr = new int[size+10];
	
	cout<<"\nInput the array \n";
	
		for(int i = 0; i<size; i++)
		{
			cin>>arr[i];
		}
		
	countingsort(arr,size, upper);
	
	cout<<"\nThe sorted array is \n";
	
		for(int i = 0; i<size; i++)
		{
			cout<<arr[i]<<' ';
		}
		
	return 0;
}

void countingsort(int arr[], int size,int upper)
{
	int *count = new int[upper+10];
	
	int *output = new int[size+10];
		  
	memset(count, 0, (upper+10)*sizeof(int));
		
	for(int i = 0; i<size; i++)
	{
		count[arr[i]]++;
	}
	
	for(int i = 1; i<=upper; i++)
	{
		count[i] += count[i-1];
	}
	
	for(int i = 0; i<size; i++)
	{
		output[count[arr[i]]-1] = arr[i];
		count[arr[i]]--;
	}
	
	for(int i = 0; i<size; i++)
	{
		arr[i] = output[i];
	}  
}
 

PROGRAM TO SORT AN INTEGER ARRAY IN DESCENDING ORDER USING COUNTING SORT

//THIS PROGRAM USES COUNTING SORT TO SORT AN ARRAY OF INTEGERS IN DESCENDING ORDER

#include <iostream>
#include <cstring>

using namespace std;

void countingsort(int [],int size, int upper);

int main()
{
	int size;
	
	cout<<"\nEnter the size of the array \n";
	cin>>size;
	
	int *arr = new int[size+10];
	
	int upper;
	
	cout<<"\nEnter the upper limit\n";
	cin>>upper;
	
	cout<<"\nEnter the array \n";
	
		for(int i= 0; i<size; i++)
		{
			cin>>arr[i];
		}
		
	countingsort(arr,size,upper);
	
	cout<<"\nThe sorted  array is \n";
	
	for(int i = 0; i<size; i++)
	cout<<arr[i]<<' ';
	
	return 0;
}

void countingsort(int arr[], int size, int upper)
{
	int *output = new int[size+10];
	int *count = new int[upper+10];
	
	for(int i = 0; i<=upper; i++)
	{
		count[i] = 0;
	}
	
	for(int i = 0; i<size; i++)                         
	{
	count[arr[i]]++;                                
	}                                 
									      
	for(int i = upper-1; i>=0; i--)       
	{
	count[i] = count[i] + count[i+1];
	}
	
	for(int i = 0; i<size; i++)
	{
		output[count[arr[i]] - 1] = arr[i];
		count[arr[i]]--;
	}
	
	for(int i = 0; i<size; i++)
	{
		arr[i] = output[i];
	}
}
 

PROGRAM TO MERGE TWO SORTED LINKED LISTS INTO A THIRD SORTED LINKED LIST

/* THIS PROGRAM MERGES TWO SORTED LINKED LISTS SUCH THAT THE SORTED LINKED LIST IS IN ASCENDING ORDER
  */

#include <iostream>
#include <process.h>

using namespace std;

struct node{
	int info;
	node *next;
};

class linkedlist{
	node *front;
	node *end;
	public:
		linkedlist()
		{
			front = end = NULL;
		}
		void add(int);
		node* retfront()
		{ return front;	}
};

node* mergelists(node *first, node *second);

int main()
{
	char wish = 'y';
	linkedlist first, second;
	
	cout<<"\nInput the first linked list's first element (ascending order)";
	
	int info;
	
	  while(wish == 'Y' || wish == 'y')
	  {
	  	cout<<"\nElement: \t";
	  	cin>>info;
	  	first.add(info);
	  	cout<<"\nAdd more? (Y/y)\n";
	  	cin>>wish;
	  }

	cout<<"\nInput the second linked list's first element (ascending order)\n";
	
	wish = 'Y';
	
		while(wish == 'y' || wish == 'Y')
		{
			cout<<"\nElement:\t";
			cin>>info;
			second.add(info);
			cout<<"\nAdd more? (Y/y)\n";
			cin>>wish;
		}
		
	cout<<"\nMerging the linked lists\n";
	
	node *newlist = mergelists(first.retfront(), second.retfront());
	
	cout<<"\nThe merged linked list is \n\n";
	
	while(newlist != NULL)
	{
		cout<<newlist->info;
		newlist = newlist->next;
		cout<<'\n';
	}
	
	return 0;
}

node * mergelists(node *first, node *second)
{
	linkedlist newlist;
	
	while(first != NULL && second != NULL)
	{
		if(first->info < second->info)
		{
			newlist.add(first->info);
			first = first->next;
		}
		else
		{
			newlist.add(second->info);
			second = second->next;
		}                                      
	}                                          
											
	if(first != NULL)
	{
		while(first != NULL)
		{
			newlist.add(first->info);
			first = first->next;
		}
	}
	else if(second != NULL)
	{
		while(second != NULL)
		{
			newlist.add(second->info);
			second = second->next;
		}
	}
	
	return newlist.retfront();
}

void linkedlist::add(int val)
{
	node *ptr = new node;
	
	if(ptr == NULL)
	{
		cout<<"\nError !!! No memory available !!!!\n";
		cout<<"\nAborting.....\n";
		exit(1);
	}
	
	ptr->info = val;
	ptr->next = NULL;
	
	if(front == NULL)
	{
		front = end = ptr;
	}
	else                    
	{                       
		end->next = ptr;
		end = ptr;
	}
}
 
 

PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING LINKED LIST

// THIS PROGRAM IMPLEMENTS A CIRCULAR QUEUE USING A LINKED LIST

#include <iostream.h>
#include <conio.h>
#include <dos.h>
#include <process.h>

struct node
{
   int info;
   node *next;
};

class queue
{
   node *front;
   node *rear;

   public:
   void enqueue();
   void dequeue();
   void show();
   queue()
   {
      front = rear = NULL;
   }
   ~queue()
   {
      cout<<"\nQUEUE DESTROYED \n";
   }
};

void main()
{
   clrscr();

   char wish;
   int choice =  -1;

   queue q;

   do{
      clrscr();
      cout<<"\n        IMPLEMENTATION OF QUEUE USING LINKED LISTS \n\n\n";
      cout<<"\nCHOOSE AN OPERATION \n";
      cout<<"\n1. INSERT IN THE QUEUE (ENQUEUE) \n";
      cout<<"2. DELETE FROM THE QUEUE (DEQUEUE)\n";
      cout<<"3. SHOW THE QUEUE STATUS\n";
      cout<<"4. EXIT THE PROGRAM\n";
      cout<<"\n\nPLEASE ENTER YOUR CHOICE\n";
      cin>>choice;

	if(choice == 1)
	{
	   q.enqueue();
	   q.show();
	}
	else if(choice == 2)
	{
	   q.dequeue();
	   q.show();
	}
	else if(choice == 3)
	{
	   q.show();
	}
	else
	{
	   cout<<"\nTERMINATING...\n";
	   sleep(1);
	   exit(0);
	}
	cout<<"\n\n\nDO ANY MORE OPERATION? (Y/N) \n";
	cin>>wish;
   }
   while(wish == 'Y' || wish == 'y');

   cout<<"\nTHANKS!!!!. DO VISIT AGAIN\n";
   cout<<"\n\nPress any key to exit\n";
   getch();
}

void queue::enqueue()
{
   node *ptr = new node;
   clrscr();

   cout<<"\nPERFORMING ENQUEUE OPERATION \n\n";
   cout<<"\nENTER THE INFO PART OF NEW NODE\n";
   cin>>ptr->info;

   if(front == NULL)
   {
     front = rear = ptr;
     ptr->next = front;
   }
   else
   {
     rear->next = ptr;
     rear = ptr;
     rear->next = front;
   }

   cout<<"\n SUCCESSFUL\n";
}

void queue::dequeue()
{
   node *save;
   save = front;

   if(front == NULL)
   {
     cout<<"\nUNDERFLOW!!!\nNOTHING TO DELETE\n";
   }
   else if(front == rear)
   {
      front = rear = NULL;
      delete save;
      cout<<"\nDEQUE SUCCESSFUL\n\n\nMODIFIED QUEUE IS \n";
   }
   else
   {
    front = front->next;
    rear->next = front;
    delete save;
    cout<<"\nDEQUE SUCCESSFUL\n";
    cout<<"\n\nMODIFIED QUEUE IS \n";
   }
}

void queue::show()
{
   if(front == NULL)
    cout<<"\nQUEUE IS EMPTY \n";
   else
   {
    node *temp = front;
    cout<<"\nQUEUE STATUS IS \n\n";
    do
    {
	cout<<temp->info<<' ';
	temp = temp->next;
    }
    while(temp != front);
   }
}
 
Leave a comment

Posted by on December 17, 2015 in Stacks, Queues and Linked Lists

 

PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING ARRAYS

// PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING ARRAYS 

#include <iostream>
#define size 4
#include <process.h>

using namespace std;

class queue
{
	int arr[size];
	int front, rear;
	public:
		queue()
		{
		  front = rear = -1;
		}
		void insert();
		void del();
		void show();
};

int main()
{
	int choice = -1;
	char wish;
	queue myqueue;
	
	do
	{
	    cout<<"\n\n           IMPLEMENTING QUEUE USING ARRAYS              \n\n";
		cout<<"\n1. INSERT AN ELEMENT \n";
		cout<<"\n2. DELETE AN ELEMENT \n";
		cout<<"\n3. SHOW QUEUE STATUS \n";
		cout<<"\n4. EXIT\n";
	lb:	cout<<"\n\nPLEASE ENTER YOUR CHOICE\n";
		cin>>choice;
		
		switch(choice)
		{
			case 1:	myqueue.insert();
		   			break;
			case 2: myqueue.del();
					break;
			case 3: cout<<"\nQueue status is \n";
					myqueue.show();
					break;
			case 4: cout<<"\nTerminating...\n";
					exit(0);
		   default: cout<<"\nInvalid choice.... Enter correct one(1-4)\n";
		   			goto lb; 
		}
		
		cout<<"\n\nDo any more operation ? \n\n";
		cin>>wish;	
	}
	while(wish == 'Y' || wish == 'y');
	
	cout<<"\n\nThanks!!!!! Do come again..\n";
	return 0;
}

void queue::insert()
{
	if(rear == -1)
	{
		front = rear = 0;                       
	}											
	else if(front == 0 && rear <size-1  ||  front != 0  && rear <front-1 )
	{
	  rear++;
	}
	else if(front == 0 && rear == size-1  ||  rear == front-1)
	{
	   cout<<"\nQueue is full\n";
	   exit(0);
	}
	else
	{  
	 if(front >0  && rear == size-1)
	 {
	   rear = 0;
	 }
	}
	cout<<"\nInput the value you want to insert\n";
	int val;
	cin>>val;
	arr[rear] = val;
	cout<<"\nInsertion successful\n";
	cout<<"\nThe queue now is \n";
	show();
}

void queue::del()
{
	if(front == -1)
	{
	   cout<<"\nUnderflow!!!!Aborting....\n";
	   exit(0);
	}
	else if(front == rear)
	{
		front = rear = -1;
	}
	else if(front == size -1)
	{
	  front = 0;
	}
	else
	{
	  front++;
	}
	cout<<"\nDeletion successful\n";
	cout<<"\nQueue after deletion is \n";
	show();
}

void queue::show()
{
    if(front == -1)
    {
    	cout<<"\nempty\n";
	}
	else if(front == rear)
	{
		cout<<arr[front];
	}
	else if(front < rear)
	{
	      for(int i =front; i<=rear; i++)
	      cout<<arr[i]<<' ';
	}
	else 
	{
	     for(int i = front; i<size; i++)
	     cout<<arr[i]<<' ';
	     for(int i = 0; i<=rear; i++)
	     cout<<arr[i]<<' ';
	}
}
 
Leave a comment

Posted by on December 17, 2015 in Stacks, Queues and Linked Lists

 

Protected: MINESWEEPER GAME

This content is password protected. To view it please enter your password below:

 
Enter your password to view comments.

Posted by on December 17, 2015 in Miscellaneous Programs

 

THIS PROGRAM PRINTS THE LARGEST GAP BETWEEN TWO PRIME NUMBERS SMALLER THAN AN ENTERED NUMBER

// THIS PROGRAM PRINTS THE LARGEST GAP BETWEEN TWO PRIME NO.S IN A RANGE

#include <iostream.h>
#include <conio.h>


void main()
{
 clrscr();
 unsigned long long range;
 cout<<"\nEnter the range of prime numbers\n";
 cin>>range;

 unsigned long long *arr = new unsigned long long [range-1];

 for(unsigned long long i = 2; i<=range;i++)
 {
  arr[i-2] = i;
 }

 for(i = 0; arr[i]<=range; i++)
 {
  if(arr[i] != 0)
  {
   for(unsigned long long j = i+1; arr[j]<=range; j++)
   {
    if(arr[j] % arr[i] == 0)
    arr[j] = 0;
   }
  }
 }

cout<<"\nThe prime numbers in this range are\n";

 for(i = 0; i<= range-2; i++)
 {
  if(arr[i] != 0)
  cout<<arr[i]<<' ';
 }

 
 int gap = 0;
 int bestgap = 0;
 unsigned long long loc = 0;

 for(i = 0; i<=range-2; i++)
 {
  gap = 0;
  for(unsigned long long j = i+1; (arr[j] == 0 && j<=range-2); j++)
  {
   gap++;
  }
  if(gap>bestgap)
  {
   bestgap = gap;
   loc = i;
  }
  j--;
  i = j;
 }

 cout<<"\n\nThe bestgap is \n"<<bestgap;
 cout<<"\n\nThe numbers comprising this gap are \n";

 loc++;

 for(i = loc; i<loc+bestgap; i++)
 cout<<i+2<<' ';

 getch();
}