Basic Sorting: Like Organizing Your Room
Welcome! You learned about trees. Now let’s learn about Sorting - arranging things in order!
What is Sorting? (Real Life Analogy)
Organizing Your Toys
Imagine your toy box is messy:
- Cars, dolls, blocks all mixed up
- You want cars with cars, dolls with dolls
- Everything in its proper place
Sorting is arranging items in a specific order - like smallest to largest, or A to Z!
Method 1: Bubble Sort - Like Bubble Blowing
The Bubble Analogy
Imagine bubbles in water:
- Big bubbles rise to the top
- Small bubbles stay below
- They “bubble up” to their correct position
Bubble Sort works the same way - bigger items “bubble” to the end!
func bubbleSort(toys []int) {
// Go through the toy box multiple times
for pass := 0; pass < len(toys)-1; pass++ {
// Compare each pair of toys
for i := 0; i < len(toys)-1-pass; i++ {
// If current toy is bigger than next toy
if toys[i] > toys[i+1] {
// Swap them! (like bubbles rising)
toys[i], toys[i+1] = toys[i+1], toys[i]
}
}
}
}
func main() {
toys := []int{5, 3, 8, 1, 9, 2}
fmt.Println("Before:", toys)
bubbleSort(toys)
fmt.Println("After:", toys) // [1, 2, 3, 5, 8, 9]
}Watch It Work Step by Step
Start: [5, 3, 8, 1, 9, 2]
Pass 1:
- Compare 5>3? Yes, swap → [3, 5, 8, 1, 9, 2]
- Compare 5<8? No, stay → [3, 5, 8, 1, 9, 2]
- Compare 8>1? Yes, swap → [3, 5, 1, 8, 9, 2]
- Compare 8<9? No, stay → [3, 5, 1, 8, 9, 2]
- Compare 9>2? Yes, swap → [3, 5, 1, 8, 2, 9]
Pass 2:
- Compare 3<5? No, stay → [3, 5, 1, 8, 2, 9]
- Compare 5>1? Yes, swap → [3, 1, 5, 8, 2, 9]
- Compare 5<8? No, stay → [3, 1, 5, 8, 2, 9]
- Compare 8>2? Yes, swap → [3, 1, 5, 2, 8, 9]
- 9 is already at end
And so on… until everything is sorted!
Method 2: Selection Sort - Like Picking Favorites
The Toy Selection Analogy
Imagine you have toys scattered everywhere:
- You pick the smallest toy first
- Put it in position 1
- Pick the next smallest
- Put it in position 2
- And so on…
Selection Sort finds the smallest item and puts it in the right place!
func selectionSort(books []int) {
// For each position in the shelf
for position := 0; position < len(books)-1; position++ {
// Assume current position has the smallest book
smallestIndex := position
// Look through remaining books
for i := position + 1; i < len(books); i++ {
if books[i] < books[smallestIndex] {
// Found a smaller book!
smallestIndex = i
}
}
// Swap the smallest book into position
books[position], books[smallestIndex] = books[smallestIndex], books[position]
}
}
func main() {
books := []int{64, 25, 12, 22, 11}
fmt.Println("Before:", books)
selectionSort(books)
fmt.Println("After:", books) // [11, 12, 22, 25, 64]
}Watch It Work
Start: [64, 25, 12, 22, 11]
Position 0:
- Look for smallest: 11 at index 4
- Swap 64 and 11 → [11, 25, 12, 22, 64]
Position 1:
- Look for smallest in [25, 12, 22, 64]: 12 at index 2
- Swap 25 and 12 → [11, 12, 25, 22, 64]
Position 2:
- Look for smallest in [25, 22, 64]: 22 at index 3
- Swap 25 and 22 → [11, 12, 22, 25, 64]
Position 3:
- Look for smallest in [25, 64]: 25
- Already in place!
Method 3: Insertion Sort - Like Sorting Cards
The Card Game Analogy
Imagine playing cards:
- You have cards in your hand
- You pick a new card
- You insert it in the right place among your existing cards
- Everything stays sorted!
Insertion Sort takes each item and inserts it where it belongs!
func insertionSort(cards []int) {
// Start from the second card
for current := 1; current < len(cards); current++ {
// Pick up the current card
cardToInsert := cards[current]
// Start comparing from the previous card
position := current - 1
// Shift larger cards to the right
for position >= 0 && cards[position] > cardToInsert {
cards[position+1] = cards[position]
position--
}
// Insert the card in its correct spot
cards[position+1] = cardToInsert
}
}
func main() {
cards := []int{12, 11, 13, 5, 6}
fmt.Println("Before:", cards)
insertionSort(cards)
fmt.Println("After:", cards) // [5, 6, 11, 12, 13]
}Watch It Work
Start: [12, 11, 13, 5, 6]
Current = 1 (11):
- Compare with 12: 11 < 12, so shift 12 right
- Insert 11 at position 0 → [11, 12, 13, 5, 6]
Current = 2 (13):
- Compare with 12: 13 > 12, stays → [11, 12, 13, 5, 6]
Current = 3 (5):
- Compare with 13: 5 < 13, shift 13 right
- Compare with 12: 5 < 12, shift 12 right
- Compare with 11: 5 < 11, shift 11 right
- Insert 5 at position 0 → [5, 11, 12, 13, 6]
Current = 4 (6):
- Compare with 13: 6 < 13, shift 13 right
- Compare with 12: 6 < 12, shift 12 right
- Compare with 11: 6 > 11, stop
- Insert 6 after 11 → [5, 6, 11, 12, 13]
Method 4: Shell Sort - Like Organizing Books by Groups
The Library Organization Analogy
Imagine organizing a messy library:
- First, group books by big categories (Fiction vs Non-fiction)
- Then subdivide (Mystery, Romance, Science Fiction)
- Keep subdividing until every book is in perfect order
Shell Sort works the same way - it sorts in big “jumps” first, then smaller jumps!
func shellSort(books []int) {
n := len(books)
// Start with big gaps (like big groups)
gap := n / 2
// Keep making gaps smaller
for gap > 0 {
// Sort books in each group
for i := gap; i < n; i++ {
// Pick up current book
currentBook := books[i]
// Compare with books in the same group
position := i
// Shift larger books to the right
for position >= gap && books[position-gap] > currentBook {
books[position] = books[position-gap]
position -= gap
}
// Put current book in its spot
books[position] = currentBook
}
// Make gap smaller (like subdividing groups)
gap /= 2
}
}
func main() {
books := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("Before:", books)
shellSort(books)
fmt.Println("After:", books) // [11, 12, 22, 25, 34, 64, 90]
}Watch It Work
Start: [64, 34, 25, 12, 22, 11, 90]
Gap = 3 (big groups):
- Group 1: 64, 22 → [22, 34, 25, 12, 64, 11, 90]
- Group 2: 34, 11 → [22, 11, 25, 12, 64, 34, 90]
- Group 3: 25, 90 → [22, 11, 25, 12, 64, 34, 90]
Gap = 1 (insertion sort):
- Now it’s like regular insertion sort to finish!
Why it’s faster: Shell sort moves items big distances first, then fine-tunes!
Which Method is Best? (Sorting Showdown)
Bubble Sort
- Good for: Small lists, learning to sort
- Bad for: Big lists (too slow)
- Like: Carefully checking every pair
- Speed: Slow for big jobs
Selection Sort
- Good for: When you don’t want to swap much
- Bad for: Big lists
- Like: Finding the best item each time
- Speed: Steady but slow
Insertion Sort
- Good for: Almost sorted lists, small lists
- Bad for: Random messy lists
- Like: Building a sorted card hand
- Speed: Fast for nearly sorted data
Shell Sort
- Good for: Medium-sized lists
- Bad for: Very small lists (overkill)
- Like: Organizing by big groups first
- Speed: Faster than the others for medium data
Implementation with Custom Comparators
type Sortable interface {
Less(i, j int) bool
Swap(i, j int)
Len() int
}
func sort(data Sortable) {
for i := 0; i < data.Len()-1; i++ {
for j := 0; j < data.Len()-i-1; j++ {
if data.Less(j+1, j) {
data.Swap(j, j+1)
}
}
}
}
// Usage example
type IntSlice []int
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s IntSlice) Len() int { return len(s) }Go’s Built-in Sorting (Like Having a Robot Helper)
Go comes with a super-smart sorting robot that does all the hard work for you!
import "sort"
func main() {
// Sort numbers automatically
toys := []int{5, 2, 8, 1, 9}
sort.Ints(toys)
fmt.Println("Sorted toys:", toys) // [1, 2, 5, 8, 9]
// Sort words alphabetically
words := []string{"zebra", "apple", "banana"}
sort.Strings(words)
fmt.Println("Sorted words:", words) // [apple, banana, zebra]
// Sort custom things (like people by age)
type Person struct {
name string
age int
}
people := []Person{
{"Alice", 25},
{"Bob", 30},
{"Charlie", 20},
}
// Tell Go how to sort people
sort.Slice(people, func(i, j int) bool {
return people[i].age < people[j].age // Sort by age
})
for _, person := range people {
fmt.Printf("%s is %d years old\n", person.name, person.age)
}
// Output: Charlie is 20, Alice is 25, Bob is 30
}Why use Go’s sort? It’s fast, reliable, and handles all the complex stuff for you!
Real Life Sorting Challenges
Challenge 1: Toy Box Organizer
Sort toys by size from smallest to largest:
func sortToysBySize(toys []int) {
// Use any sorting method you learned
// Your code here
}Challenge 2: Library Book Sorter
Sort book titles in alphabetical order:
func sortBooksAlphabetically(books []string) {
// Your code here
}Challenge 3: Student Grade Organizer
Sort students by their test scores:
type Student struct {
name string
score int
}
func sortStudentsByScore(students []Student) {
// Your code here
}Challenge 4: Even Numbers First
Sort numbers but put even numbers before odd numbers:
func sortEvenBeforeOdd(numbers []int) {
// Your code here - even numbers first, then odds
}Challenge 5: Reverse Order
Sort numbers from biggest to smallest:
func sortBiggestFirst(numbers []int) {
// Your code here
}What’s Next?
Awesome! You learned basic sorting methods. Next, we’ll explore Advanced Sorting Algorithms - super-fast methods for huge lists!
Quick Quiz
- What’s the difference between bubble sort and selection sort?
- When is insertion sort fastest?
- Why do we sort things in programming?
- Can you sort strings the same way as numbers?
- What’s the fastest basic sorting method we learned?
Remember: Sorting is like organizing - it makes finding things much easier!