Understanding Sorting Algorithms: A Guide to 12 Sorting Techniques with Pseudocode
Hey everyone, it’s alanturrr1703 back again! 😄 Today, we’re diving into a fundamental concept in computer science: Sorting Algorithms. Sorting is essential for organizing data, making searches faster, and optimizing various operations. In this blog, we’ll cover 12 popular sorting algorithms, explaining how they work with pseudocode for each.
Let’s dive in and understand how to sort like a pro! 🚀
1. Bubble Sort
Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.
Pseudocode for Bubble Sort:
Function BubbleSort(array):
n = length(array)
For i = 0 to n - 1:
For j = 0 to n - i - 2:
If array[j] > array[j + 1]:
Swap(array[j], array[j + 1])
Time Complexity:
- Best case: O(n) (already sorted)
- Worst case: O(n²)
2. Insertion Sort
Insertion Sort works by building a sorted portion of the array one element at a time. It takes each element from the unsorted portion and inserts it into the correct position in the sorted portion.
Pseudocode for Insertion Sort:
Function InsertionSort(array):
For i = 1 to length(array) - 1:
key = array[i]
j = i - 1
While j >= 0 and array[j] > key:
array[j + 1] = array[j]
j = j - 1
array[j + 1] = key
Time Complexity:
- Best case: O(n)
- Worst case: O(n²)
3. Selection Sort
Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element. It has a simple but inefficient approach.
Pseudocode for Selection Sort:
Function SelectionSort(array):
For i = 0 to length(array) - 1:
minIndex = i
For j = i + 1 to length(array) - 1:
If array[j] < array[minIndex]:
minIndex = j
Swap(array[i], array[minIndex])
Time Complexity:
- Best case: O(n²)
- Worst case: O(n²)
4. Merge Sort
Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges them into a sorted array.
Pseudocode for Merge Sort:
Function MergeSort(array):
If length(array) > 1:
mid = length(array) / 2
leftHalf = array[0:mid]
rightHalf = array[mid:length(array)]
MergeSort(leftHalf)
MergeSort(rightHalf)
i = j = k = 0
While i < length(leftHalf) and j < length(rightHalf):
If leftHalf[i] < rightHalf[j]:
array[k] = leftHalf[i]
i = i + 1
Else:
array[k] = rightHalf[j]
j = j + 1
k = k + 1
While i < length(leftHalf):
array[k] = leftHalf[i]
i = i + 1
k = k + 1
While j < length(rightHalf):
array[k] = rightHalf[j]
j = j + 1
k = k + 1
Time Complexity:
- Best case: O(n log n)
- Worst case: O(n log n)
5. Quick Sort
Quick Sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array into two halves. Elements smaller than the pivot go to the left, and those larger go to the right, and the process is repeated recursively.
Pseudocode for Quick Sort:
Function QuickSort(array, low, high):
If low < high:
pivotIndex = Partition(array, low, high)
QuickSort(array, low, pivotIndex - 1)
QuickSort(array, pivotIndex + 1, high)
Function Partition(array, low, high):
pivot = array[high]
i = low - 1
For j = low to high - 1:
If array[j] < pivot:
i = i + 1
Swap(array[i], array[j])
Swap(array[i + 1], array[high])
Return i + 1
Time Complexity:
- Best case: O(n log n)
- Worst case: O(n²)
6. Heap Sort
Heap Sort is based on a binary heap data structure. The array is first transformed into a max-heap, and then the largest element is repeatedly removed and placed at the end.
Pseudocode for Heap Sort:
Function HeapSort(array):
BuildMaxHeap(array)
For i = length(array) - 1 to 1:
Swap(array[0], array[i])
MaxHeapify(array, 0, i)
Function BuildMaxHeap(array):
For i = floor(length(array) / 2) - 1 to 0:
MaxHeapify(array, i, length(array))
Function MaxHeapify(array, i, n):
largest = i
left = 2 * i + 1
right = 2 * i + 2
If left < n and array[left] > array[largest]:
largest = left
If right < n and array[right] > array[largest]:
largest = right
If largest != i:
Swap(array[i], array[largest])
MaxHeapify(array, largest, n)
Time Complexity:
- Best case: O(n log n)
- Worst case: O(n log n)
7. Counting Sort
Counting Sort is a non-comparison-based algorithm. It works by counting the number of occurrences of each distinct element in the array, and then calculating the correct position for each element.
Pseudocode for Counting Sort:
Function CountingSort(array, maxVal):
count = array of zeros of size maxVal + 1
output = array of zeros of size length(array)
For i = 0 to length(array) - 1:
count[array[i]] = count[array[i]] + 1
For i = 1 to maxVal:
count[i] = count[i] + count[i - 1]
For i = length(array) - 1 down to 0:
output[count[array[i]] - 1] = array[i]
count[array[i]] = count[array[i]] - 1
Return output
Time Complexity:
- Best case: O(n + k)
- Worst case: O(n + k)
8. Radix Sort
Radix Sort sorts the array digit by digit, starting from the least significant digit and moving to the most significant digit. It uses counting sort as a subroutine.
Pseudocode for Radix Sort:
Function RadixSort(array, maxDigit):
For digit = 1 to maxDigit:
CountingSortByDigit(array, digit)
Function CountingSortByDigit(array, digit):
# Similar to Counting Sort but applied to the digit place
Time Complexity:
- Best case: O(nk)
- Worst case: O(nk)
9. Bucket Sort
Bucket Sort works by distributing elements into several buckets, sorting the elements in each bucket, and then merging the buckets.
Pseudocode for Bucket Sort:
Function BucketSort(array):
buckets = Create n empty buckets
For i = 0 to length(array) - 1:
index = floor(array[i] * n)
Insert array[i] into bucket[index]
For i = 0 to n - 1:
Sort each bucket
Concatenate all buckets into array
Time Complexity:
- Best case: O(n + k)
- Worst case: O(n²)
10. Shell Sort
Shell Sort is an optimization of insertion sort that allows the exchange of far-apart elements. It uses a gap sequence to divide the list into sublists and sorts them.
Pseudocode for Shell Sort:
Function ShellSort(array):
gap = length(array) / 2
While gap > 0:
For i = gap to length(array) - 1:
temp = array[i]
j = i
While j >= gap and array[j - gap] > temp:
array[j] = array[j - gap]
j = j - gap
array[j] = temp
gap = gap / 2
Time Complexity:
- Best case: O(n log n)
- Worst case: O(n
²)
11. Tim Sort
Tim Sort is a hybrid sorting algorithm based on merge sort and insertion sort. It is the default sorting algorithm in Python.
Pseudocode for Tim Sort:
Function TimSort(array):
Run = 32
For i = 0 to length(array) - 1 in steps of Run:
InsertionSort(array, i, min(i + Run - 1, length(array) - 1))
size = Run
While size < length(array):
For left = 0 to length(array) - 1 in steps of 2 * size:
mid = left + size - 1
right = min(left + 2 * size - 1, length(array) - 1)
Merge(array, left, mid, right)
size = size * 2
Time Complexity:
- Best case: O(n)
- Worst case: O(n log n)
12. Pigeonhole Sort
Pigeonhole Sort is used when the number of elements and the range of possible key values are approximately the same. It places elements into holes (or pigeonholes) corresponding to their key values.
Pseudocode for Pigeonhole Sort:
Function PigeonholeSort(array):
minVal = min(array)
maxVal = max(array)
size = maxVal - minVal + 1
holes = array of empty lists of size
For i = 0 to length(array) - 1:
holes[array[i] - minVal].append(array[i])
index = 0
For i = 0 to size - 1:
For each element in holes[i]:
array[index] = element
index = index + 1
Time Complexity:
- Best case: O(n + range)
- Worst case: O(n + range)
Wrapping It Up
In this blog, we’ve explored 12 popular sorting algorithms, ranging from simple ones like Bubble Sort to more complex algorithms like Tim Sort and Pigeonhole Sort. Each sorting algorithm has its strengths and weaknesses, and the choice of which to use depends on the specific requirements of your problem.
Sorting is a fundamental aspect of computer science, and understanding how these algorithms work will help you build more efficient solutions for organizing and processing data.
That’s all for today! I hope this post gave you a solid understanding of sorting algorithms and how to implement them. Until next time, happy coding! 🚀