Sorting and Searching Algorithms Using C++
Sorting and searching are fundamental concepts in computer science and are commonly
used in a variety of applications. Sorting algorithms are designed to rearrange data into a
specific order, such as ascending or descending, while searching algorithms are used to find
specific elements within a collection of data. In this lecture, we will discuss popular sorting
and searching algorithms, including their implementation in C++, followed by a comparison
of their performance.
Sorting Algorithms
Sorting is the process of arranging elements in a list or array in a specific order. Below are
some of the most common sorting algorithms:
1. Bubble Sort
Bubble Sort is a simple algorithm that repeatedly steps through the list, compares adjacent
elements, and swaps them if they are in the wrong order. This process is repeated until the
list is sorted.
Bubble Sort C++ Code:
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Time Complexity:
• Best Case: O(n)
• Average Case: O(n^2)
• Worst Case: O(n^2)
2. Selection Sort
Selection Sort works by selecting the minimum element from the unsorted part of the list
and swapping it with the first unsorted element. This process is repeated for each
subsequent element.
Selection Sort C++ Code:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[min_idx], arr[i]);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Time Complexity:
• Best Case: O(n^2)
• Average Case: O(n^2)
• Worst Case: O(n^2)
3. Insertion Sort
Insertion Sort builds the final sorted array one element at a time. It takes each element from
the unsorted part and places it in the correct position in the sorted part.
Insertion Sort C++ Code:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Time Complexity:
• Best Case: O(n)
• Average Case: O(n^2)
• Worst Case: O(n^2)
4. Quick Sort
Quick Sort is a divide-and-conquer algorithm. It selects a 'pivot' element from the array and
partitions the other elements into two sub-arrays, according to whether they are less than
or greater than the pivot. The sub-arrays are then sorted recursively.
Quick Sort C++ Code:
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Time Complexity:
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n^2)
5. Merge Sort
Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts each
half, and then merges the sorted halves back together.
Merge Sort C++ Code:
#include <iostream>
using namespace std;
void merge(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge(arr, left, mid);
merge(arr, mid + 1, right);
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
merge(arr, 0, n-1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Time Complexity:
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)
Comparison of Sorting Algorithms
Algorithm Best Case Average Case Worst Case Space Complexity Stable
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Searching Algorithms
Searching algorithms are used to find a specific element in a list. Below are the most
common searching algorithms:
1. Linear Search in C++
Linear Search is a simple algorithm that sequentially checks each element of the list
until the target element is found or the end of the list is reached.
Linear Search C++ Code:
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return the index if target is found
}
}
return -1; // Return -1 if target is not found
}
int main() {
int arr[] = {12, 34, 23, 56, 89, 45, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 56;
int result = linearSearch(arr, n, target);
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
Explanation:
• This program searches for the element 56 in the array.
• If the element is found, it returns the index of the element; otherwise, it returns
-1.
Time Complexity:
• Best Case: O(1) (if the element is at the beginning)
• Worst Case: O(n) (if the element is at the end or not in the list)
• Average Case: O(n)
2. Binary Search in C++
Binary Search is more efficient than Linear Search but requires the array to be sorted.
It works by dividing the array into two halves and eliminating half of the search space
at each step.
Binary Search C++ Code:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if target is at mid
if (arr[mid] == target) {
return mid; // Return the index if target is found
}
// If target is smaller, ignore right half
if (arr[mid] > target) {
high = mid - 1;
}
// If target is larger, ignore left half
else {
low = mid + 1;
}
}
return -1; // Return -1 if target is not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 60;
int result = binarySearch(arr, n, target);
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
Explanation:
• This program searches for the element 60 in the sorted array.
• If the element is found, it returns the index of the element; otherwise, it returns
-1.
Time Complexity:
• Best Case: O(1) (if the middle element is the target)
• Worst Case: O(log n) (if the search space is halved each time)
• Average Case: O(log n)