🔼 DSA using Python: Sorting 🔽

 Follow me

"Learn all major sorting algorithms in Data Structures using Python with simple examples, syntax, and practical explanations for beginners."

🧠 Definition: Sorting in DSA

Sorting is the process of arranging data (numbers, strings, or objects) in a specific order — typically ascending or descending. Sorting makes it easier to search, analyze, and organize data efficiently.

💡 Example:

Imagine you have a list of students and their marks:

students = [("Amit", 85), ("Riya", 92), ("Vivek", 78), ("Neha", 90)]

After sorting in descending order of marks:

sorted_students = [("Riya", 92), ("Neha", 90), ("Amit", 85), ("Vivek", 78)]

This makes it easy to see who scored the highest and who needs improvement.

📋 Types of Sorting Algorithms (Only Names):

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Counting Sort
7. Radix Sort

🧠 Definition: Bubble Sort

Bubble Sort is a simple sorting algorithm that 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.

• It works by "bubbling" the largest (or smallest) element to the end of the list in each iteration.
• Time Complexity:
• Worst & Average: O(n²)
• Best (when array is sorted): O(n)

🧰 Syntax in Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap if the element is greater than the next
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

💡 Example:

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

Output:

Sorted array is: [11, 12, 22, 25, 34, 64, 90]

🔧 Practical Use Case:

While Bubble Sort is not used in large applications due to its inefficiency, it is useful in:

• Educational purposes for understanding sorting concepts.
• Small datasets where simplicity is more important than performance.
• Detecting tiny errors in nearly sorted data (e.g., two elements swapped).

🧠 Definition: Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: sorted and unsorted. In each pass, it selects the smallest element from the unsorted part and swaps it with the first unsorted element, thus growing the sorted part one element at a time.

·         It works by repeatedly selecting the minimum element.

·         Time Complexity:

o    Best, Average, Worst: O(n²)

·         Space Complexity: O(1) (in-place sorting)

🧰 Syntax in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        # Find the minimum element in remaining unsorted array
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum with the first unsorted element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

💡 Example:

arr = [29, 10, 14, 37, 13]
selection_sort(arr)
print("Sorted array is:", arr)

Output:

Sorted array is: [10, 13, 14, 29, 37]

📌 Summary:

• Selection Sort is simple and works well for small datasets.
• It always takes O(n²) time regardless of the input.
• It’s useful for educational purposes, or where memory usage must be minimal.

🧠 Definition: Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works the same way as sorting playing cards in your hand – by inserting each new card into its correct position.

·         It starts from the second element, compares it with previous elements, and inserts it in the correct position.

·         Time Complexity:

o    Best: O(n) (when already sorted)

o    Average/Worst: O(n²)

·         Space Complexity: O(1) (in-place sort)

🧰 Syntax in Python:

def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 # Move elements greater than key to one position ahead while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key

💡 Example:

arr = [12, 11, 13, 5, 6] insertion_sort(arr) print("Sorted array is:", arr)

Output:

Sorted array is: [5, 6, 11, 12, 13]

✅Key Points:

• Efficient for small or nearly sorted datasets.
• Performs better than bubble and selection sort in practice.
• Used in online algorithms, like insertion while receiving a stream of data.


Quick Sort Steps
Steps Result is :-
3, 7, 9, 11, 12
🧠 Definition: Quick Sort

Quick Sort is a divide-and-conquer algorithm. It works by selecting a pivot
element and partitioning the array into two parts:

·  Elements less than the pivot (left side),
· Elements greater than the pivot (right side).

The process is repeated recursively on each part until the array is sorted.
· Time Complexity:
Best & Average: O(n log n)
Worst (if pivot is poorly chosen): O(n²)
· Space Complexity:
O(log n) for recursive calls (in-place sort)
🧰 Syntax in Python:

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

💡 Example:

arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

Output:

Sorted array is: [1, 5, 7, 8, 9, 10]
✅Key Points:

• Quick Sort is faster than Bubble, Insertion, and Selection Sort on large datasets.
• It is widely used in practice and built into many programming libraries.
• The choice of pivot is crucial for performance.



Counting Sort Steps
Steps Result is: -
0, 2, 2, 2, 3, 3
🧠 Definition: Counting Sort
Counting Sort is a non-comparison-based sorting algorithm used to sort integers within a 
known, limited range.It works by counting the occurrences of each element and then 
calculating their positions in the sorted array.
It is fast for sorting integers or characters when the range of input values (k) is 
  not significantly larger than the number of elements (n).
Time Complexity:
Best, Average, Worst: O(n + k)
Space Complexity: O(k)
⚠️ Important Notes:
Works only for non-negative integers (or modified for handling negatives).
It is not comparison-based, hence can be faster than Quick Sort for small ranges.
It is stable (preserves the relative order of equal elements).
🧰 Syntax in Python: 

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
 
    # Count the occurrences
    for num in arr:
        count[num] += 1
 
    # Build the sorted array
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

💡 Example:

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array is:", sorted_arr)

Output:

Sorted array is: [1, 2, 2, 3, 3, 4, 8]

✅Use Case:

Great for sorting exam scores, age lists, characters, and digits where values 
         are limited (e.g., 0–100).
Used in radix sort as a subroutine.

Radix Sort Steps
Steps Result is :-
17, 24, 25, 33, 40, 45

🧠Definition: Radix Sort
Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing 
individual digits, starting from the least significant digit (LSD) to the most significant 
digit (MSD).

It uses a stable sorting algorithm (like Counting Sort) as a subroutine to sort digits at each place 
value.
Time Complexity: O(n * k), where
n = number of elements
k = number of digits in the maximum number
Space Complexity: O(n + k)
📌Characteristics:
Efficient for large lists of integers or strings of fixed length.
Works only for integers or data that can be broken into positional digits.
Stable sort
🧰 Syntax in Python:

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    # Count occurrences based on digit at 'exp' position
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
 
    # Cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    # Build the output array
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
 
    # Copy to original array
    for i in range(n):
        arr[i] = output[i]
 
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

💡 Example:

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array is:", arr)

Output:

Sorted array is: [2, 24, 45, 66, 75, 90, 170, 802]

✅Key Use Cases:

Sorting large lists of numbers where keys are of uniform length.
Used in scenarios like:
Phone number sorting
ZIP code sorting
Integer data logs


Merge Sort Steps
Steps Result is :-
3, 4, 5, 8, 9, 11, 12
🧠 Definition: Merge Sort
Merge Sort is a Divide and Conquer algorithm that:
1.Divides the array into two halves,
2.Recursively sorts each half,
3.Merges the two sorted halves to produce the final sorted array.
· It is a stable sorting algorithm.
· Suitable for sorting linked lists and large datasets.
📊Time & Space Complexity:
· Time Complexity:
o Best, Average, Worst: O(n log n)
·Space Complexity: O(n) (uses extra space for temporary arrays)
🧰 Syntax in Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
 
        # Recursive call on each half
        merge_sort(left_half)
        merge_sort(right_half)
 
        # Merge the sorted halves
        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
 
        # Copy remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

💡 Example:

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array is:", arr)
Output:
Sorted array is: [3, 9, 10, 27, 38, 43, 82]

✅Key Use Cases:

Efficient for large datasets.
Works well for external sorting (when data doesn't fit in memory).
Suitable for linked lists, as it doesn’t require random access.