Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort
1. Bubble Sort
Concept:
Bubble Sort repeatedly compares adjacent elements in the array and swaps them if they are in
the wrong order. This process continues until no more swaps are needed, which means the
array is sorted.
How it works:
Compare each pair of adjacent elements.
If the first element is larger than the second, swap them.
After each full pass through the array, the largest element will "bubble up" to its
correct position.
Repeat the process for the unsorted portion of the array.
Example:
For an array arr[] = {5, 3, 8, 4, 2}:
1. First Pass:
o Compare 5 and 3, swap them → {3, 5, 8, 4, 2}
o Compare 5 and 8, no swap needed → {3, 5, 8, 4, 2}
o Compare 8 and 4, swap them → {3, 5, 4, 8, 2}
o Compare 8 and 2, swap them → {3, 5, 4, 2, 8}
2. Second Pass:
o Compare 3 and 5, no swap → {3, 5, 4, 2, 8}
o Compare 5 and 4, swap them → {3, 4, 5, 2, 8}
o Compare 5 and 2, swap them → {3, 4, 2, 5, 8}
3. Third Pass:
o Compare 3 and 4, no swap → {3, 4, 2, 5, 8}
o Compare 4 and 2, swap them → {3, 2, 4, 5, 8}
4. Fourth Pass:
o Compare 3 and 2, swap them → {2, 3, 4, 5, 8}
Now the array is sorted: {2, 3, 4, 5, 8}.
Time Complexity: O(n²)
2. Selection Sort
Concept:
Selection Sort divides the array into two parts: sorted and unsorted. It repeatedly selects the
smallest (or largest) element from the unsorted part and swaps it with the first unsorted
element, moving the boundary of the sorted part.
How it works:
Start with the first element and find the smallest element in the remaining unsorted
portion.
Swap the smallest element with the current element at the start of the unsorted part.
Move the boundary of the sorted section and repeat.
Example:
For an array arr[] = {5, 3, 8, 4, 2}:
1. First Pass:
o Find the smallest element in {5, 3, 8, 4, 2} → smallest is 2.
o Swap 2 with the first element → {2, 3, 8, 4, 5}.
2. Second Pass:
o Find the smallest element in {3, 8, 4, 5} → smallest is 3 (no change).
o No swap needed → {2, 3, 8, 4, 5}.
3. Third Pass:
o Find the smallest element in {8, 4, 5} → smallest is 4.
o Swap 4 with 8 → {2, 3, 4, 8, 5}.
4. Fourth Pass:
o Find the smallest element in {8, 5} → smallest is 5.
o Swap 5 with 8 → {2, 3, 4, 5, 8}.
Now the array is sorted: {2, 3, 4, 5, 8}.
Time Complexity: O(n²)
3. Insertion Sort
Concept:
Insertion Sort works by taking each element from the unsorted portion of the array and
inserting it into the correct position in the sorted portion. The sorted portion is built
incrementally.
How it works:
Start with the second element and compare it with the first.
If the second element is smaller, move the first element to the right and place the
second element in the correct position.
Repeat this process for each subsequent element.
Example:
For an array arr[] = {5, 3, 8, 4, 2}:
1. First Pass (insert 3):
o Compare 3 with 5, move 5 to the right → {5, 5, 8, 4, 2}
o Place 3 in the first position → {3, 5, 8, 4, 2}.
2. Second Pass (insert 8):
o 8 is already greater than 5, so no changes → {3, 5, 8, 4, 2}.
3. Third Pass (insert 4):
o Compare 4 with 8, move 8 to the right → {3, 5, 8, 8, 2}
o Compare 4 with 5, move 5 to the right → {3, 5, 5, 8, 2}
o Place 4 in the correct position → {3, 4, 5, 8, 2}.
4. Fourth Pass (insert 2):
o Compare 2 with 8, 5, 4, and 3, move all elements to the right → {3, 4, 5,
8, 8}
o Place 2 at the beginning → {2, 3, 4, 5, 8}.
Now the array is sorted: {2, 3, 4, 5, 8}.
Time Complexity: O(n²)
4. Merge Sort
Concept:
Merge Sort is a divide-and-conquer algorithm. It divides the array into two halves,
recursively sorts each half, and then merges the two sorted halves back together.
How it works:
Split the array into two halves until each subarray has only one element.
Merge the subarrays back together in sorted order.
Example:
For an array arr[] = {5, 3, 8, 4, 2}:
1. Divide the array into two halves:
o Left half: {5, 3, 8}
o Right half: {4, 2}
2. Recursively divide:
o Left: {5, 3, 8} → split into {5} and {3, 8}
o Right: {4, 2} → split into {4} and {2}
3. Merge:
o {3, 8} is merged into {3, 8}.
o {4, 2} is merged into {2, 4}.
4. Merge the two halves:
o Merge {5} and {3, 8} → {3, 5, 8}
o Merge {2, 4} with {3, 5, 8} → {2, 3, 4, 5, 8}.
Now the array is sorted: {2, 3, 4, 5, 8}.
Time Complexity: O(n log n)
5. Quick Sort
Concept:
Quick Sort is a divide-and-conquer algorithm. It selects a pivot element, partitions the array
into two parts based on the pivot (elements less than the pivot and elements greater than the
pivot), and recursively sorts the subarrays.
How it works:
Choose a pivot element.
Partition the array into two subarrays: elements less than the pivot and elements
greater than the pivot.
Recursively sort each subarray.
Example:
For an array arr[] = {5, 3, 8, 4, 2} and pivot 2 (last element):
1. Partition around the pivot 2:
o Elements less than 2: {} (none)
o Elements greater than 2: {5, 3, 8, 4}
o After partitioning: {2, 3, 8, 4, 5}
2. Recursively apply Quick Sort to {3, 8, 4, 5} with pivot 5:
o Partition around 5 → {3, 4} and {8}.
o After partitioning: {2, 3, 4, 5, 8}.
Now the array is sorted: {2, 3, 4, 5, 8}.
Time Complexity:
Worst-case: O(n²) (if the pivot is poorly chosen)
Best-case: O(n log n)
Summary:
Bubble Sort: Simple but inefficient for large datasets, repeatedly compares adjacent
elements.
Selection Sort: Repeatedly selects the smallest (or largest) element and places it in its
correct position.
Insertion Sort: Builds the sorted portion of the array by inserting each new element
into its correct position.
Merge Sort: A divide-and-conquer algorithm that splits the array, sorts the halves,
and merges them back together.
Quick Sort: A divide-and-conquer algorithm that selects a pivot, partitions the array,
and sorts the partitions.
An array is a data structure that stores a collection of elements, all of the same type, in a
contiguous block of memory. It allows you to store multiple values in a single variable,
instead of declaring separate variables for each value. Each element in the array is accessed
by an index or a key.
Key Characteristics of Arrays:
1. Fixed Size: When you declare an array, its size (the number of elements) is typically
fixed. It cannot be resized during runtime (in most programming languages, such as
C).
2. Homogeneous Data: All elements in an array must be of the same data type, like
integers, characters, or floats.
3. Indexing: Arrays use an index to access each element. The indexing usually starts at
0 (in languages like C, Java, Python, etc.).
4. Contiguous Memory Allocation: All elements are stored in adjacent memory
locations, which helps with efficient access and manipulation.