The sorting algorithms are widely used in computer science; it helps in arranging elements in order and also helps with many problems faced while writing the code. Sorting algorithms help in manipulating the data, which makes things easy for us. In this article, we will learn about Sorting in C++ and also about different sorting algorithms.
What Is Sorting in C++?
Sorting in C++ is a concept in which the elements of an array are rearranged in a logical order. This order can be from lowest to highest or highest to lowest. Sorting an unsorted array helps to solve many problems such as searching for the minimum or maximum element, etc.
Arranging things in a sorted manner makes it easier to analyze and search for a particular element among the collection of elements.
For example, In the below example, we are sorting or arranging the elements of an unsorted array in ascending order, i.e., from lowest to highest.
Let's understand categories of sorting in C++.
Categories of Sorting in C++
The categories of sorting are:
- Internal sorting
- External sorting
We know that all the programs are stored inside the hard disk, and whenever we run a program in C++, it comes to the RAM.
In internal sorting, the data to be sorted is present in the main memory or RAM, and sorting process will also occur in the main memory itself. Examples of internal sorting are bubble sort, insertion sort, selection sort.
While in the case of external sorting, the data is not always present in the RAM because the data is large. So data is filled in the RAM or main memory in small portions. An example of external sorting is the Merge sort.
Now let's understand types of sorting in C++.
Types of Sorting Techniques
There are various types of sorting techniques in C++. We will be learning the most popular ones in this article.
- Bubble sort
- Selection sort
- Insertion sort
- Quick sort
Bubble Sort
Bubble sort is one of the most straightforward sorting algorithms. In this sorting technique, we begin by comparing the first two elements of the array and checking if the first element is greater than the second element; if it is, we will swap those elements and move forward to the next element.
If the first element is not greater than the second, then we don’t need to swap it. And this process will keep on repeating till the end of the array.
Now let’s have a look at an example of Bubble sort.
As we can see in the above example, we have an unsorted array containing elements
12, 3, 1, 5, 18, 10, 7 and 35. Two for loops are used to sort this array, the first for loop is iterating from 0 to 8, and the second is repeating from i+1 to 8. When i is at 0, then j will be at 0+1, i.e., index 1, so the comparison will occur between the element at index1 and element 0.
Inside the for loops, there is an if statement which states that if arr[j] is less than arr[i], then swapping will occur, i.e., if the element at index1 is less than the index 0 element, then the swapping will take place. Similarly, one by one, each element will be compared with the next element, and it will proceed till the end.
This is the output.
Selection Sort
In selection sorting technique, the smallest element is fetched by comparing itself with the rest of the elements and sorted at the array's first position. The complete array is divided into two halves, the sorted subarray on the left and the unsorted subarray on the right. Once the first element is sorted, the search for the second minimum element begins from the rest of the array and is positioned at second place.
Similarly, all the elements are positioned on the sorted side of the subarray one after the other, and the complete array becomes a sorted array.
Let’s have a look at an example of the Selection sort.
As we can see in the example, we have taken the input of the array from the user. These array elements are unsorted. So by using selection sort, we will sort these array elements.
The first for loop will iterate from 0 to num-1. Inside the for loop block, the first element is assigned to this min variable and the element's index to the P variable.
After that, another for loop is used to iterate from j+1 to num. Inside the for loop, there is an if statement that states that if arr[j] is less than the min element, we will assign that element to the min variable, and similarly, we will assign the index of that element to P.
As the index is assigned to P, so we will swap arr[i] with arr[P]. Once swapping is done, we will print the sorted array.
Insertion Sort
In this sorting technique, the elements are sorted by comparing the elements with their previous elements. It starts by comparing the second element with the first element. If the second element is smaller than the first, then we will swap it.
After that, we will compare the third element with all the elements that are before it. Similarly, it goes for the fourth element and so on. Once all the comparisons are made, the elements become sorted.
In this example, we are taking an array as input from the user. After taking the input, a for loop is used, which is iterating from 1 to num-1; the loop starts from 1 because the comparison will start from index 1.
Inside the for loop, the array element is copied to the temp variable, and j is set i-1 because we have to compare the element with its previous element.
Inside the while loop, there's a condition if the temp is less than arr[j], that means if temp which is storing the index 1 element is less than arr[j], which is index 0 element, then we will put arr[j] into its correct position, i.e., arr[j+1].
j=j-1 is used for decrementing the loop, as per the condition j must be greater than 0.
Then we will put the element at its correct position by assigning temp to the arr[j+1].
Quick Sort
The quicksort algorithm is the most widely used algorithm and the most efficient sorting algorithm. It works on the divide and conquer approach, i.e., the array is divided into subarrays, and when these subarrays are sorted, they are combined to form a complete sorted array.
In this approach, a pivot element is selected, and the array is partitioned into two halves based on the pivot element. The elements that are smaller than the pivot element are shifted to the left side of it, and the elements greater than the pivot element are moved to the right side.
For example:
Now let's have a look at an example of Quick sort.
Here, in this example after taking the array as an input from the user, we are passing the array along with its first index 0 and its last index num-1 to the Quick function.
Inside the Quick function, there is an if condition which states that if the start index is less than the end index, which means if the array has more than one element, then only the if block will execute. Inside the if block, there is a call to the divide function, and start index and end index are passed as arguments.
Inside this divide function, the last element is assigned to the pivot element. Typically, the last element is selected as the pivot, and the start index is given to the index variable. Inside the for loop, an if condition states that if the element is less than the pivot element, swap it to the left. We are swapping arr[i] with arr[index], which is the first element.
Once it’s done, we will position the partition point by swapping arr[end] with arr[index], and by returning the index, we will return the position of partition or division. Then with the help of d(the point of division), we will call the Quick function recursively to sort the subarrays.
Below is the output.
So using all of these techniques, we can perform sorting in C++.
Sorting Using C++ Library
We can also sort using the C++ library. To use that library function, we must include the #include<algorithm> header file.
The below function compares every element within the range.
The syntax of the function is sort; then, there will be a starting iterator and the ending iterator within the brackets.
Earn upto 25 CEUs from Caltech CTME and score a new job with an average annual package of 9-10 L after completing the PGP in Full Stack Web Development. Enroll Today!
Conclusion
After reading this article on sorting in C++, you would have understood What is sorting?, the categories of sorting in C++, and the types of sorting techniques like bubble sort, insertion sort, quick sort etc. You also learned how to sort using the C++ library and also understood the practical aspect of the sorting techniques with the help of examples.
If you are looking to build a career in software development, check the Post-Graduate Program in Full Stack Development by Simplilearn. It can prove to be the ideal solution to help you build your career in the right direction.
Do you have any questions regarding this tutorial on Sorting in C++? If you do, then put them in the comments section. We’ll help you solve your queries. To learn more about Sorting in C++, click on the following link: Sorting in C++
