Understanding Different Sorting Algorithms

1. Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Example:
Input: [5, 3, 2]
Output: [2, 3, 5]

Characteristics:

Simple to understand

Not efficient for large data

Time Complexity:
O(n²)

1. Selection Sort

Selection Sort selects the smallest element from the unsorted portion and places it at the correct position.

Example:
Input: [4, 2, 1]
Output: [1, 2, 4]

Characteristics:

Fewer swaps than Bubble Sort

Still inefficient for large inputs

Time Complexity:
O(n²)

1. Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting elements into their correct position.

Example:
Input: [5, 2, 4]
Output: [2, 4, 5]

Characteristics:

Efficient for small datasets

Works well for nearly sorted arrays

Time Complexity:
O(n²), but better in best case O(n)

1. Merge Sort

Merge Sort uses a divide-and-conquer approach:

Divide the array into halves

Sort each half

Merge them

Characteristics:

Very efficient and stable

Uses extra memory

Time Complexity:
O(n log n)

1. Quick Sort

Quick Sort selects a pivot and partitions the array into smaller and larger elements.

Characteristics:

Very fast in practice

In-place sorting

Worst case O(n²), average O(n log n)

1. Heap Sort

Heap Sort uses a binary heap structure:

Convert array into heap

Extract elements one by one

Characteristics:

No extra space required

Consistent performance

Time Complexity:
O(n log n)