Introduction on Sorting in C++
Having a collection of elements to order, sorting helps in arranging the elements in the record based on ordering relation. Consider a file record which contains a lot of information, to access a list from the record it is necessary to have a key field to point the current location of the element. 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 easier in solving many problems like Searching, Maximum and Minimum element. Although a 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:
There are Merge Sort, radix sort, tape sorting which we may discuss later. First, we will go with Bubble sort.
4.5 (3,249 ratings)
View Course
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. In an array of N elements, it is necessary to have N-1 passes 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 conquer algorithm and considered to be very efficient as well as 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 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 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 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 the 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–
