Go for Sort: Part 2 - Expanding the Fundamentals and Implementing Few Other Sorting Algorithms

Hello, fellow developers! Welcome back to the "Go for Sort" series. In the previous post, we laid the groundwork by exploring the fundamentals of sorting and implementing the Insertion Sort algorithm. Today, we're taking the next step in our journey to understand common sorting techniques by diving deep into Selection Sort and Bubble Sort. As a friendly reminder, all code examples in this series are provided in Go. However, the underlying logic and concepts are universal, so if you're familiar with any programming language, you should be able to follow along without any issues. Selection Sort: Finding the Minimum Let's start with Selection Sort. The name itself gives us a strong hint about how this algorithm works: it repeatedly selects something. But what exactly does it select? At its core, Selection Sort focuses on finding the element with the minimum value in the unsorted portion of the array at each iteration. Imagine you're organizing a deck of cards and want to put them in ascending order. Selection Sort is like scanning through the unsorted cards, picking out the smallest one, and placing it at the beginning of the sorted pile. Here's how it works step-by-step: Iteration: We iterate through the input array using an outer loop, from the first element up to the second-to-last element. Finding the Minimum: For each position in the outer loop (let's say at index i), we scan the rest of the unsorted part of the array (from index i + 1 to the end) to find the index of the smallest element. We'll call this minIndex. Swapping: Once we've found the minIndex, if it's different from the current index i, we swap the element at i with the element at minIndex. This places the smallest element found so far into its correct sorted position at the beginning of the unsorted portion. This process ensures that with each pass of the outer loop, the smallest remaining element is moved to its correct sorted position. Here's the Go implementation of Selection Sort: package main import ( "fmt" ) func SelectionSort(arr []int) { n := len(arr) for i := 0; i

Apr 29, 2025 - 15:55

Go for Sort: Part 2 - Expanding the Fundamentals and Implementing Few Other Sorting Algorithms

Hello, fellow developers! Welcome back to the "Go for Sort" series. In the previous post, we laid the groundwork by exploring the fundamentals of sorting and implementing the Insertion Sort algorithm. Today, we're taking the next step in our journey to understand common sorting techniques by diving deep into Selection Sort and Bubble Sort.

As a friendly reminder, all code examples in this series are provided in Go. However, the underlying logic and concepts are universal, so if you're familiar with any programming language, you should be able to follow along without any issues.

Selection Sort: Finding the Minimum

Let's start with Selection Sort. The name itself gives us a strong hint about how this algorithm works: it repeatedly selects something. But what exactly does it select?

At its core, Selection Sort focuses on finding the element with the minimum value in the unsorted portion of the array at each iteration. Imagine you're organizing a deck of cards and want to put them in ascending order. Selection Sort is like scanning through the unsorted cards, picking out the smallest one, and placing it at the beginning of the sorted pile.

Here's how it works step-by-step:

Iteration: We iterate through the input array using an outer loop, from the first element up to the second-to-last element.
Finding the Minimum: For each position in the outer loop (let's say at index i), we scan the rest of the unsorted part of the array (from index i + 1 to the end) to find the index of the smallest element. We'll call this minIndex.
Swapping: Once we've found the minIndex, if it's different from the current index i, we swap the element at i with the element at minIndex. This places the smallest element found so far into its correct sorted position at the beginning of the unsorted portion.

This process ensures that with each pass of the outer loop, the smallest remaining element is moved to its correct sorted position.

Here's the Go implementation of Selection Sort:

package main

import (
    "fmt"
)

func SelectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        if minIndex != i {
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
        }
    }
}

func main() {
    nums := []int{78, 64, 89, 345, 123, 1}
    fmt.Println("Unsorted:", nums)
    SelectionSort(nums)
    fmt.Println("Sorted:", nums)
}

Time Complexity of Selection Sort

The time complexity of Selection Sort is O(n²) in all cases (best, average, and worst). This is because the outer loop runs n-1 times, and for each iteration of the outer loop, the inner loop runs approximately n-i times. Even if the array is already sorted, the algorithm will still perform the same number of comparisons. While it's simple to understand and implement, its quadratic time complexity makes it inefficient for large datasets.

When Might You Use Selection Sort?

While not the most efficient general-purpose sorting algorithm, Selection Sort has some niche advantages:

Simplicity: It's very easy to understand and implement.
Minimal Swaps: Selection Sort performs a minimal number of swaps (O(n) in the worst case). This can be beneficial in scenarios where swapping elements is a costly operation.

Bubble Sort: Let the Largest Elements Rise

Now, let's move on to our second algorithm for today: Bubble Sort. The name of this algorithm comes from the way larger elements "bubble" to the end of the array with each pass. As the heading suggests, Selection Sort focuses on finding the minimum value, while Bubble Sort focuses on moving the largest to the end. Other than that, both algorithms perform swaps after finding smallest and largest elements respectively. But there's a slight difference in how they perform swaps — let's dive in!

Imagine again our deck of cards (I know, next time I'll use something funnier as an example). Now, instead of picking out the smallest card directly, think of going through the deck, one pair at a time. If two adjacent cards are in the wrong order (e.g., a 7 comes before a 3 when we want ascending order), we swap them. We repeat this process, going through the deck multiple times. With each pass, the larger (or smaller, depending on the desired order) cards will gradually "bubble" their way towards their correct position at the end of the deck.

Here's the process:

Iteration: We iterate through the array multiple times.
Comparison and Swapping: In each pass, we compare each pair of adjacent elements. If the element on the left is greater than the element on the right, we swap them.
Optimization (Optional): After each pass, the largest unsorted element is guaranteed to be in its correct position at the end of the unsorted portion. This means we can reduce the number of comparisons in subsequent passes. If no swaps occur during a pass, it indicates that the array is already sorted, and we can terminate the algorithm early.

Here's the Go implementation of Bubble Sort:

package main

import (
    "fmt"
)

func BubbleSort(arr []int) {
    n := len(arr)
    swapped := true
    for swapped {
        swapped = false
        for i := 0; i < n-1; i++ {
            if arr[i] > arr[i+1] {
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped = true
            }
        }
        n-- // Optimization: Reduce the number of comparisons in subsequent passes
    }
}

func main() {
    nums := []int{78, 64, 89, 345, 123, 1}
    fmt.Println("Unsorted:", nums)
    BubbleSort(nums)
    fmt.Println("Sorted:", nums)
}

Time Complexity of Bubble Sort

The time complexity of Bubble Sort is O(n²) in the average and worst cases. This is due to the nested loops that compare and potentially swap adjacent elements.

However, Bubble Sort has a best-case time complexity of O(n) when the input array is already sorted. In this scenario, the algorithm will make one pass through the array without any swaps, and the swapped flag will remain false, causing the algorithm to terminate.

When Might You Use Bubble Sort?

Like Selection Sort, Bubble Sort is generally not the most efficient algorithm for large datasets due to its quadratic time complexity. However, it can be useful in the following situations:

Small Datasets: For very small arrays, the simplicity of Bubble Sort might outweigh the slight performance overhead compared to more complex algorithms.
Educational Purposes: It's a very intuitive and easy-to-understand algorithm, making it a great starting point for learning about sorting.
Nearly Sorted Data: If you know that your data is almost sorted, Bubble Sort can perform quite well (approaching O(n) with the optimization).

Conclusion

In this post, we've expanded our sorting knowledge by exploring two more fundamental algorithms: Selection Sort and Bubble Sort. We've seen how they work, looked at their Go implementations, and discussed their time complexities and potential use cases.

Stay tuned for the next part of our "Go for Sort" series, where we'll delve into more efficient sorting algorithms!