////////////////////////////////////////////////////////////////////////////////
// Program Name: DataStructureAlgorithm.c
// Description : This program shows the demonstration of all data structure
// algorithms.
// Author : Sunil V. Bhagwat
// Created Date : 15 August 2023
// Modified Date: 16 August 2023
////////////////////////////////////////////////////////////////////////////////
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
// CheckFor: Create new Array
void CreateArray(int A[], int n){
// CheckFor: Declaration of local variable
int i = 0;
// Checkfor: Accept the array elements
printf("Enter the array element: \n");
// LoopFor: Accepet the array elements
for ( i = 0; i < n; i++)
scanf("%d", &A[i]);
}
// CheckFor: Display the Array
void DisplayArray(int A[], int n){
// CheckFor: Declaration of local variable
int i = 0;
// Checkfor: Display the array elements
printf("The array elements are: \t");
// LoopFor: Display the array elements
for ( i = 0; i < n; i++)
printf("%d \t", A[i]);
}
// CheckFor: Sort the Array Element using Bubble Sort Algorithm
void BubbleSort(int A[], int n){
// CheckFor: Declaration of local variable
int i = 0, j = 0, temp = 0;
// LoopFor: Moving the Array from first to last element
for( i = 0; i < n; i++){
// LoopFor: Get element from unsorted array
// and check with sorted Array element
for( j = 0; j < n-i-1; j++){
// CheckFor: First element is greater than second
// if yes then swap the elements.
if ( A[j] > A[j+1]){
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
// CheckFor: Display the Sorted Array
printf("\n\nThe Sorted Array after Bubble Sort is: ");
for ( i = 0; i < n; i++)
printf("%d \t", A[i]);
}
// CheckFor: Sort the Array Element using Insertion Sort Algorithm
void InsertionSort(int A[], int n){
// CheckFor: Declaration of local variable
int i = 0, j = 0, key = 0;
// LoopFor: Moving the Array from first to last element
for( i = 1; i < n; i++){
// CheckFor: Assign the first element of unsorted array for the key
key = A[i];
// LoopFor: Check the accurate position of the key element.
for( j = i-1; (j >= 0) && (key < A[j]); j--){
A[j+1] = A[j];
}
// CheckFor: Place the accurate position of the key element.
A[j+1] = key;
}
// CheckFor: Display the Sorted Array
printf("\n\nThe Sorted Array after Insertion Sort is: ");
for ( i = 0; i < n; i++)
printf("%d \t", A[i]);
}
// CheckFor: Sort the Array Element using Selection Sort Algorithm
void SelectionSort(int A[], int n){
// CheckFor: Declaration of local variable
int i = 0, j = 0, loc = 0, min = 0, temp = 0;
// LoopFor: Moving the Array from first to last element
for ( i = 0; i < n-1; i++){
// CheckFor: Assign the minimum element of Array and location
min = A[i];
loc = i;
// LoopFor: Select the next minimum element from Array
for ( j = i+1; j < n; j++){
// CheckFor: Minimum element and change it and save its location
if ( min > A[j]){
min = A[j];
loc = j;
}
}
// CheckFor: Swap the the minimum element its correct position
temp = A[i];
A[i] = A[loc];
A[loc] = temp;
}
// CheckFor: Display the Sorted Array
printf("\n\nThe Sorted Array after Selection Sort is: ");
for ( i = 0; i < n; i++)
printf("%d \t", A[i]);
}
// CheckFor: Search the Array Element using Linear Search Algorithm
void LinearSearch(int A[], int n, int key){
// CheckFor: Declaration of local variable
int i = 0;
// LoopFor: Moving the Array from first to last element
for ( i = 0; i < n; i++){
// CheckFor: Key element match into the Array elements
// if Match then print the message
if ( key == A[i]){
printf("\n\nThe %d element search at %d position in Array", key, i+1);
}
}
// CheckFor: Key element does not found in Array
if ( i > n-1)
printf("\n %d element not found in Array\n", key);
}
// CheckFor: Search the Array Element using Sentinel Search Algorithm
void SentinelSearch(int A[], int n, int key){
// CheckFor: Declaration of local variable
int i = 0, last = A[n-1];
// CheckFor: Assign last element as a key
A[n-1] = key;
// LoopFor: Search the given key element into the Array
while ( A[i] != key)
i++;
// CheckFor: Reassign last element as a original value
A[n-1] = last;
// CheckFor: The given key is found in Array or not
if ( (i < n-1) || (key == A[n-1])){
printf("\n\nThe %d element search at %d position in Array", key, i+1);
}
else{
printf("\n %d element not found in Array\n", key);
}
}
// CheckFor: Search the Array Element using Binary Search Algorithm (Non-Recursive)
void BinarySearch(int A[], int n, int key){
// CheckFor: Declaration of local variable
int Lower_Bound = 0, Upper_Bound = 0, Mid_Element = 0;
// CheckFor: Assign the Upper_Bound
Upper_Bound = n - 1;
// LoopFor: Search the given key element into the Array
while ( Lower_Bound <= Upper_Bound){
Mid_Element = (Lower_Bound + Upper_Bound) / 2;
// CheckFor: The given key is found in Array or not
if (A[Mid_Element] == key){
printf("\n\nThe %d element search at %d position in Array", key, Mid_Element+1);
break;
}
else if ( key > A[Mid_Element])
// CheckFor: Set the lower bound of Array
Lower_Bound = Mid_Element + 1;
else if ( key < A[Mid_Element])
// CheckFor: Set the Upper bound of Array
Upper_Bound = Mid_Element - 1;
}
if(Lower_Bound > Upper_Bound)
printf("\nThe %d element does not found\n", key);
}
int main(){
int A[MAX], num = 0, key = 0, Choice = 0;
while(1){
printf("Enter your choice: \n 1. Create Array \n 2. Display Array \n 3. Bubble Sort \n 4. Insertion Sort \n 5. Selection Sort \n 6. Linear Search \n 7. Sentinel Seach \n 8. Binary Search \n 9. Exit \n");
scanf("%d", &Choice);
switch(Choice){
case 1:
printf("Enter How many element we want to in array: ");
scanf("%d", &num);
CreateArray(A, num);
break;
case 2:
DisplayArray(A, num);
break;
case 3:
BubbleSort(A, num);
break;
case 4:
InsertionSort(A, num);
break;
case 5:
SelectionSort(A, num);
break;
case 6:
printf("Enter element we want to search in array: ");
scanf("%d", &key);
LinearSearch(A, num, key);;
break;
case 7:
printf("Enter element we want to search in array: ");
scanf("%d", &key);
SentinelSearch(A, num, key);;
break;
case 8:
printf("Enter element we want to search in array: ");
scanf("%d", &key);
BinarySearch(A, num, key);;
break;
case 9:
exit(0);
}
}
system("pause");
return 0;
}