How is Insertion Sort in C done in C? How can the efficiency of sorting in C be measured?
The process of arranging items in ascending or descending order is called solution sorting.
People coined the term “sorting” after realizing how quickly finding things was vital.
Many things in life require us to look for them, such as a specific record in a database, roll numbers on a list, a phone number in a phone book, a particular page in a book, and so on.
The data would only be sorted or ordered if stored in a way that made it easier to find a specific item. But thankfully, the concept of sorting emerged, making it easier for everyone to put things in order.
To facilitate searching, data is organized logically.
Getting Stuff Done
If we want to put a deck of cards in order, we should check each card individually before putting the deck together.
Even though it takes a long time, we still put the deck together similarly. Computers, on the other hand, do not operate in this manner.
Scientists have been attempting to find a way to sort data using various algorithms since the dawn of the computer age and through sorting they have finally hit their aim .
Example
Following is the C program for sorting the data −
#include<stdio.h>
int main(){
int a[50], i,j,n,t,sm;
printf(“enter the No: of elements in the list:
“);
scanf(“%d”, &n);
printf(“enter the elements:
“);
for(i=0; i<n; i++){
scanf (“%d”, &a[i]);
}
for (i=0; i<n-1; i++){
sm=i;
for (j=i+1; j<n; j++){
if (a[j] < a[sm]){
sm=j;
}
}
t=a[i];
a[i]=a[sm];
a[sm]=t;
}
printf (“after selection sorting the elements are:
“);
for (i=0; i<n; i++)
printf(“%d\t”, a[i]);
return 0;
}
Output
When the above program is executed, it produces the following result −
enter the No: of elements in the list:
4
enter the elements:
34
12
56
7
after selection sorting the elements are:
7 12 34 56
Now let us discuss about the two main type of sorting in C –
- Selection Sort
- Insertion Sort
What is Selection Sort?
In C, you can use the selection sort algorithm to arrange a list of items in ascending or descending order.
In this method, the smallest item on the list replaces the first item. The second least important item on the list is also chosen, and it returns the first item on the list. It will keep rearranging the parts until the entire list is sorted somehow.
The selection sort in C is an in-place algorithm because it moves items around in the list. There is no need for a separate list or array to sort the elements.
You Must Like: Angular JS Interview: The Most Frequently Asked Questions Guide
C Selection Sort Algorithm/Pseudocode
The following is how the C Selection Sort algorithm works:
- Set a variable’s first value, such as “min index,” to array position 0.
- Search the entire array for the smallest element.
- When traversing the array, the two smaller elements are switched if a smaller element than the min index is found.
- Then, to point to the next array entry, add 1 to the min index.
- Repeat the previous step until the list is complete.
Insertion Sort in C
What is an insertion sort in C?
In C, the “insertion sort” method divides an array into parts that are already sorted and parts that aren’t. It then takes the appropriate values from the unsorted parts and places them in the proper locations in the sorted parts.
C Insertion Sort Algorithm/Pseudocode
Insertion Sort is a simple sorting algorithm in C that divides the array it is given into sorted and unsorted parts.
Technically, the insertion sort uses the following algorithm to put a list of sizes in order from smallest to largest:
1. Start at arr[1] and keep going through arr[n] until you reach arr[n].
2. Compare the current element (key) to its predecessor.
3. Compare the size of the essential element’s parts to the sizes of their predecessors. Move the larger elements up one position to accommodate the new element.
Insertion Sort in C Algorithm/Pseudo-code
- Take the first element and consider it to be a sorted part(a single element is always sorted)
- Now pick arr[1] and store it is a temporary variable
- Start comparing the values of tmp with elements of the sorted part from the rear side
- If tmp is less than the rear element, say arr[k], then shift arr[k] to k+1 index
- This shifting will continue until the appropriate location is identified. Then, we will put the temporary element at the identified location
- This will continue for all the elements, and we will have our desired sorted array in ascending order.
Conclusion
Therefore, through this article you will be able to get to know about how C language through its sorting programs is useful in Data Structures. After reading this article you will know the pseudocodes for insertion and selection sort using C language also you get to go through various programs of C using insertion and selection sort.
