Introduction on Sorting in C++
Having a collection of elements to ordersorting helps in arranging the elements in the record based on ordering relation. Consider a file record that contains a lot of information. To access a list from the record, it is necessary to have a key field to point to the element’s current location. For example, consider a list of names on the database; it could be sorted alphabetically. Sorting placed an important role in the field of Computers and technology. Let us see more in this article.
What is the Sorting in C++?
Sorting is the basic concept used by the programmer or researcher to sort the inputs required. The order of complexity is given by 0(N*log(N)). Sorting an input makes it easier in solving many problems like Searching, Maximum and Minimum element. Although sorting arranges data in the sequence, the efficiency of the process is very important, which is based on two criteria: – Time and memory required to perform sorting on the given data. Time is measured by counting the comparisons of keys used. There are many algorithms available to sort.
In general, Sorting in C++ are distinguished into two types:
- Internal Sorting
- External Sorting
Syntax and Example
Syntax:
C++ uses sort () built-in function for their algorithms to sort the containers like vectors, arrays.
Sort(array , array +size);
Examples:
#include<iostream>
using namespace std;
int main ()
{
int ins[12] = { 19,13,5,27,1,26,31,16,2,9,11,21};
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
{
cout <<ins[i]<<"\t";
}
for(int k=1; k<12; k++)
{
int t = ins[k];
int j= k-1;
while(j>=0 && t <= ins[j])
{
ins[j+1] = ins[j];
j = j-1;
}
ins[j+1] = t;
}
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
{
cout <<ins[i]<<"\t";
}
}
Output:
How does it Work?
To start with, we will take Quick Sort, which is considered an important method among various sorting types. The basic sorting of an array takes a Quicksort approach. There are different ways to implement sorting, the aim of each of these techniques is the same as comparing two elements and swapping them with the temporary variable. In this article, we shall discuss the most important sorting used for implementation. Following are:
4.5 (6,858 ratings)
View Course
There are Merge Sort, radix sort, tape sorting, which we may discuss later. First, we will go with Bubble sort.
1. Bubble Sort
Bubble sort is one of the simplest sort methods we can use it for applications. In this technique, successive swaps are made through the records to be sorted. At each step, it compares the key to the data and exchanges the elements if not in the desired order. Sorting is done with the adjacent elements at the time only one element is placed in the sorted place after a swap.
Example: Let us consider an unsorted array A[]={ 6,2,4,7,1}
| 6 | 2 | 4 | 7 | 1 |
| A[0] | A[1] | A[2] | A[3] | A[4] |
Step 1: Comparing A [0] > A [1], if condition is true swap the element (6>2) true, place 2 in A [0]. Similarly, all the steps take the same until the array becomes sorted.
Now the array is A [] = {2,6,4,7,1}
Step 2: 6 is compared with 4. As 6 is greater than 4. Therefore, 6 and 4 are swapped.
Now the array is A [] = {2,4,6,7,1}
Step 3: Element 6 is compared with 7. Since 6<2 and the elements are in ascending order, elements are not swapped.
The sorted array is A [] ={2,4,6,7,1}.
Continue the process until the array is sorted.
2. Insertion Sort
In this technique, we start with the second data element by assuming the first element is already sorted, and comparison is done with the second element, and the step is continued with the other subsequent element. It is necessary to have N-1 passes in an array of N elements to have a sorted element.
Consider an array A[] = { 8,3,6,1}
| 8 | 3 | 6 | 1 |
Step 1: The first element looks for the largest element in the array to swap. If it is larger, it remains the same and gets moved on to the second element; here, 8 is greater than all, no swap is made.
| 8 | 3 | 6 | 1 |
Step2: Swapping with the second element
| 3 | 8 | 6 | 1 |
Step3: Swapping with the third element
| 3 | 6 | 8 | 1 |
Step4: Swapping with the fourth element
| 1 | 3 | 6 | 8 |
3. Quick Sort
This technique follows the divide and conquers algorithm and is considered very efficient and quicker for huge arrays. They are divided into three subsections: a left, a right and the middle. The middle element has a single value, and it is named as the pivot. The mechanism goes like this, the element in the left segment should not have a key larger than the middle element and the no element in the right has a key that is smaller than that of the middle element. Now let’s start with an illustration of the process of sorting. Quicksort uses a recursive concept while sorting sub-part. The array is divided into subpart, again left and right segments are partitioned by conquering. Here in this example, considering the last element has a pivot, and the first element is assumed low. Consider an array element
| 49 | 22 | 11 | 16 | 56 | 30 |
Taking the rightmost element has the pivot element = 30
| 16 | 22 | 11 | 30 | 56 | 49 |
The element greater than the pivot is placed towards the left, smaller at the right.
| 16 | 22 | 11 | 56 | 49 |
The pointer is placed at the pivot and is partitioned around a pivot.
| 11 | 22 | 16 | 56 | 49 |
The subparts are sorted individually.
| 11 | 16 | 22 | 30 | 49 | 56 |
Finally, we got a Sorted Array.
4. Selection Sort
This technique is also called exchange sorting performs dual operation searching and sorting. The implementation takes straight selection sorting as defined below. Here, it is required to identify the smallest element present in the array, and this element is sorted in the first ith position; next, the second smallest element is identified, and it is sorted in the second position. The selection sort exits its loop when the unsorted subpart becomes empty. The time complexity is given as O(n2).
Consider the following array:
| 63 | 26 | 13 | 23 | 12 |
1. Finding the smallest element and place it at the beginning, and it is swapped with the position.
| 12 | 26 | 13 | 23 | 63 |
2. The second element, a [1], is identified compare with the minimum element and place it in the second position; similarly, the pass continues.
| 12 | 13 | 26 | 23 | 64 |
Final sorted output
| 12 | 13 | 23 | 26 | 64 |
Conclusion
To conclude, this article focussed on sorting concepts and their working mechanism. All these sorting techniques use parallel processing concepts. Sorting forms a core building block in structuring algorithms to solve the problems of data in the real world by sorting the set of values according to the requirements.
Recommended Articles
This is a guide to Sorting in C++. Here we discuss the Introduction and Syntax with examples along with How does it work. You can also go through our other suggested articles to learn more–
