Built-in Sorting (The "Right" Way)
● [Link](): Modifies the list in-place (doesn't return a new list).
● sorted(list): Returns a new, sorted list (leaves the original list unchanged).
<!-- end list -->
# 1. sorted() - Returns a new list
my_list = [3, 1, 4, 1, 5, 9, 2]
new_sorted_list = sorted(my_list)
print(f"Original: {my_list}")
print(f"New List: {new_sorted_list}")
# 2. .sort() - Modifies the list in-place
my_list.sort()
print(f"Original (now sorted): {my_list}")
# 3. Sorting in reverse
rev_sorted_list = sorted(my_list, reverse=True)
print(f"Reverse sorted: {rev_sorted_list}")
1. 🧼 Bubble Sort
This is the simplest, but also one of the slowest, sorting algorithms.
● Analogy: Heavy "bubbles" in water sink to the bottom (or light ones bubble to the top).
● How it works: It repeatedly steps through the list, compares adjacent elements, and
swaps them if they are in the wrong order. With each pass, the next largest element
"bubbles up" to its correct position at the end of the list.
● Time Complexity: O(n^2) - (very slow for large lists).
Easy Program: Bubble Sort
def bubble_sort(arr):
n = len(arr)
# Loop for each pass
for i in range(n):
# A flag to optimize if the list is already sorted
swapped = False
# Inner loop for comparisons
# (n-i-1) because the last 'i' elements are already sorted
for j in range(0, n - i - 1):
# Compare adjacent elements
if arr[j] > arr[j + 1]:
# Swap them
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swaps happened in a full pass, it's sorted
if not swapped:
break
return arr
# Example
my_list = [64, 34, 25, 12, 22, 11, 90]
print(f"Bubble Sort: {bubble_sort(my_list)}")
2. 🎴 Selection Sort
This is also simple but slow. It's more intuitive than Bubble Sort.
● Analogy: "Selecting" the smallest (or largest) item from the unsorted pile and moving it to
the sorted pile.
● How it works: It divides the list into a sorted part (at the beginning) and an unsorted part.
It finds the smallest element in the unsorted part and swaps it with the first element of the
unsorted part, growing the sorted section by one.
2,3,1,5,4,6,9
● Time Complexity: O(n^2) - (slow for large lists).
3,5,2,6,1,4,7
1,3,2,5,4,6,9
Easy Program: Selection Sort
1,2,3,5,4,6,9
def selection_sort(arr):
n = len(arr) 1,2,3,4,5,6,9
# Loop through every element
for i in range(n):
# Assume the current element is the minimum
min_index = i
# Find the actual minimum in the rest of the list
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum with the first element of the
unsorted part
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Example
my_list = [64, 25, 12, 22, 11]
print(f"Selection Sort: {selection_sort(my_list)}")
3. 🃏 Insertion Sort
This sort is very efficient for small lists or lists that are already almost sorted.
● Analogy: Sorting a hand of playing cards. You pick up one card at a time and "insert" it
into its correct position within the cards you are already holding.
● How it works: It builds the final sorted list one item at a time. It takes each item from the
input and finds the correct place for it in the already-sorted part, shifting other elements as
needed.
● Time Complexity: O(n^2) (but can be as fast as O(n) if the list is nearly sorted).
Easy Program: Insertion Sort
6, 4, 3, 8, 9, 2, 5
def insertion_sort(arr):
3, 4, 6, 8, 9, 2, 5
# Start from the second element (index 1)
for i in range(1, len(arr)):
# This is the "card" we are trying to place
key = arr[i]
# This is the index of the last card in our "sorted hand"
j = i - 1
# Move elements of arr[0..i-1] that are greater than key
# one position to the right
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# Place our "key card" in its correct spot
arr[j + 1] = key
return arr
# Example
my_list = [12, 11, 13, 5, 6]
print(f"Insertion Sort: {insertion_sort(my_list)}")
4. 📚 Merge Sort
This is a much more efficient algorithm. It's a "Divide and Conquer" strategy.
● Analogy: You have a huge, jumbled pile of exam papers. You split the pile in half, give
half to a friend, and you both split your piles again. You keep splitting until everyone has
just one paper (which is "sorted"). Then you merge the sorted single papers back into
sorted piles of two, then four, and so on, until you have one, huge, sorted pile.
● How it works:
1. Divide: Recursively split the list in half until you have many lists of size 1.
2. Conquer & Merge: Merge the small, sorted lists back together in the correct order.
● Time Complexity: O(n \log n) - (very efficient).
Easy Program: Merge Sort
def merge_sort(arr):
if len(arr) > 1:
# 1. Divide
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort both halves
merge_sort(left_half)
merge_sort(right_half)
# 2. Conquer (Merge)
i = j = k = 0 # Pointers for left_half, right_half, and main
arr
# Copy data from left_half and right_half back into arr
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
# Check for any leftover 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
return arr
# Example
my_list = [38, 27, 43, 3, 9, 82, 10]
print(f"Merge Sort: {merge_sort(my_list)}")
5. ⚡ Quick Sort
This is often the fastest sorting algorithm in practice. It's also "Divide and Conquer."
● Analogy: You are lining up kids by height. You pick one kid as the "pivot" and tell
everyone shorter to go to their left and everyone taller to go to their right. Now you have
two smaller, unsorted groups, and you repeat the process with a new pivot for each
group.
● How it works:
1. Pick a Pivot: Choose an element from the list (e.g., the last one) to be the "pivot."
2. Partition: Reorder the list so that all elements smaller than the pivot are on its left,
and all elements larger are on its right.
3. Recurse: Recursively apply the same logic to the left and right sub-lists.
● Time Complexity: O(n \log n) on average, but O(n^2) in the worst case (e.g., on an
already-sorted list).
Easy Program: Quick Sort
def quick_sort(arr):
# This simple implementation is easy to understand
# (though not the most memory-efficient)
if len(arr) <= 1:
return arr
else:
# 1. Pick a pivot (here, we'll just take the first element)
pivot = arr[0]
6, 4, 2, 3, 1, 7
# 2. Partition the list 2, 3, 1, 4, 6, 7
left = [x for x in arr[1:] if x < pivot]
middle = [x for x in arr if x == pivot] 1, 2, 3, 4, 6, 7
right = [x for x in arr[1:] if x > pivot]
# 3. Recurse
return quick_sort(left) + middle + quick_sort(right)
# Example
my_list = [10, 7, 8, 9, 1, 5]
print(f"Quick Sort: {quick_sort(my_list)}")
Summary of Algorithms
Algorithm Time Complexity (Average) In-Place?
Bubble Sort O(n^2) Yes
Selection Sort O(n^2) Yes
Insertion Sort O(n^2) Yes
Merge Sort O(n \log n) No (Uses extra memory)
Quick Sort O(n \log n) Yes (in most implementations)
Python's sorted() O(n \log n) N/A (Returns new list)
