Category Archives: Data Structures

C program to evaluate a postfix expression.

evaluate-postfix.c

C program to find out the value of an arithmetic expression in postfix (reverse polish) notation is as follows:

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

#define SIZE 100

int top = -1;
int stack[SIZE];

//Function prototypes
void push(int item);
int pop();
int is_operator(char symbol);

void main()
{
	int i, j;
	int x, y, result, value;
	char postfix_exp[SIZE];
	char item;
	int data_values[SIZE];

	clrscr();

	printf("\nEnter the arithmetic expression in Postfix notation: \n");
	gets(postfix_exp);

	//Take the values of all operands from the user.
	i = 0;
	j = 0;
	item = postfix_exp[i++];
	while(item != '\0')
	{
		if(isalpha(item))
		{
			printf("\nEnter the value of operand %c: ",item);
			scanf("%d",&data_values[j++]);
		}
		item = postfix_exp[i++];
	}

	//Evaluate the postifx expression using a stack.
	i = 0;
	j = 0;
	item = postfix_exp[i++];
	while(item != '\0')
	{
		if(isalpha(item))
		{
			push(data_values[j++]);
		}
		else if(is_operator(item))
		{
			y = pop();
			x = pop();

			switch(item)
			{
				case '+':
					result = x + y;
					break;
				case '-':
					result = x - y;
					break;
				case '*':
					result = x * y;
					break;
				case '/':
					result = x / y;
					break;
				case '^':
					result = pow(x,y);
					break;
			}

			push(result);
		}
		else
		{
			printf("\nInvalid Postfix Expression.\n");
			getch();
			exit(0);
		}

		item = postfix_exp[i++];
	}

	value = pop();
	printf("\nValue of the postfix expression is %d.\n",value);
	getch();
}

//Function for push operation
void push(int item)
{
	if(top >= SIZE-1)
	{
		printf("\nStack Overflow. Push not possible.\n");
	}
	else
	{
		top = top+1;
		stack[top] = item;
	}
}

//Function for pop operation
int pop()
{
	int item = NULL;

	if(top <= -1)
	{
		printf("\nStack Underflow. Pop not possible.\n");
	}
	else
	{
		item = stack[top];
		stack[top] = NULL;
		top = top-1;
	}
	return(item);
}

//Function to check whether the symbol is an operator.
int is_operator(char symbol)
{
	if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-')
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

C program for Selection Sort.

selection-sort.c

Here is a C program to sort the array elements in ascending order using Selection Sort technique:

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

#define SIZE 20

void selection_sort(int arr[]);

void main()
{
	int i,j;
	int array_to_sort[SIZE];
	clrscr();

	//Get the elements of Array
	for(i=0; i<SIZE; i++)
	{
		j = i+1;
		printf("\nEnter element %d: ",j);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Sort array.
	selection_sort(array_to_sort);

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

//Logic for Selection Sort.
void selection_sort(int arr[])
{
	int i, j, min_value, min_location, temp;

	for(i=0; i<SIZE-1; i++)
	{
		min_value = arr[i];
		min_location = i;

		for(j=i+1; j<SIZE; j++)
		{
			if(min_value > arr[j])
			{
				min_value = arr[j];
				min_location = j;
			}
		}

		if(min_location != i)
		{
			//Swap arr[i] with arr[min_location]
			temp = arr[i];
			arr[i] = arr[min_location];
			arr[min_location] = temp;
		}
	}
}

C program for Insertion Sort.

insertion-sort.c

Here is a C program to sort the elements of the array in ascending order using a technique called Insertion Sort.

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

#define SIZE 10

void insertion_sort(int unsorted_array[], int sorted_array[]);

void main()
{
	int i,j;
	int array_to_sort[SIZE], sorted_array[SIZE];
	clrscr();

	//Get the elements of Array
	for(i=0; i<SIZE; i++)
	{
		j = i+1;
		printf("\nEnter element %d: ",j);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Sort array.
	insertion_sort(array_to_sort, sorted_array);

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",sorted_array[i]);
	}

	getch();
}

//Logic for Insertion Sort.
void insertion_sort(int unsorted_array[], int sorted_array[])
{
	int i, j, key, location;

	sorted_array[0] = unsorted_array[0];

	for(i=1; i<SIZE; i++)
	{
		//Pick the element
		key = unsorted_array[i];

		//Find appropriate location by comparison
		location = i;
		while((location > 0) && (key < sorted_array[location-1]))
		{
			location = location - 1;
		}

		//Shift elements if required
		j = i;
		while(j > location)
		{
			sorted_array[j] = sorted_array[j-1];
			j = j-1;
		}

		//Place the element
		sorted_array[location] = key;
	}
}

C program for Quick Sort.

quick-sort.c

C program to sort the elements of the array in ascending order using Quick Sort technique is as follows:

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

#define SIZE 10
int array_to_sort[SIZE];

void quick_sort(int lower_bound, int upper_bound);
int partition(int left, int right);
void swap(int *num_1, int *num_2);

void main()
{
	int i, j, lower_bound, upper_bound;

	clrscr();

	//Get the elements of Array
	for(i=0; i<SIZE; i++)
	{
		j = i+1;
		printf("\nEnter element %d: ",j);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Sort array.
	lower_bound = 0;
	upper_bound = SIZE-1;
	quick_sort(lower_bound, upper_bound);

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

//Logic for Quick Sort.
void quick_sort(int lower_bound, int upper_bound)
{
	int left, right, loc;

	left = lower_bound;
	right = upper_bound;

	if(left < right)
	{
		loc = partition(left, right);
		quick_sort(left, loc-1);
		quick_sort(loc+1, right);
	}
}

int partition(int left, int right)
{
	int loc;

	loc = left;

	while(left < right)
	{
		//Scan from right to left
		while((array_to_sort[loc] <= array_to_sort[right]) && loc < right)
		{
			right = right - 1;
		}
		if(array_to_sort[loc] > array_to_sort[right])
		{
			swap(&array_to_sort[loc], &array_to_sort[right]);
			loc = right;
			left = left + 1;
		}

		//Scan from left to right
		while((array_to_sort[loc] >= array_to_sort[left]) && loc > left)
		{
			left = left + 1;
		}
		if(array_to_sort[loc] < array_to_sort[left])
		{
			swap(&array_to_sort[loc], &array_to_sort[left]);
			loc = left;
			right = right - 1;
		}
	}
	return(loc);
}

void swap(int *num_1, int *num_2)
{
	int temp;
	// printf("Swapping");
	temp = *num_1;
	*num_1 = *num_2;
	*num_2 = temp;
}

C program for Bubble Sort.

bubble-sort.c

Here is a C program to sort the elements of the array in ascending order using Bubble Sort technique:

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

#define SIZE 20

void bubble_sort(int arr[]);

void main()
{
	int i,j;
	int array_to_sort[SIZE];
	clrscr();

	//Get the elements of Array
	for(i=0; i<SIZE; i++)
	{
		j = i+1;
		printf("\nEnter element %d: ",j);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Sort array.
	bubble_sort(array_to_sort);

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");	
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

//Logic for Bubble Sort.
void bubble_sort(int arr[])
{
	int i,j,temp,swapped;

	for(i=1; i<SIZE; i++)
	{
		swapped = 0;
		for(j=0; j<SIZE-i; j++)
		{
			if(arr[j] > arr[j+1])
			{
				//Swap the elements
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				swapped = 1;
			}
		}

		//For optimization purpose.
		if(swapped == 0)
		{
			break;
		}
	}
}

C program for Merge Sort.

merge-sort.c

C program to sort the elements of the array in ascending order using Merge Sort technique is as follows:

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

#define SIZE 6
int array_to_sort[SIZE];

void merge_sort(int left, int right);
void merge(int left, int mid, int right);

void main()
{
	int i, j, lower_bound, upper_bound;

	clrscr();

	//Get the elements of Array
	for(i=0; i<SIZE; i++)
	{
		j = i+1;
		printf("\nEnter element %d: ",j);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Sort array.
	lower_bound = 0;
	upper_bound = SIZE-1;
	merge_sort(lower_bound, upper_bound);

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");
	for(i=0; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

//Logic for Merge Sort.
void merge_sort(int left, int right)
{
	int mid;
	if(left < right)
	{
		mid = (int)((left + right) / 2);
		merge_sort(left, mid);
		merge_sort(mid+1, right);
		merge(left, mid, right);
	}
}

void merge(int left, int mid, int right)
{
	int temp_array[SIZE];
	int i = left, j = mid + 1;
	int k = left;
	int m;

	while((i <= mid) && (j <= right))
	{
		if(array_to_sort[i] <= array_to_sort[j])
		{
			temp_array[k] = array_to_sort[i];
			i = i + 1;
			k = k + 1;
		}
		else
		{
			temp_array[k] = array_to_sort[j];
			j = j + 1;
			k = k + 1;
		}
	}
	if(i > mid)
	{
		while(j <= right)
		{
			temp_array[k] = array_to_sort[j];
			j = j + 1;
			k = k + 1;
		}
	}
	else
	{
		while(i <= mid)
		{
			temp_array[k] = array_to_sort[i];
			i = i + 1;
			k = k + 1;
		}
	}

	for(m=left; m<k; m++)
	{
		array_to_sort[m] = temp_array[m];
	}
}

C program for Heap Sort.

heap-sort.c

C program to sort the elements of the array in ascending order using Heap Sort technique is as follows:

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

#define SIZE 6
int array_to_sort[SIZE];

void build_heap();
void heap_sort();
void swap(int *num_1, int *num_2);

void main()
{
	int i;

	clrscr();

	//Get the elements of Array
	for(i=1; i<SIZE; i++)
	{
		printf("\nEnter element %d: ",i);
		scanf("%d", &array_to_sort[i]);
	}

	//Print the unsorted array.
	printf("\n\nUnsorted elements of Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	//Create heap tree
	build_heap();

	//Print the heap array.
	printf("\n\nUnsorted elements of Heap Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	heap_sort();

	//Print the sorted array.
	printf("\n\nSorted elements of Array are: ");
	for(i=1; i<SIZE; i++)
	{
		printf("%d ",array_to_sort[i]);
	}

	getch();
}

void build_heap()
{
	int i, j, parent;
	int temp_array[SIZE];

	for(i=1; i<SIZE; i++)
	{
		temp_array[i] = array_to_sort[i];

		j = i;
		while(j > 1)
		{
			parent = (int) (j/2);

			if(temp_array[parent] < temp_array[j])
			{
				swap(&temp_array[j], &temp_array[parent]);

				j = parent;
			}
			else
			{
				break;
			}
		}
	}

	for(i=1; i<SIZE; i++)
	{
		array_to_sort[i] = temp_array[i];
	}
}

void heap_sort()
{
	int i, j, lchild, rchild;

	for(i=SIZE-1; i>1; i--)
	{
		swap(&array_to_sort[1], &array_to_sort[i]);

		j = 1;
		while(j < i-1)
		{
			lchild = 2*j;
			rchild = 2*j+1;

			if((lchild < i) && (rchild < i))
			{
				if((array_to_sort[j] < array_to_sort[lchild]) && (array_to_sort[lchild] > array_to_sort[rchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[lchild]);
					j = lchild;
				}
				else if((array_to_sort[j] < array_to_sort[rchild]) && (array_to_sort[rchild] > array_to_sort[lchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[rchild]);
					j = rchild;
				}
				else
				{
					break;
				}
			}
			else if(lchild < i)
			{
				if((array_to_sort[j] < array_to_sort[lchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[lchild]);
					j = lchild;
				}
				else
				{
					break;
				}
			}
			else if(rchild < i)
			{
				if((array_to_sort[j] < array_to_sort[rchild]))
				{
					swap(&array_to_sort[j], &array_to_sort[rchild]);
					j = rchild;
				}
				else
				{
					break;
				}
			}
			else
			{
				break;
			}
		}
	}
}

void swap(int *num_1, int *num_2)
{
	int temp;
	temp = *num_1;
	*num_1 = *num_2;
	*num_2 = temp;
}