Scribd
Upload
20 views3 pages

Sorting

Sorts arrays using 4 different algorithms in C

Uploaded by

Sayak Mitra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
20 views3 pages

Sorting

Sorts arrays using 4 different algorithms in C

Uploaded by

Sayak Mitra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include<stdio.

h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX 100
int main()
{
int ar[MAX],n,i,ch;
while(true)
{
printf("Menu List \n");
printf("[Link] Sort \n");
printf("[Link] Sort \n");
printf("[Link] Sort \n");
printf("[Link] Sort \n");
printf("[Link]\n");
printf("Enter your choice: \n");
scanf("%d",&ch);//accepting the users' choice
if(ch<=4)
{
printf("Enter the size of the array:");
scanf("%d",&n);//accepts the order of the array
}
switch(ch)
{
case 1: fill_array(ar,n);
selection_sort(ar,n);//calls the function to perform
selection sort
printf("The Selection Sorted Array is :\n");//prints the
sorted array
print_array(ar,n);
break;
case 2: fill_array(ar,n);
bubble_sort(ar,n);//calls the function to perform
bubble sort
printf("The Bubble Sorted Array is :\n");//prints the sorted
array
print_array(ar,n);
break;
case 3: fill_array(ar,n);
insertion_sort(ar,n);//calls the function to perform
insertion sort
printf("The Insertion Sorted Array is :\n");//prints the sorted
array
print_array(ar,n);
break;
case 4: fill_array(ar,n);
quick_sort(ar,0,n-1);//calls the function to perform
quick sort
printf("The Quick Sorted Array is :\n");//prints the sorted
array
print_array(ar,n);
break;
case 5: printf("Exiting from the menu");
exit(0);//exiting from the program
default:printf("Sorry Wrong Choice: \n");//Default choice
}
}//end of loop
return 0;
}//end of method()
void selection_sort(int ar[],int n)//implements the selection sort
{
int i,j,min=0;
for(i=0;i<n-1;i++)
{
min=i;//Find the minimum element in unsorted array
for(j=i+1;j<n;j++)
{
if (ar[j]<ar[min])
min=j;
}
swapping(&ar[min],&ar[i]);//calls the swap function to swap the found
minimum element with the first element
}
}//end of method()
void bubble_sort(int ar[],int n)//implements the bubble sort
{
int i,j;
for(i=0;i<n-1;i++)
{
for (j=0;j<n-i-1;j++)
{
if (ar[j]>ar[j+1])//checks if the current element is greater than the
next element
swapping(&ar[j],&ar[j+1]);//calls the swap function to swap the
elements
}
}
}//end of method()
void insertion_sort(int ar[],int n)//implements the bubble sort
{
int i,j,temp;
for(i=1;i<n;i++)//sorts the array in ascending order
{
temp=ar[i];//holds index of current value
j=i-1;//holds index of previous index value
while(temp<ar[j]&&j>=0)
{
ar[j+1]=ar[j];
j--;//decrements j once it is sorted
}
ar[j+1]=temp;//value of temp is stored
}
}//end of method
void quick_sort(int ar[],int beg,int end)//implements the quick sort
{
int loc;
if (beg<end)
{
loc=partitions(ar,beg,end);//calls the partition function,for the partition
with the pivot
quick_sort(ar,beg,loc-1); //sorts the arrays using recursion before
partition
quick_sort(ar,loc+1,end);//sorts the arrays using recursion after
partition
}//end of if
}//end of method()
int partitions(int ar[],int beg,int end)//Places the pivot in its correct position
and places all smaller elements to left of pivot and larger to it's right
{
int pivot=ar[end];// takes the last element pivot
int i=beg-1,j; // Index of smaller element
for(j=beg;j<=end-1;j++)
{
if(ar[j]<=pivot)// If current element is smaller than or equal to pivot
{
i++; // increment index of smaller element
swapp(&ar[i],&ar[j]);//calls the functions to swap the elements
}
}//end of loop
swapping(&ar[i+1],&ar[end]);//calls the function to swap the elements
return(i+1);
}//end of method
void swapping(int*a,int*b)//swaps between two pointer variables
{
int t=*a;
*a=*b;
*b=t;
}//end of method()
void fill_array(int ar[],int n)
{
int i;
printf("Enter %d elements\n",n);
for(i=0;i<n;i++)
scanf("%d",&ar[i]);//accepts the array elements
printf("The Unsorted Array is :\n");
print_array(ar,n);
}//end of method()
void print_array(int ar[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",ar[i]);//prints the array
printf("\n");
}//end of method()

Common questions

Powered by AI

If the 'swapping' function was incorrectly implemented, it could lead to incorrect element placements during sorting operations, potentially causing the entire sorting procedure to fail. This would result in an unsorted array at the end of the approach, thus invalidating the reliability of the sorting algorithms used.

Selecting bubble sort over quick sort may be preferable in a scenario where the dataset is almost sorted or very small, as bubble sort can efficiently handle small or nearly ordered arrays with its simplicity and minimal overhead. Furthermore, bubble sort's stability can preserve the order of equal elements, an important consideration for certain datasets where order matters.

The 'print_array' function is included to display the contents of the array at various stages of the program, which is essential for verifying the correctness of the sorting operations. It helps in debugging by allowing the user to observe the array before and after sorting to ensure that sorting algorithms work as intended.

The insertion sort algorithm in the program sorts elements by iteratively taking each element and inserting it into its correct position in the sorted portion of the array to the left. It uses a temporary variable to hold the current value while it shifts larger elements to the right.

Both sorting algorithms rearrange elements to achieve a sorted array, but they take different approaches. Selection sort repeatedly finds the minimum element from the unsorted part and swaps it to the front, working through the array one step at a time. Quick sort uses a divide-and-conquer approach that partitions the array around a pivot, sorting recursively. While selection sort has a consistent time complexity of O(n^2), quick sort is more efficient on average with O(n log n), although its worst-case time complexity is also O(n^2)

The quick sort's implementation includes a recursion-based partitioning that dynamically alters based on input size and order, effectively segmenting and sorting any number of elements by dividing the array optimally at each step. Its adaptability to pivot choices and recursive approach allows it to handle different input sizes efficiently.

The 'partition' function is crucial within the quick sort algorithm. It selects a pivot element and reorganizes the array such that all elements less than the pivot are on the left and all greater elements are on the right. This is key to the algorithm's efficiency, allowing quick sort to use divide-and-conquer recursion, achieving an average time complexity of O(n log n)

Using a fixed array size (defined by 'MAX') limits the volume of data that can be processed by sorting algorithms in the program, potentially leading to inefficiencies when handling larger datasets as only arrays up to this predefined size can be sorted. Furthermore, it doesn't leverage dynamic memory allocation, which could adaptively handle varying data sizes.

The program implements selection sort by iterating over the array to find the minimum element in the unsorted part, then swapping it with the first unsorted element. The time complexity of selection sort is O(n^2) because it involves two nested loops iterating over the array.

In the program, bubble sort works by repeatedly iterating through the array and swapping adjacent elements if they are in the wrong order, moving the largest unsorted element to its correct position with each pass. Its practical limitation is the time complexity of O(n^2), making it inefficient for large datasets.

You might also like