1
Data Structure
and Algorithms
2
Chapter 3: Simple Sorting
Yusuf Abas, PhD
Candidate (AI)
3
Last class
• Arrays store data in a sequential and indexed structure, allowing fast direct access.
• Arrays can be unordered (fast insertion, slow search) or ordered (slow insertion, fast
search).
• Linear search checks elements one by one, while binary search (on ordered arrays) is
much faster.
• Binary search efficiency is based on logarithms, reducing the search space step by step.
• Arrays can store simple values and complex objects, organized using a key.
• Big O notation is used to measure algorithm efficiency:
O(1) best, O(log N) good, O(N) fair, O(N²) slow.
• Arrays are simple and efficient for access but not ideal for frequent insertion and
deletion.
Chapter Overview
✓ What is Sorting & Why It Matters
✓ Manual Sorting Thinking
✓ Bubble Sort - Algorithm & Examples
✓ Selection Sort - Algorithm & Examples
✓ Insertion Sort - Algorithm & Examples
✓ Comparing Sorting Algorithms
✓ Class activity
What is Sorting?
Sorting means arranging data in a specific order.
Ascending (Small → Large) Descending (Large → Small)
Unsorted: Unsorted:
[5, 2, 9, 1] [5, 2, 9, 1]
Sorted: Sorted:
[1, 2, 5, 9] [9, 5, 2, 1]
Why is Sorting Important?
Faster Searching
Binary search works on sorted data
Better Organization
Makes data easier to understand
Improved Performance
Enables efficient algorithms
How Would You Sort?
Imagine sorting cards in your hand:
1 Take two cards and compare
2 Place smaller card on left
3 Move to next card
4 Repeat until sorted
This simple thinking is the foundation of sorting algorithms!
Bubble Sort - Concept
How it works:
Compare adjacent elements and swap if wrong order. Largest "bubbles up" to end.
Algorithm Steps:
① Compare pairs of adjacent elements
② If left > right, swap them Time: O(n²) | Space: O(1)
③ Continue across entire array (one pass)
④ Largest element is now at the end
⑤ Repeat for remaining unsorted portion
Bubble Sort - Example
Array: [5, 3, 8, 2]
Pass 1:
[5,3,8,2] → Compare 5&3 → [3,5,8,2]
[3,5,8,2] → Compare 5&8 → [3,5,8,2]
[3,5,8,2] → Compare 8&2 → [3,5,2,8] ✓
Pass 2:
[3,5,2,8] → Compare 3&5 → [3,5,2,8]
[3,5,2,8] → Compare 5&2 → [3,2,5,8] ✓
Pass 3:
[3,2,5,8] → Compare 3&2 → [2,3,5,8] ✓
Selection Sort - Concept
How it works:
Find smallest element and place at start. Repeat for remaining unsorted portion.
Algorithm Steps:
① Find the minimum element in array
Time: O(n²) | Space: O(1)
② Swap it with the first position
③ Move to the next position
④ Repeat for remaining unsorted portion
⑤ Continue until array is fully sorted
Selection Sort - Example
Array: [5, 3, 8, 2]
Step 1: Find min → 2, swap with pos 0 → [2, 3, 8, 5]
Step 2: Find min (pos 1+) → 3, in place → [2, 3, 8, 5]
Step 3: Find min (pos 2+) → 5, swap → [2, 3, 5, 8]
Result: [2, 3, 5, 8] ✓ Sorted!
Insertion Sort - Concept
How it works:
Build sorted list by inserting each element into its correct position.
Algorithm Steps:
① Start with first element (already sorted)
Time: O(n²) Best: O(n) | Space: O(1)
② Take next element (key)
③ Shift all larger elements one position right
④ Insert key into correct position
⑤ Repeat until all elements processed
Insertion Sort - Example
Array: [5, 3, 8, 2]
Start: [5] - Already sorted
Insert 3: [3, 5] - Move 5 right, insert 3
Insert 8: [3, 5, 8] - 8 largest, place at end
Insert 2: [2, 3, 5, 8] - Shift all, insert 2
Final: [2, 3, 5, 8] ✓
Best for small or nearly sorted data
Comparing All Three
Algorithm Method Best
Bubble Sort Swap adjacent Slow
Selection Sort Select min Slow
Insertion Sort Insert into sorted place Better for small data
When to Use Simple Sorting?
✓ Use When: ✗ Avoid When:
• Data size is small • Data size > 10,000
• Learning algorithms • Performance critical
• Data nearly sorted • Real-time systems
• Memory is limited • Production code
Big O Comparison of Simple Sorting Algorithms
Algorithm Best Case Average Case Worst Case Space Reason
Bubble Sort O(n) O(n²) O(n²) O(1) Repeatedly compares adjacent
elements; many unnecessary
comparisons
Selection Sort O(n²) O(n²) O(n²) O(1) Always scans entire array to find
minimum, even if sorted
Insertion Sort O(n) O(n²) O(n²) O(1) Efficient when data is already or
nearly sorted
Practice Exercise
Manual Sorting Challenge
Array: [7, 3, 9, 1, 5]
① Apply Bubble Sort - Count operations
② Apply Selection Sort - Count operations
③ Apply Insertion Sort - Count operations
④ Compare which was most efficient
Chapter Summary
1 Sorting arranges data in ascending or descending order
2 Bubble Sort: repeatedly swaps adjacent elements
3 Selection Sort: selects minimum and places it
4 Insertion Sort: builds sorted array incrementally
5 All three have O(n²) average time complexity
6 Use for small data or learning only
7 For large data, use advanced algorithms
19
End