NUHMAN.com

Sorting and searching are fundamental tasks in computer science, and mastering efficient algorithms for both can significantly improve your coding skills. Sorting algorithms arrange elements in a specified order, while searching algorithms help you find specific elements in a dataset.

In this article, we'll cover three key algorithms:

1. Quick Sort – A divide-and-conquer algorithm for sorting.
2. Merge Sort – A stable divide-and-conquer algorithm for sorting.
3. Binary Search – A searching algorithm for sorted arrays.

1️⃣ Quick Sort

Quick Sort is a divide-and-conquer algorithm that works by selecting a pivot element from the array, partitioning the array around the pivot, and recursively sorting the two halves.

Quick Sort Algorithm:

1. Select a pivot element from the array.
2. Partition the array into two subarrays: one with elements less than the pivot and one with elements greater than the pivot.
3. Recursively apply the same procedure to the subarrays.

Python Code:

python

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Test Quick Sort
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # Output: [1, 1, 2, 3, 6, 8, 10]

Time Complexity:

• Best/Average: O(n log n)
• Worst: O(n²) (rare)

2️⃣ Merge Sort

Merge Sort is another divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.

Merge Sort Algorithm:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves into a single sorted array.

Python Code:

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    sorted_arr = []
    while left and right:
        if left[0] < right[0]:
            sorted_arr.append(left.pop(0))
        else:
            sorted_arr.append(right.pop(0))
    sorted_arr.extend(left or right)
    return sorted_arr

# Test Merge Sort
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # Output: [1, 1, 2, 3, 6, 8, 10]

Time Complexity:

• Best/Average/Worst: O(n log n)

3️⃣ Binary Search

Binary Search is an efficient searching algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.

Binary Search Algorithm:

1. Find the middle element.
2. If the target is equal to the middle element, return the index.
3. If the target is smaller, repeat the search on the left half.
4. If the target is larger, repeat the search on the right half.

Python Code:

python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found

# Test Binary Search
arr = [1, 2, 3, 6, 8, 10]
target = 6
index = binary_search(arr, target)
print(index)  # Output: 3 (index of 6)

Time Complexity:

• O(log n) for each search

📝 Summary

AlgorithmTypeTime Complexity (Best/Average/Worst)Quick SortSortingO(n log n) / O(n²)Merge SortSortingO(n log n) / O(n log n)Binary SearchSearchingO(log n)

Sorting and searching algorithms are crucial for solving various problems efficiently. By mastering Quick Sort, Merge Sort, and Binary Search, you'll be better equipped to tackle coding challenges, especially on platforms like LeetCode.