DATA STRUCTURES AND
ALGORITHMS
SCS 3102
George William
Kasaazi
Module 4: Sorting and Searching
Algorithms
• In this module, we address two of the most common problems in all
of computing:
• Searching
• Given a collection of data, find a specific item.
• Sorting
• Arrange a collection of data into a specific order.
• These two problems are deeply related. As we've seen, searching
becomes incredibly fast if the data is already sorted.
Searching Algorithm 1: Linear Search
• The "Brute Force" Method
• Start at the beginning and check every single element until you find the target
or reach the end.
• When to Use it
• When you have no information about the data. It might be unsorted.
• Analysis:
• Best Case: O(1) - The item is the first one you check.
• Worst Case: O(n) - The item is the last one, or not in the list at all.
• Average Case: O(n)
// C-Style Array Implementation
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; ++i) {
if (arr[i] == target) {
return i; // Return the index of the found
item
}
}
return -1; // Sentinel value indicating "not found"
Searching Algorithm 2: Binary Search
• The "Divide and Conquer" Method.
• CRITICAL PRE-REQUISITE
• The data MUST be sorted.
• Algorithm:
• Look at the middle element of the sorted collection.
• If it's the target, you're done.
• If your target is smaller, you can completely ignore the entire right half of the
collection.
• If your target is larger, you can ignore the entire left half.
• Repeat this process on the remaining half.
• Analysis: You cut the problem in half at every step. This is incredibly
efficient.
• Time Complexity: O(log n) for all cases (best, average, worst).
Binary Search C++ Implementation
// C-Style Array Implementation
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Avoids overflow vs. (low+high)/2
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1; // Search the right half
} else {
high = mid - 1; // Search the left half
}
}
return -1; // Not found
}
Introduction to O(n²) Sorting
Algorithms
• These are the simplest sorting algorithms to understand.
• They are generally inefficient for large datasets but are excellent for
learning the fundamentals of sorting.
• They typically involve nested loops, leading to their O(n²) time
complexity.
Sorting Algorithm 1: Bubble Sort
The Idea
Repeatedly step through the list, compare adjacent pairs of elements, and swap
them if they are in the wrong order. The largest unsorted elements "bubble" up to
their correct position at the end of the list with each pass.
[ 5, 1, 4, 2 ]
[ 1, 5, 4, 2 ] (Swap 5 and 1)
[ 1, 4, 5, 2 ] (Swap 5 and 4)
[ 1, 4, 2, 5 ] (Swap 5 and 2) --> Pass 1 complete. 5 is now sorted.
Analysis:
Time Complexity: O(n²). You have a loop that runs (n-1) times, and inside it,
another loop that runs approximately n times.
Space Complexity: O(1). It sorts in-place.
Bubble Sort C++ Implementation
#include <utility> // for std::swap
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
// The last 'i' elements are already in place
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
Bubble Sort Visualization
Sorting Algorithm 2: Insertion Sort
• The Idea:
• Mimics how many people sort a hand of playing cards. The array is conceptually divided into
two parts: a sorted sublist on the left and an unsorted sublist on the right. The algorithm
picks the first element from the unsorted part and "inserts" it into its correct position in the
sorted part.
• How it Works:
• Start with the second element (at index 1), as the first element is already a "sorted list of
one".
• Take this element (the key) and compare it with the elements to its left (in the sorted part).
• Shift all elements in the sorted part that are greater than the key one position to the right to
make space.
• Insert the key into the created gap.
• Repeat this process for all remaining elements in the unsorted part.
• Analysis:
• Time Complexity:
• Best Case: O(n) - This happens when the array is already sorted. The algorithm just makes one
comparison per element.
• Worst Case: O(n²) - This happens when the array is sorted in reverse order.
• Average Case: O(n²)
Insertion Sort Visualization
Insertion Sort C++ Implementation
#include <utility> // Not strictly needed, but good practice
void insertionSort(int arr[], int size) {
// Start from the second element (the first element is trivially
sorted)
for (int i = 1; i < size; ++i) {
int key = arr[i]; // The element to be inserted into the sorted
part
int j = i - 1; // The index of the last element in the
sorted part
// Move elements of arr[0..i-1] that are greater than the key
// one position to their right.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Place the key at its correct sorted position
arr[j + 1] = key;
}
}
Sorting Algorithm 3: Selection Sort
• The Idea
• The algorithm builds the sorted part of the array one element at a time. It
repeatedly selects the smallest (or largest) element from the remaining unsorted portion
and moves it to its correct sorted position.
• How it Works:
• The array is conceptually divided into a sorted part (initially empty, on the left) and an
unsorted part (the entire array, on the right).
• Find the index of the minimum element in the unsorted part.
• Swap that minimum element with the very first element of the unsorted part.
• This expands the sorted part by one element.
• Repeat this process for the remaining unsorted part until the entire array is sorted.
• Analysis:
• Time Complexity: O(n²) for Best, Worst, and Average cases. The algorithm's behavior
doesn't change based on the initial order of the data; it always needs to scan the entire
unsorted part to find the minimum element.
• Space Complexity: O(1). It is an in-place sort.
Selection Sort Visualization
Selection Sort C++ Implementation
#include <utility> // For std::swap
void selectionSort(int arr[], int size) {
// One by one, move the boundary of the unsorted subarray
for (int i = 0; i < size - 1; i++) {
// Find the index of the minimum element in the unsorted part
// (from arr[i] to arr[size-1])
int min_index = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element
// of the unsorted part (arr[i])
if (min_index != i) { // Small optimization: avoid swapping
with self
std::swap(arr[min_index], arr[i]);
}
}
Bubble, Insertion, & Selection sort
comparison
[Link]
The Need for Speed: Beyond O(n²)
• A O(n²) algorithm is acceptable for a few hundred or thousand items.
• For a million items (n=1,000,000), n² is a trillion (1,000,000,000,000)
operations. This could take hours or days.
• A O(n log n) algorithm for a million items is roughly 20 million
operations. This takes well under a second.
• The difference is astronomical.
Sorting Algorithm 4: Quick Sort
• The Idea
• It's a "Divide and Conquer" algorithm.
• Divide
• Pick an element from the array. This element is called the pivot. Rearrange the
array so that all elements smaller than the pivot come before it, and all
elements greater come after it. This step is called partitioning.
• Conquer
• Recursively apply the same Quick Sort logic to the two sub-arrays (the one with
smaller elements, and the one with larger elements).
• Combine
• No work needed! Because the partitioning is done in-place, the array is sorted
once the recursive calls finish.
• The key is the partition step.
Quick Sort Visualization
Quick Sort C++ Implementation
// This function partitions the array and returns the index of the pivot
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Simple strategy: pick the last element as the pivot
int i = low - 1; // Index of the smaller element
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot_index = partition(arr, low, high);
quickSort(arr, low, pivot_index - 1); // Recursively sort elements
before pivot
quickSort(arr, pivot_index + 1, high); // Recursively sort elements after
pivot
Quick Sort Analysis
• Average Case Time Complexity
• O(n log n). In the average case, the pivot will divide the array into two
roughly equal halves.
• Worst Case Time Complexity
• O(n²). This happens if the pivot is always the smallest or largest element
(e.g., if the array is already sorted and we pick the last element as the
pivot). This creates unbalanced partitions.
• Space Complexity
• O(log n) on average, for the recursive call stack.
Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - V
isuAlgo
Quick Sort Tutorials & Notes | Algorithms | HackerEarth