DEV Community: Alibek

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

Alibek — Tue, 29 Apr 2025 14:49:11 +0000

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!

Go for Sort: Part 1 - Exploring the Fundamentals and Implementing Insertion Sort

Alibek — Mon, 28 Apr 2025 07:22:57 +0000

Hello! Welcome to this post where we'll explore the fascinating world of sorting algorithms. As a follow-up to my previous post on search algorithms, particularly binary search, it's crucial to understand that binary search requires sorted input. In this article, we'll define what it means for data to be sorted and explore various methods to achieve this ordering.

As usual, all the code examples are provided in the Go programming language. However, I am confident that even if you're not familiar with Go but have programming experience, you'll be able to understand the examples with minimal effort.

Alright, here we go. What does it mean for something to be "sorted"? Well, first thing that comes to my mind is that something has some kind of an order, or there is the sequence of the things that follows predefined rules. Consider a box of apples of various colors. If we decide to group them into separate boxes based on their color, what is that process called? That's right – sorting! With numbers, the concept of order is intuitive: 1 is less than 2, 2 is less than 3, and this pattern continues. How can we leverage this natural ordering? Well, we can create a sequence where numbers follow this rule: starting with the smallest, ending with the largest, and ensuring that each element is greater than or equal to the preceding one and less than or equal to the following one. Because sorting enables the efficient arrangement of massive datasets, making information retrieval a breeze, it stands as a cornerstone of computer science, underpinning countless applications from database management to search engines.

In this series of posts, we are going to look at a few different algorithms, and to start, let's dive into something called Insertion Sort. This sorting algorithm is quite intuitive because it reminds us of how we might sort a hand of playing cards.

Imagine you're holding a hand of cards dealt one by one. As you receive each new card, you look at the cards you're already holding and insert the new card into its correct position within your hand, ensuring that the cards in your hand are always sorted. You might shift some of the existing cards to the right to make space for the new one.

Insertion Sort works in a similar way with arrays or lists. It iterates through the elements, and for each element, it compares it with the elements before it. If the current element is smaller than the preceding elements, it "inserts" it into the correct sorted position by shifting the larger elements to the right.

Let's illustrate this with an example. Suppose we have the following unsorted array of numbers: [5, 2, 4, 6, 1, 3].

Here's how Insertion Sort would process it step by step:

Start with the second element (2). Compare it with the element before it (5). Since 2 is smaller than 5, we move 5 to the right and insert 2 in its place: [2, 5, 4, 6, 1, 3]. The first two elements are now sorted.
Move to the third element (4). Compare it with the elements before it (5 and 2). 4 is smaller than 5, so we shift 5 to the right. Now compare 4 with 2. Since 4 is greater than 2, we insert 4 in its current position: [2, 4, 5, 6, 1, 3]. The first three elements are now sorted.
Consider the fourth element (6). Compare it with the elements before it (5, 4, and 2). 6 is greater than all of them, so it remains in its current position: [2, 4, 5, 6, 1, 3]. The first four elements are sorted.
Move to the fifth element (1). Compare it with 6, 5, 4, and 2. 1 is smaller than all of them. We shift 6, 5, 4, and 2 to the right and insert 1 at the beginning: [1, 2, 4, 5, 6, 3]. The first five elements are sorted.
Finally, consider the last element (3). Compare it with 6, 5, 4, 2, and 1. 3 is smaller than 6, 5, and 4, so we shift them to the right. 3 is greater than 2, so we insert 3 in its correct position: [1, 2, 3, 4, 5, 6].

Now the entire array is sorted!

This step-by-step process of taking an element and inserting it into its correct sorted position within the already sorted portion of the array is the essence of Insertion Sort. Now to the coding example:

package main

import "fmt"

// InsertionSort sorts an integer slice
func InsertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        j := i
        for j > 0 && arr[j-1] > arr[j] {
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j = j - 1 
        }
    }
}

func main() {
    unsortedArray := []int{5, 2, 4, 6, 1, 3}
    fmt.Println("Unsorted array:", unsortedArray)

    InsertionSort(unsortedArray)

    fmt.Println("Sorted array:", unsortedArray)
}

When you run this Go code, you will see the following output:
Unsorted array: [5 2 4 6 1 3]
Sorted array: [1 2 3 4 5 6]

This clearly shows how the InsertionSort function takes an unsorted array and modifies it in-place to produce a sorted array.

Time Complexity of Insertion Sort:

To understand how efficient Insertion Sort is, we need to consider its time complexity in different scenarios:

Worst-case: The worst-case scenario occurs when the input array is sorted in reverse order. In this case, for each element, we have to compare it with all the preceding elements and shift them to the right. This results in approximately n(n-1)/2 comparisons and swaps, where n is the number of elements in the array. Therefore, the worst-case time complexity of Insertion Sort is O(n²).
Best-case: The best-case scenario happens when the input array is already sorted. In this situation, for each element, we only need to perform one comparison with the element before it, and no swaps are needed. Thus, the best-case time complexity of Insertion Sort is O(n).
Average-case: In the average case, where the elements in the input array are in a random order, we can expect to perform approximately half the number of comparisons and shifts as in the worst case. Therefore, the average-case time complexity of Insertion Sort is also O(n²).

Insertion Sort is efficient for small datasets or for datasets that are nearly sorted. Its simplicity and low overhead make it a good choice in such cases. However, for larger, unsorted datasets, algorithms with better average and worst-case time complexities, like Merge Sort or Quick Sort, are generally preferred.

That wraps up our exploration of Insertion Sort. In the next post, we'll delve into the characteristics and implementation of another fundamental sorting algorithm. Stay tuned!

Linear Search vs. Binary Search: A Practical Guide in Go

Alibek — Mon, 21 Apr 2025 08:42:18 +0000

Hello, in this post I am going to talk about different types of search algorithms. In essence, I am going to focus on linear search and binary search, illustrating how these algorithms work and comparing them in terms of time complexity, also known as Big O Notation.

All the code examples are provided in the Go programming language. However, I am confident that even if you're not familiar with Go but have programming experience, you'll be able to understand the examples with minimal effort.

Alright, let's dive in. Firstly, we'll start with linear search, which is one of the simplest (perhaps even the most straightforward) algorithms available. I would even call this algorithm intuitive because, in most cases when faced with the task of finding a specific element within a collection, our initial thought is often to examine each element sequentially. This algorithm works exactly like that: we begin at the start of the list or array and compare each element with the target element one by one, step by step, until we find it. If the target element is not present in the list, we can simply return -1 or nil to indicate its absence.

Here is an example implementation in Go:

package main

import "fmt"

func linearSearch(arr []int, target int) int {
    for i, element := range arr {
        if element == target {
            return i // Return the index if the target is found
        }
    }
    return -1 // Return -1 if the target is not found
}

func main() {
    numbers := []int{2, 5, 1, 8, 3, 9, 4, 7, 6}
    target := 3
    index := linearSearch(numbers, target)

    if index != -1 {
        fmt.Printf("Element %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Element %d not found in the array\n", target)
    }

    target = 10
    index = linearSearch(numbers, target)

    if index != -1 {
        fmt.Printf("Element %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Element %d not found in the array\n", target)
    }
}

In this Go code, the linearSearch function takes an integer slice arr and an integer target as input. It iterates through each element and its corresponding index in the slice. If the element matches the target, the function immediately returns the index. If the loop completes without finding the target, the function returns -1. The main function demonstrates how to use the linearSearch function with a sample array and target values.

Why is it called linear search, though? Remember Big O notation? Well, it turns out that Big O describes the so-called time complexity of this algorithm, which represents the time required for this algorithm to perform the operation, in our case, finding the element in the collection. Does it tell us the exact time needed to complete the search? No, of course not. Even though this term is called time complexity, it doesn't actually describe the precise time required to do the work. Instead, it tells us the number of operations this algorithm would require to complete the given task.

This algorithm can have different scenarios or cases. Let's say the best-case scenario is when the target element is the first in the collection (or the element with the index of 0). In that case, we don't need to go through the entire collection to find the target; it will be found in the first iteration, meaning we would require just one operation.

Now, let's consider the worst case. This basically means that the target element is at the end of the collection. And yes, as you might have guessed, we will need to compare every element in the collection with our target to find out that the target is the last element (or the element with the index of len(arr)-1). In that case, we can say that we require N operations to complete the task, where N is the size of our array. If there are 10 elements in the array, that's not a big deal; our code iterates 10 times to find the target. But what happens if the size of the array is 1 million elements or even worse, 1 billion elements, and the target is still the last element? Well, the code will iterate either 1 million or 1 billion times, thus resulting in linear time complexity—the number of operations required to complete the task grows linearly with the size of the input. With that, we can say that the time complexity of linear search in the worst case is proportional to the size of the input, which is N, or simply O(n). That's how Big O notation looks :) One more thing: Big O often describes the worst-case scenario.

If linear search has a time complexity of O(n) and can indeed be slow with very large inputs, is there a more efficient alternative? Yes, there is, and it's called binary search. Binary search is significantly faster compared to linear search, boasting a time complexity of O(log n). This means that the number of operations required to complete the task grows logarithmically with the input size.

What does O(log n) actually mean? Let's recall some basic math. What is 2 raised to the power of 2? The answer is 4. What is 2 raised to the power of 3? It's 8. Now, what is a logarithm? Simply put, it's the inverse operation of exponentiation. For example, the logarithm base 2 of 8 (written as log₂(8)) is 3, because 2 raised to the power of 3 equals 8.

So, why is this relevant to search algorithms? Imagine we have a sorted collection of integers with a size of 128, and we need to find the element 78. With linear search, we would potentially have to examine every element until we find the target, which isn't very efficient. Binary search offers a much better approach.

To use binary search, the collection must be sorted in ascending order (from the smallest to the largest). So, our input would look something like this: [0, 1, 2, 3, 4, 5, ..., 127].

Looking at this sorted array, we can think about dividing it into two roughly equal halves. The first half would be from index 0 to 63 (since the middle index of 128 elements is around 63.5), and the second half from index 64 to 127. Where do we think our target, 78, might be? It's clearly in the second half. So, do we still need to consider the first half? Not really; we can focus our search on the second half (indices 64-127). With just one comparison (with the middle element), we've effectively halved the search space from N (128) to N/2 (64).

What do we do next? We repeat the same process, but now within our new search boundaries (indices 64 to 127). We find the middle element of this sub-array (around index 95). We compare our target (78) with this middle element. Since 78 is smaller than 95, we know our target must lie in the first half of this sub-array (indices 64 to 94). Again, we've halved our search space.

We continue this process of dividing the search interval in half. In each step, we compare the target value with the middle element of the current interval. If the target is equal to the middle element, we've found it. If the target is smaller than the middle element, we narrow our search to the left half. If the target is larger, we focus on the right half. We keep doing this until the target is found or the search interval becomes empty (meaning the target is not present in the array).

Because we are halving the search space in each step, the number of steps required to find the target (or determine its absence) grows logarithmically with the size of the input. For an array of size N, in the worst case, binary search will take approximately log₂(N) steps. For our example of 128 elements, log₂(128) is 7, which is significantly fewer operations than the potential 128 operations in linear search!

Here's an example implementation of binary search in Go:

package main

import (
    "fmt"
    "sort"
)

func binarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1

    for left <= right {
        mid := (right + left) / 2 // finding the middle index
        if arr[mid] == target {
            return mid // Target found at the middle index
        } else if arr[mid] < target {
            left = mid + 1 // Target is in the right half
        } else {
            right = mid - 1 // Target is in the left half
        }
    }
    return -1 // Target not found
}

func main() {
    numbers := []int{9, 2, 5, 1, 8, 3, 10, 4, 7, 6}
    sort.Ints(numbers) // Important: Binary search requires a sorted array
    fmt.Println("Sorted array:", numbers)

    target := 7
    index := binarySearch(numbers, target)

    if index != -1 {
        fmt.Printf("Element %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Element %d not found in the array\n", target)
    }

    target = 11
    index = binarySearch(numbers, target)

    if index != -1 {
        fmt.Printf("Element %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Element %d not found in the array\n", target)
    }
}

In this Go code, the binarySearch function takes a sorted integer slice arr and an integer target as input. It initializes left and right pointers to the beginning and end of the slice, respectively. The for loop continues as long as the left pointer is less than or equal to the right pointer. In each iteration, it calculates the middle index mid. If the element at arr[mid] is equal to the target, the function returns mid. If arr[mid] is less than the target, it means the target must be in the right half of the slice, so we update left to mid + 1. Otherwise, if arr[mid] is greater than the target, the target must be in the left half, and we update right to mid - 1. If the loop finishes without finding the target, the function returns -1. The main function demonstrates the usage of binarySearch with a sample (unsorted) array, which is then sorted using sort.Ints before the search.

In conclusion, we've explored two fundamental search algorithms: linear search and binary search. While linear search offers a straightforward and intuitive approach by examining each element sequentially, its O(n) time complexity makes it less efficient for large datasets. Binary search, on the other hand, leverages the power of a sorted input to achieve a significantly faster O(log n) time complexity by repeatedly halving the search space. Understanding the strengths and weaknesses of each algorithm, particularly their time complexities, is crucial for choosing the most appropriate search method for a given task and dataset size. As we've seen, even a seemingly simple change in approach can lead to substantial performance improvements, especially when dealing with vast amounts of data.