Simple Sorting Algorithms

Welcome to this practice-based lesson dedicated to Simple Sorting Algorithms. Sorting is one of the most investigated classes of algorithms in computer science. Understanding different methods of organizing data becomes more crucial as data size increases.

In this lesson, we will explore basic sorting algorithms: Bubble, Selection, and Insertion sorts. These are excellent exercises for practicing nested loops and index-based manipulation, and they lay the groundwork for more complex sorting algorithms like QuickSort.

Note: In this lesson, we primarily focus on explaining the logic and step-by-step mechanics. While we provide a code example for Bubble Sort to get you started, the other algorithms are described conceptually. This approach is designed to help you develop the ability to translate conceptual algorithms into code—a vital skill for technical interviews. You will have the opportunity to implement these algorithms in Kotlin during the upcoming practice tasks.

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. With each complete pass, the largest unsorted element "bubbles up" to its correct position.

Step-by-Step Breakdown:

1. Use an outer loop with index i from 0 to the last element to track the number of passes.
2. Use an inner loop with index j from 0 up to n - i - 2 (where n is the array size).
3. Compare the element at index j with the element at j + 1.
4. If the element at j is greater than the element at j + 1, swap them.
5. Optimization: If the inner loop completes without any swaps, the array is already sorted—break the loop.

Kotlin Implementation:

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n) {
        var swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // If no two elements were swapped by inner loop, then break
        if (!swapped) break
    }
}

The Selection Sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

Step-by-Step Breakdown:

1. Use an outer loop with index i that moves from 0 to the second-to-last element.
2. Inside the outer loop, initialize a variable minIndex to i.
3. Use an inner loop with index j starting from i + 1 to the end of the array.
4. If the element at j is smaller than the element at minIndex, update minIndex to j.
5. After the inner loop completes, swap the element at index i with the element at index minIndex.