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.

Insertion Sort builds a sorted portion of the array one element at a time by picking a "key" and shifting larger elements to the right.

Step-by-Step Breakdown:

1. Use an outer loop with index i starting from 1 to the end of the array.
2. Store the value at array[i] in a variable called key.
3. Initialize an inner index j as i - 1.
4. Use a while loop that runs as long as j >= 0 and the element at array[j] is greater than the key.
5. Inside the while loop, move array[j] one position to the right (array[j + 1] = array[j]) and decrement j.
6. Once the loop ends, place the key at its correct position: array[j + 1] = key.

Before we wrap up, let's peek into more complex territory by examining QuickSort and Merge Sort, which are popular divide-and-conquer sorting algorithms.

QuickSort works by picking a pivot element and partitioning the array around it.

Step-by-Step Breakdown:

1. Base Case: If the range has fewer than two elements, return (it is already sorted).
2. Partition: Pick a pivot (often the last element). Use a pointer i to track the boundary of elements smaller than the pivot.
3. Rearrange: Iterate through the range with index j. If array[j] is less than the pivot, increment i and swap array[i] with array[j].
4. Place Pivot: After the loop, swap the pivot with array[i + 1]. The pivot is now at its final sorted index.
5. Recursion: Recursively apply the same steps to the sub-array before the pivot and the sub-array after the pivot.

Merge Sort functions by recursively dividing the array into halves until each subarray contains only one element, then merging them back in order.

Step-by-Step Breakdown:

1. Base Case: If the array length is 1, return it.
2. Divide: Find the middle point and split the array into a left half and a right half.
3. Recursion: Recursively call Merge Sort on the left half and the right half.
4. Merge: Create a function to merge two sorted arrays. Compare the front elements of both halves, pick the smallest, and move it into a new temporary array.
5. Repeat: Continue comparing and moving elements until all elements from both halves are combined into the temporary array in sorted order.

Now that we have looked at the conceptual frameworks and the step-by-step logic for these algorithms, you have a strong foundation in how data can be reorganized. These foundational algorithms reinforce your understanding of loops and conditional logic. Happy learning, and let's sort it out!