Comparator function of qsort() in C

In this article, you will learn about the comparator function ofthe qsort() function in C++ with different methods.

Introduction:

The qsort function in C is a standard library function used for sorting arrays. It takes four parameters: a pointer to the base of the array, the number of elements in the array, the size of each element, and a comparison function that is used to determine the order of elements.

Syntax:

It has the following syntax:

int compare(const void *a, const void *b);

The compare function takes two parameters, a and b, which are pointers to the elements being compared. The function should return an integer less than, equal to, or greater than zero if a is considered to be less than, equal to, or greater than b, respectively.

Program:

Let's take an example to illustrate the use of qsort() in C++:

#include <stdio.h>

#include <stdlib.h>

// Comparison function for qsort

int compare(const void *a, const void *b) {

 return (*(int*)a - *(int*)b);

}

int main() {

 // An array of integers

 int arr[] = {5, 2, 8, 1, 6};

 // Calculate the number of elements in the array

 int n = sizeof(arr) / sizeof(arr[0]);

 // Use sort to sort the array in ascending order

 qsort(arr, n, sizeof(int), compare);

 // Print the sorted array

 printf("Sorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Sorted array: 1 2 5 6 8

Explanation:

Header Files:

• #include <stdio.h>: It includes the standard input/output header file for basic I/O operations.
• #include <stdlib.h>: It includes the standard library header file for general utility functions, including memory allocation.

Comparison Function (compar):

• The compare function is a callback function used by the sort function for comparing elements during the sorting process.
• It takes two pointers (a and b) to elements and returns an integer.
• The compare function compares the values pointed to by a and b.
• The result of the comparison determines the order of elements:
• If the result is negative, a is considered less than b.
• If the result is zero, a is considered equal to b.
• If the result is positive, a is considered greater than b.

Main Function:

• An array of integers, arr, is declared and initialized.
• The variable n is calculated to determine the number of elements in the array.
• The qsort function is used to sort the array in ascending order:
• It takes the array, the number of elements, the size of each element, and the comparison function (compare) as arguments.
• After that, the sorted array is printed using a simple loop.
• The program concludes by returning 0 from the main Function.

Execution Result:

• When the program is executed, the output will display the sorted array in ascending order.

Complexity analysis:

Time Complexity:

• The time complexity of the provided code is dominated by the sorting operation performed by the sort function. The time complexity of qsort is generally O(n log n) on average, where "n" is the number of elements in the array.
• The comparison function (compare) is called multiple times during the sorting process, contributing to the overall time complexity. The exact number of comparisons depends on the sorting algorithm used by qsort.
• In the worst case, qsort could degrade to O(n^2) time complexity if a poor choice of pivots leads to inefficient partitioning.

Space Complexity:

• The space complexity of the code is primarily determined by the space required for the array of integers. Additionally, this sort of function may use additional space for its internal operations, depending on the implementation.
• The space complexity of the provided code is O(n), where "n" is the number of elements in the array. It is because the array requires O(n) space, and the space used by the qsort Function is typically O(log n) or O(n) in the worst case.

Method 1: Using Quicksort:

Divide and Conquer:

Quicksort is a divide-and-conquer algorithm. It divides the array into sub-arrays, recursively sorts these sub-arrays, and then combines them to obtain a sorted array.

The key step is the partitioning of the array, where a pivot element is chosen, and the array is rearranged such that elements smaller than the pivot are on its left, and elements greater than the pivot are on its right.

Partitioning:

The partitioning process is a critical step in Quicksort. It selects a pivot (often the last element in the array) and rearranges the elements such that elements smaller than the pivot come before it, and elements greater than the pivot come after it.

After that, the pivot is placed in its final sorted position.

Pivot Choice:

The choice of the pivot can affect the performance of Quicksort. In the code provided, the last element is chosen as the pivot. Other strategies include choosing the first element, a random element, or selecting the median of three elements to

Program:

Let's take an example to illustrate the use of comparator of qsort() using quicksort in C++:

#include <stdio.h>

//Function to partition the array and return the index of the pivot element

int partition(int arr[], int low, int high) {

 int pivot = arr[high];

 int i = (low - 1);

 for (int j = low; j <= high - 1; j++) {

 if (arr[j] < pivot) {

 i++;

 // Swap arr[i] and arr[j]

 int temp = arr[i];

 arr[i] = arr[j];

 arr[j] = temp;

 }

 }

 // Swap arr[i + 1] and arr[high] (pivot)

 int temp = arr[i + 1];

 arr[i + 1] = arr[high];

 arr[high] = temp;

 return (i + 1);

}

// Quicksort function

void quicksort(int arr[], int low, int high) {

 if (low < high) {

 // Find the partitioning index

 int pivotIndex = partition(arr, low, high);

 // Recursively sort the sub-arrays

 quicksort(arr, low, pivotIndex - 1);

 quicksort(arr, pivotIndex + 1, high);

 }

}

// Main Function to demonstrate Quicksort

int main() {

 int arr[] = {5, 2, 8, 1, 6};

 int n = sizeof(arr) / sizeof(arr[0]);

 printf("Original array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 // Apply Quicksort

 quicksort(arr, 0, n - 1);

 printf("\nSorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Original array: 5 2 8 1 6

Sorted array: 1 2 5 6 8

Explanation:

Partition Function:

• Partition function takes an array (arr), a low index (low), and a high index (high) as parameters.
• It selects the last element (arr[high]) as the pivot.
• It uses a loop to iterate through the array, placing elements smaller than the pivot to its left and elements greater than the pivot to its right.
• The partition function returns the index of the pivot after the partitioning.

Quicksort Function:

• Quicksort function takes an array (arr), a low index (low), and a high index (high) as parameters.
• It checks if the array has more than one element to sort (low < high).
• If so, it finds the partitioning index using the partition function and recursively applies quicksort to the left and right sub-arrays.

Main Function:

• It declares an array of integers (arr) and its size n.
• It prints the original array.
• It calls the quicksort function to sort the array.
• It prints the sorted array.

Complexity analysis:

Time Complexity:

Average Case: O(n log n)

Quicksort has an average-case time complexity of O(n log n), which makes it very efficient for large datasets. This average-case performance is achieved when the pivot choices are reasonably balanced, leading to roughly equal partitioning of the array.

Worst Case: O(n^2)

The worst-case time complexity of Quicksort is O(n^2). It occurs when the pivot choice consistently results in highly unbalanced partitions, such as always selecting the smallest or largest element as the pivot. Various techniques, including randomizing the pivot selection or using the median-of-three strategy, can help mitigate the likelihood of worst-case behavior.

Space Complexity:

Average Case: O(log n)

The average-case space complexity of Quicksort is O(log n) due to the recursive nature of the algorithm. The space required is proportional to the maximum depth of the recursive call stack.

Worst Case: O(n)

In the worst-case scenario, the space complexity of Quicksort can degrade to O(n), especially when the recursion depth becomes maximal. Each recursive call consumes space on the call stack, and in the worst case, it might lead to a stack size proportional to the size of the input array.

Method 2: Using Mergesort

Divide and Conquer:

Mergesort is a divide-and-conquer algorithm that breaks down the problem of sorting an array into smaller sub-problems. After that, it solves each sub-problem independently and combines the solutions to obtain the final sorted array.

Divide Step:

The array is recursively divided into two halves until each sub-array contains only one element. It is the base case for the recursion.

Conquer Step:

The conquer step involves sorting the individual sub-arrays. It is inherently sorted because each sub-array contains only one element at the base case.

Merge Step:

The merge step is the key operation in Mergesort. It involves merging two sorted sub-arrays to create a larger sorted array. This process is repeated until the entire array is merged.

Stable Sorting:

Mergesort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output as they were in the input.

Program:

Let's take an example to illustrate the use of the mergesort to sort an array in C++:

#include <stdio.h>

#include <stdlib.h>

// Merge two sub-arrays of arr[]

// First sub-array is arr[l..m]

// Second sub-array is arr[m+1..r]

void merge(int arr[], int l, int m, int r) {

 int i, j, k;

 int n1 = m - l + 1;

 int n2 = r - m;

 // Create temporary arrays

 int L[n1], R[n2];

 // Copy data to temporary arrays L[] and R[]

 for (i = 0; i < n1; i++)

 L[i] = arr[l + i];

 for (j = 0; j < n2; j++)

 R[j] = arr[m + 1 + j];

 // Merge the temporary arrays back into arr[l..r]

 i = 0;

 j = 0;

 k = l;

 while (i < n1 && j < n2) {

 if (L[i] <= R[j]) {

 arr[k] = L[i];

 i++;

 } else {

 arr[k] = R[j];

 j++;

 }

 k++;

 }

 // Copy the remaining elements of L[], if there are any

 while (i < n1) {

 arr[k] = L[i];

 i++;

 k++;

 }

 // Copy the remaining elements of R[], if there are any

 while (j < n2) {

 arr[k] = R[j];

 j++;

 k++;

 }

}

// Main Function to perform mergesort

void mergesort(int arr[], int l, int r) {

 if (l < r) {

 // Same as (l+r)/2, but avoids overflow for large l and r

 int m = l + (r - l) / 2;

 // Sort first and second halves

 mergesort(arr, l, m);

 mergesort(arr, m + 1, r);

 // Merge the sorted halves

 merge(arr, l, m, r);

 }

}

// Main Function to demonstrate Mergesort

int main() {

 int arr[] = {12, 11, 13, 5, 6, 7};

 int n = sizeof(arr) / sizeof(arr[0]);

 printf("Original array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 // Apply Mergesort

 mergesort(arr, 0, n - 1);

 printf("\nSorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Original array: 12 11 13 5 6 7

Sorted array: 5 6 7 11 12 13

Explanation:

Merge Function:

• Merge function takes an array (arr[]) and indices l, m, and r representing two sorted sub-arrays to be merged.
• It creates temporary arrays (L[] and R[]) to hold the values of the sub-arrays.
• After that, the merge function merges the two sub-arrays back into the original array in sorted order.

Mergesort Function:

• The mergesort function is the main recursive function for the Mergesort algorithm.
• It recursively divides the array into halves until the base case (single-element sub-arrays) is reached.
• After that, it recursively sorts and merges the sub-arrays until the entire array is sorted.

Main Function:

• It declares an array of integers (arr) and its size n.
• It prints the original array.
• It calls the mergesort Function to sort the array.
• It prints the sorted array.

Complexity analysis:

Time Complexity:

Average Case: O(n log n)

Mergesort consistently exhibits O(n log n) time complexity on average, making it efficient for a wide range of inputs.

Worst Case: O(n log n)

Mergesort's worst-case time complexity is also O(n log n), ensuring reliable performance even in scenarios where the input array is not well-behaved.

Best Case: O(n log n)

Unlike some other sorting algorithms, Mergesort does not have a separate best-case time complexity. It consistently performs well, regardless of the input distribution.

Space Complexity:

Additional Space (for Merging): O(n)

Mergesort requires additional space for merging, creating temporary arrays for each merging operation. The size of these temporary arrays is proportional to the size of the input array.

Total Space (including Input Array): O(n)

The total space complexity of Mergesort, including the input array and the additional space that is needed for merging, is O(n).

Method 3: Using Bubble Sort:

Simple Comparison and Swapping:

Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Repeated Passes:

The algorithm makes multiple passes through the array, with each pass comparing and swapping adjacent elements as necessary.

Stable Sorting:

Bubble Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output as they were in the input.

Inefficient for Large Datasets:

While easy to understand and implement, Bubble Sort is generally inefficient for large datasets compared to more advanced sorting algorithms such as Quicksort or Mergesort.

Program:

Let's take an example to illustrate the use of bubblesort to sort an array in C++:

#include <stdio.h>

//Function to perform Bubble Sort

void bubbleSort(int arr[], int n) {

 for (int i = 0; i < n - 1; i++) {

 for (int j = 0; j < n - i - 1; j++) {

 // Compare adjacent elements and swap if they are in the wrong order

 if (arr[j] > arr[j + 1]) {

 // Swap arr[j] and arr[j + 1]

 int temp = arr[j];

 arr[j] = arr[j + 1];

 arr[j + 1] = temp;

 }

 }

 }

}

// Main Function to demonstrate Bubble Sort

int main() {

 int arr[] = {64, 34, 25, 12, 22, 11, 90};

 int n = sizeof(arr) / sizeof(arr[0]);

 printf("Original array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 // Apply Bubble Sort

 bubbleSort(arr, n);

 printf("\nSorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Original array: 64 34 25 12 22 11 90

Sorted array: 11 12 22 25 34 64 90

Explanation:

Bubble Sort Function (bubbleSort):

• The outer loop (for i) represents each pass through the array, and the inner loop (for j) compares and swaps adjacent elements within that pass.
• If an element at position j is greater than the element at position j + 1, the two elements are swapped.

Main Function:

• It declares an array of integers (arr) and its size n.
• It prints the original array.
• It calls the bubbleSort Function to sort the array.
• It prints the sorted array.

Complexity analysis:

Time Complexity:

Average Case: O(n^2)

In the average case, Bubble Sort compares and swaps elements in a quadratic fashion, resulting in a time complexity of O(n^2).

Worst Case: O(n^2)

The worst-case time complexity occurs when the array is sorted in reverse order, and every element needs to be compared and swapped in each pass, resulting in O(n^2) comparisons and swaps.

Best Case: O(n)

The best-case time complexity occurs when the array is already sorted. In this case, Bubble Sort still makes passes through the array, but no swaps are needed. The number of comparisons is still O(n), resulting in a best-case time complexity of O(n).

Space Complexity:

Additional Space: O(1)

Bubble Sort is an in-place sorting algorithm, meaning that it doesn't require additional space proportional to the input size. It only uses a constant amount of additional space for temporary variables, regardless of the size of the input array.

Method 4: Using Insertion Sort

Incremental Building:

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time.

It iterates through the input array, takes one element at a time from the unsorted part, and inserts it into its correct position in the sorted part.

Comparisons and Shifting:

For each element taken from the unsorted part, it is compared with the elements in the sorted part to find its correct position.

If the element is smaller (or larger, depending on the sorting order) than the compared element, it is shifted to make room for the new element.

Stable Sorting:

Insertion Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output as they were in the input.

Efficient for Small Datasets:

While Insertion Sort has a quadratic time complexity; it is efficient for small datasets or nearly sorted datasets.

Program:

Let's take an example to illustrate the use of the insertion sort to sort an array in C++:

#include <stdio.h>

//Function to perform Insertion Sort

void insertionSort(int arr[], int n) {

 int i, key, j;

 for (i = 1; i < n; i++) {

 key = arr[i];

 j = i - 1;

 // Move elements greater than key to one position ahead of their current position

 while (j >= 0 && arr[j] > key) {

 arr[j + 1] = arr[j];

 j = j - 1;

 }

 // Insert the key into its correct position

 arr[j + 1] = key;

 }

}

// Main Function to demonstrate Insertion Sort

int main() {

 int arr[] = {12, 11, 13, 5, 6};

 int n = sizeof(arr) / sizeof(arr[0]);

 printf("Original array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 // Apply Insertion Sort

 insertionSort(arr, n);

 printf("\nSorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Original array: 12 11 13 5 6

Sorted array: 5 6 11 12 13

Explanation:

Insertion Sort Function (insertionSort):

• The insertionsort function iterates through the array starting from the second element (i = 1).
• For each element, it compares it with the elements in the sorted part of the array and inserts it into its correct position by shifting the larger elements.

Main Function:

• It declares an array of integers (arr) and its size n.
• It prints the original array.
• It calls the insertionSort Function to sort the array.
• It prints the sorted array.

Complexity analysis:

Time Complexity:

Average Case: O(n^2)

In the average case, Insertion Sort compares and shifts elements in a quadratic fashion, resulting in a time complexity of O(n^2).

Worst Case: O(n^2)

The worst-case time complexity occurs when the array is sorted in reverse order, and every element needs to be compared and shifted in each pass, resulting in O(n^2) comparisons and shifts.

Best Case: O(n)

The best-case time complexity occurs when the array is already sorted. In this case, Insertion Sort still makes passes through the array, but no shifting is needed. The number of comparisons is still O(n), resulting in a best-case time complexity of O(n).

Space Complexity:

Additional Space: O(1)

Insertion Sort is an in-place sorting algorithm, meaning that it doesn't require additional space proportional to the input size. It only uses a constant amount of additional space for temporary variables, regardless of the size of the input array.

Method 5: Using Selection Sort

Divide into Sorted and Unsorted Regions:

Selection Sort divides the array into two regions: a sorted region and an unsorted region.

The sorted region starts as empty, and the unsorted region contains all the elements.

Select and Swap:

The algorithm iteratively selects the smallest (or largest, depending on the desired sorting order) element from the unsorted region and swaps it with the first element of the unsorted region.

Repeated Process:

This process is repeated until the entire array is sorted. In each iteration, the size of the sorted region increases, and the size of the unsorted region decreases.

In-Place Sorting:

Selection Sort is an in-place sorting algorithm, meaning that it doesn't require additional space proportional to the input size.

Stable Sorting:

Selection Sort is not a stable sorting algorithm, as the relative order of equal elements may change during the sorting process.

Program:

Let's take an example to illustrate the use of the selectionsort method to sort an array in C++:

#include <stdio.h>

//Function to perform Selection Sort

void selectionSort(int arr[], int n) {

 int i, j, min_idx;

 // One by one move the boundary of the unsorted region

 for (i = 0; i < n - 1; i++) {

 // Find the minimum element in the unsorted region

 min_idx = i;

 for (j = i + 1; j < n; j++) {

 if (arr[j] < arr[min_idx]) {

 min_idx = j;

 }

 }

 // Swap the found minimum element with the first element of the unsorted region

 int temp = arr[min_idx];

 arr[min_idx] = arr[i];

 arr[i] = temp;

 }

}

// Main Function to demonstrate Selection Sort

int main() {

 int arr[] = {64, 25, 12, 22, 11};

 int n = sizeof(arr) / sizeof(arr[0]);

 printf("Original array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 // Apply Selection Sort

 selectionSort(arr, n);

 printf("\nSorted array: ");

 for (int i = 0; i < n; i++) {

 printf("%d ", arr[i]);

 }

 return 0;

}

Output:

Original array: 64 25 12 22 11

Sorted array: 11 12 22 25 64

Explanation:

Selection Sort Function (selectionSort):

• The outer loop (for i) represents the boundary between the sorted and unsorted regions. It iterates from the beginning to the second-to-last element.
• The inner loop (for j) finds the index of the minimum element in the unsorted region.
• After that, the minimum element is swapped with the first element of the unsorted region.

Main Function:

• It declares an array of integers (arr) and its size n.
• It prints the original array.
• It calls the selectionSort function to sort the array.
• It prints the sorted array.

Complexity analysis:

Time Complexity:

Average Case: O(n^2)

In the average case, Selection Sort performs nested loops, resulting in a quadratic time complexity.

Worst Case: O(n^2)

The worst-case time complexity also occurs when the array is sorted in reverse order, as the algorithm makes the same number of comparisons and swaps in each iteration.

Best Case: O(n^2)

Unlike some other sorting algorithms, Selection Sort doesn't have a separate best-case time complexity. It consistently performs the same number of comparisons and swaps, regardless of the initial order of the elements.

Space Complexity:

Additional Space: O(1)

Selection Sort is an in-place sorting algorithm. It doesn't require additional space proportional to the input size. The only additional space used is for a constant number of temporary variables, making the space complexity O(1)