11. Sorting

C++ sort function syntax

---

sort(startIterator, endIterator);

Where:

• startIterator - Points to the first element to sort
• endIterator - Points to one past the last element to sort

For an array, to sort the entire array, we need to pass the start and end + 1 pointers:

int arr[n]; // Array 
 
sort(arr, arr + n);

Here:

• arr: Points to first element of array
• arr + n: Points to one past the last element of array

We can also derive this as:

start = arr 
end = arr + (n - 1) // Last element
end + 1 = arr + n

Therefore:

sort(start, end + 1);
sort(arr, arr + (n-1) + 1);
sort(arr, arr + n);

So that statement breaks down the start and end pointers passed to sort function for an array.

Sorting an Arrays

---

• Sorting refers to arranging the elements of a container (like array or vector) in a logical order - ascending, descending etc.
• • The std::sort() algorithm from C++ standard library can sort elements in O(NlogN) time on average.
• std::sort() takes the array start and end positions. To sort the entire array:

std::sort(arr, arr + n);

• std::sort() internally uses compare functions to compare elements and reorder them. By default, it sorts in ascending order.

TIP

Inbuilt Sort function can’t be directly applied on 2D Arrays

#include <iostream>
#include <algorithm> // for sort
using namespace std;
 
// User-defined descending comparator 
bool desc(int a, int b) {
  return a > b;
}
 
// Print array 
void printArray(int arr[], int n) {
  for(int i = 0; i < n; i++) {
    cout << arr[i] << " "; 
  }
  cout << endl;
}
 
int main() {
 
  int arr[] = {5, 2, 8, 3, 6}; 
  int n = sizeof(arr)/sizeof(arr[0]);
 
  // Sort array in ascending order (default comparator)
  sort(arr, arr + n); 
  printArray(arr, n);
 
  // Sort array in descending order (custom comparator)
  sort(arr, arr + n, desc);
  printArray(arr, n);
  
  return 0;
}

Explanation:

• Includes required headers like <algorithm>
• Defines a print array function for clarity
• Custom descending comparator desc
• Sorts array first in ascending order (default sort)
• Then sorts again using desc comparator to sort descending
• Prints sorted array after each sort

Different Sorting Algorithms:

---

• Bubble Sort - O(N^2) time, compares adjacent elements and swaps them if required
• Insertion Sort - O(N^2) time, grows a sorted array from left to right
• Selection Sort - O(N^2) time, selects minimum/maximum from unsorted part and puts in sorted part
• Merge Sort - O(NlogN) time, divides array into parts and merges them
• Quick Sort - O(NlogN) time on average, picks a pivot and partitions the array around it
• Heap Sort - O(NlogN) time, can be implemented using heaps
• Counting Sort - O(N+k) time, works on integers within a specific range
• Radix Sort - O(N) time, sorts based on individual digits/characters

Comparators in Sorting

---

We can provide custom comparator functions to control the sorting logic of std::sort().

A comparator function takes two elements as arguments and returns a bool value - true if first element goes before second element when sorting.

Some ways to define custom comparators:

1. Function Pointer

bool desc(int a, int b) {
  return a > b; 
}
 
std::sort(arr, arr+n, desc);

2. Functor Class

struct Descending {
  bool operator()(int a, int b) {
    return a > b;
  }  
};
 
std::sort(arr, arr+n, Descending()); 

3. Lambda Function

std::sort(arr, arr+n, [](int a, int b){
  return a > b; 
});

4. Built-in Function Objects

Like std::greater<T> :

• Function object (functor) that compares elements in descending order
• Defined in <functional> header

std::sort(arr, arr+n, greater<int>()); // Descending sort 

Internally, greater<int>() implements:

bool operator()(int a, int b) {
  return b < a; 
}

We can use it for any data type like greater<string>(). Custom comparators give flexibility to customize sorting logic.

Example

---

Demonstrating the use of greater<int>() with std::sort():

#include <iostream>
#include <algorithm> // for sort 
using namespace std;
 
// Print function 
void print(int arr[], int n) {
  for(int i = 0; i < n; i++){
     cout << arr[i] << " ";  
  }
  cout << endl; 
}
 
int main() {
 
  int n;
  cin >> n;
  
  int arr[n];
  
  // Get array input
  for(int i=0; i<n; i++) {
    cin >> arr[i]; 
  }
 
  // Sort array in descending order  
  sort(arr, arr + n, greater<int>());
 
  // Print sorted array 
  print(arr, n);
  
  return 0;
}```