Sort function in C++

Sorting Integral Data Types

In this type, you will use integral data types such as 1,2 and so on or in other words, the whole numbers. 

Example Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include #include #include #include Using namespace std; int main() { std::vector Vec{5,3,6,2,7,4,1,8,2,9}; std::sort(std::execution::par, Vec.begin(),Vec.end()); for(auto elm:Vec) { cout << elm << “ ”; } return 0; }

Output:

1 2 3 4 5 6 7 8 9Sorting user-defined data types

This type is an important one where you have a collection of objects depending on your class’s parameter.

If you want to sort all the objects in your array or vector, 

Example Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Point{ public: int x; int y; Point (int x=0, int y=0): x(x), y(y) {} bool operator < (const Point& p1){  return ( x+y ) < (p1.x + p1.y); } }; int main() { std::vector Vec {{1,2},{3,1},{0,1}}; std::sort (Vec.begin(), Vec.end()); for ( auto e: Vec) { Cout << e.x <<” “<< e.y << endl; } return 0; }

Explanation:

The class point is a user-defined data type. We used the ‘less than’ operator (“<”) in the form of operator overloading. A sort compares one element with another element, it takes one element and compares using ‘less than’ operator, and then it takes the next element. Consider “A” is an object of the class Point, and B is also the same class’s object. Since A

Consider ‘1’ and ‘2’ is an object, and ‘3’, and ‘1’ is an object. Now, the addition of ‘1’ and ‘2’ is ‘3’.  Furthermore, the addition of ‘3’ and ‘1’ is ‘4’.  While comparing, ‘3’ is less than ‘4’ so the objects ‘1’ and ‘2’ will be placed first, and the process goes on till it is sorted out.

Output: 

0 1

1 2

3 1 

Note: If you want to sort your objects or collection in descending order, then you have to overload the greater than the operator and give std::greater() as the third parameter in sort function.

Example:

Sort(Vec.begin(), Vec.end(), std::greater

()); 

Sort using a Function Object

This method uses a function object to sort. 

Example: 

1 2 3 4 5 6 7 8 9 10 11

struct{ bool operator () (int a, int b) const{ return a } } customLess; int main(){ std::vector Vec{5,4,6,7,3,2,8,1} std::sort(Vec.begin(), Vec.end().customLess); for(auto elm: Vec){ cout<< elm<<” “; }

Explanation:

‘customLess’ is a pointer that we use in this example. It is called within the round brackets as a function when it is called it gets redirected to the struct block, and the sort function begins.

Output:

1 2 3 4 5 6 7 8 

Sorting using the Lambda Expression

In this type, you will directly inject the function into the places where the object is called. You can use the function body directly instead of creating a separate function block to do the expression and calling it in the main function. We can directly add them to the main function itself.

Example Program:

1 2 3 4 5 6 7 8 9

int main() { std::vector Vec{5,4,7,6,2,8,9,1,3}; std::sort ( Vec.begin(), Vec.end(), [](int a, int b) { return a for (auto elm: Vec){ cout << elm << ” “; } return 0; }

Output:

1 2 3 4 5 6 7 8 9

Apart from using Sort () function, few other sorting methods are done manually by writing a code for it. These methods are mostly used in array sets.

These methods are:

1. 
   Bubble sort
   
2. 
   Insertion sort
   
3. 
   Selection sort 
   
4. 
   Merge sort
   
5. 
   Quicksort
   
6. 
   Heapsort
   

Let’s see a few of the sorting methods.

1. Insertion Sort

Insertion sort is a simple in-place comparison-based sorting algorithm.

It maintains a sub-array (sub-list) which is always sorted and is built one element at a time. It selects each element and inserts it at its sorted position in the sorted sub-array. 

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void insertionSort( int A[],int n) { int i,value, index; for(i=1;i { value = A[i]; index=i; while(index>0 && A[index-1] { A[index]=A[index-1]; index=index-1; } A[index]=value; } }

Explanation:

Considering an array named A, it holds six elements as such 

5

2

3

1

6

4

We know that the index number always starts from 0.

We start with the first element. Initially, the sorted sub-array has 0 elements. When we insert the first element, it will be placed in the sorted position. It selects each element one by one. The variable “i’ is useful for transversal within the array.Also, we use the variables “value” and “index” . Value is used to store the value of the selected element, and the index is used to insert the element in a sorted sub-array. The variable “index” contains the index of the selected element. Each element in array A is compared with the elements in the sorted sub-array. After each comparison, it shifts all the greater elements than the selected element to one position to the right. Then it inserts the selected element at its sorted position. This process repeats till the array is sorted.

2. Bubble Sort

Bubble sort is a simple comparison-based algorithm, where each pair of adjacent elements are compared and swapped if they are not in the right position.

Example Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

void Bubblesort (int A[[], int n) { int k, i, temp, flag; For ( k=1;k { Flag =0; For (i=0; i< n-k; i++) { If (A[i]>A[i+1]) { temp=A[i]; A[i]=A[i+1}; A[i+1]=temp; flag=1; } } if(flag==0) break; } }

Explanation:

N is the number of elements in the array, K represents the past number where the range of K is 1to n-1. The elements are compared with the adjacent elements starting from index number 0 till index “n-k”, which means in every index, “n-k” comparison is made. After each comparison, if the left element is greater than the element on the right, their positions interchange or else it will move to the next pair. After each pass, the greater element will be added to its sorted position. This process is repeated till the array is sorted out.

3. Selection Sort

Selection sort is also a simple in-place comparison-based sorting algorithm.

Example Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int selectionSort (int A[], int n) { int i, j, small, temp; for(i=0;i { small=i; for (j=i+1; j< n; j++) { if (A[j] < A[small]) small=j; } temp=A[i]; A[i] =A[small]; A[small] =temp; } }

Explanation:

We divide the array of elements that require sorting into two sub-arrays: ‘Sorted’ (left) and ‘Unsorted’ (right). We consider the whole array as ‘unsorted’ in the beginning. The array is then sorted element by element. As the sorting happens, the sorted subarray’s size increases and the unsorted subarray size decreases. The leftmost element of the unsorted subarray is selected, and it gets swapped with the smallest element of the unsorted sub-array. 

To understand better, let’s see with an example.

3

2

5

1

4

Consider this array to be ‘unsorted’, we select the leftmost element in the ‘unsorted’ subarray using the variable “i”. We have to find the smallest element in the unsorted subarray and swap it with the leftmost element. To find the smallest element, we use the variable ‘small”. The variable “small” stores the index of the smallest element. It is then equated to “i”. 

Initially, “i” and “small” have the index 0 assigned to it. Another variable “j” is in usage to loop through the array to find the smallest element. At every iteration, there is a comparison of the value at “small” and the value at “j”. Suppose the value at “j’ is smaller than the value at “small”. In that case, the index of the element is stored in “small”. This process repeats till we reach the end of the array. 

We swap the value at “i” and “small”. Hence, the “small” value is stored, and it becomes part of the sorted sub-array. We repeat the procedure, over and over again, and each time we sort the value in “small”, the value of “I” increments by ‘1’ every time to select the leftmost element.

Final Output:

1

2

3

4

5