Understanding Quick Sort Algorithm with Kotlin

Hello, curious learners! Today, we will embark on a journey through the Quick Sort world. Picture yourself organizing various items — like toys or books — by size or color. That's what Quick Sort does with spectacular speed. Are you ready to explore further? Fantastic! Let's get started.

Quick Sort is a clever little algorithm invented by a British computer scientist named Tony Hoare in 1959. It uses a strategy called 'divide-and-conquer' to put elements in order. Quick Sort takes an array, selects a particular "pivot" element, and then places everything smaller than the pivot on one side and everything larger on the other.

Quick Sort has a three-step process:

1. Pick a "pivot" element from the array. In our implementation, we'll use the last element as the pivot for simplicity, though in practice, different strategies (like random selection) can be used.
2. Move all elements smaller than the pivot to one side and bigger ones to the other. This operation effectively divides the array into two parts, guaranteeing that all the elements will be kept within their part until the end of the sorting process.
3. Repeat steps 1 and 2 for each part until there are no more unsorted elements.

For example, if we have nine marbles numbered [3, 9, 4, 7, 5, 1, 6, 2, 8] and our chosen marble, or pivot, is 8 (the last element), then after one round of sorting, we'll get [3, 7, 4, 5, 1, 6, 2, 8, 9]. It seems that this is a minor change, but now the pivot element is in its correct position, and we can think of the first half of the array [3, 7, 4, 5, 1, 6, 2] and [9] separately as they won't ever intersect again.

Let's translate these steps into a concrete Kotlin program. We'll tackle it part by part. Our first step is to partition an array around a pivot. In the Kotlin world, we need to write a function, let's call it partition(), to handle this:

fun partition(arr: IntArray, start: Int, end: Int): Int {
    val pivot = arr[end]  // choosing the last element as pivot
    var i = start - 1     // marking the index of smaller element

    for (j in start until end) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] } // swap using Kotlin's 'also'
        }
    }

In this part of the code, we selected the last element as the pivot and placed smaller elements on the left.

1. The function begins by initializing i to one index before start. This i tracks the position where a smaller element has been swapped. If arr[j] is less than or equal to the pivot, i increments and arr[j] is swapped with arr[i] using a concise Kotlin operation.

The start and end parameters dictate the section of the array where partitioning occurs, enabling targeted operations on array segments.