Advanced Sorting Algorithms and Their Practical Applications

Introduction to the Lesson

Welcome to this insightful session, where our aim is to master the complexities of the illustrious applications of sorting algorithms . Today's voyage links two problems: "Find the K-th Ordinal Statistic in a List" and "Count the Number of Inversions in a List." These problems mirror practical scenarios, and the efficient techniques used to solve them present valuable demonstrations of the application of sorting algorithms . By solving these two problems, we'll see how Quick Sort and Merge Sort knowledge applies here and helps provide efficient implementations for both questions. Let's dive into these captivating problems!

Problem 1: Find the K-th Ordinal Statistic in a List

Our first problem presents a list of integers and the number k . The challenge is finding the k -th smallest element in that given list. To further elucidate, for k = 1, you are seeking to find the smallest element; if k = 2, you're searching for the second smallest element, and so on. By the conclusion of this lesson, you'll be highly skilled at performing this task!

Problem 1: Naive Approaches

O(n^2)

Problem 1: Efficient Approach Explanation

The Quick Sort algorithm, a splendid application of divide and conquer, can solve this problem efficiently. By selecting the right pivot for partitioning, the input list is divided into two: a left partition, which contains elements less than the pivot, and a right partition, which includes elements greater than the pivot. In Go, arrays and slices are useful for managing groups of data. We must handle their positions carefully to avoid mistakes. We also use recursive functions, which call themselves, to solve problems with these groups. In recursion, if a pivot’s position matches k, we’ve found our answer. If the pivot is smaller than k, we focus on the right side; otherwise, we look at the left side.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 1: Implementation and Explanation

We will implement the solution bit by bit, starting with the partition function:

func partition(arr []int, start, end int) int {
    pivot := arr[end]
    i := start - 1

    // Rearrange elements based on pivot
    for j := start; j < end; j++ {
        if arr[j] <= pivot {
            i++
            // Swap elements to place element <= pivot on the left
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // Place pivot in its correct position
    arr[i+1], arr[end] = arr[end], arr[i+1]
    return i+1 // return pivot position
}

func partition(arr []int, start, end int) int {
    pivot := arr[end]
    i := start - 1

    // Rearrange elements based on pivot
    for j := start; j < end; j++ {
        if arr[j] <= pivot {
            i++
            // Swap elements to place element <= pivot on the left
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // Place pivot in its correct position
    arr[i+1], arr[end] = arr[end], arr[i+1]
    return i+1 // return pivot position
}

The partition function rearranges the elements in the array segment between start and end using the last element as the pivot. Elements less than or equal to the pivot are moved to the left, while elements greater than the pivot are on the right. The final position of the pivot is returned, indicating the division between left and right partitions.

Next we will delve into the kthSmallest function:

func kthSmallest(arr []int, start, end, k int) int {
    if k > 0 && k <= end-start+1 {
        pos := partition(arr, start, end) // Partition the array
        // Check if pivot position is the k-1 index
        if pos-start == k-1 {
            return arr[pos] // Found the k-th smallest element
        }
        // Search left subarray
        if pos-start > k-1 {
            return kthSmallest(arr, start, pos-1, k)
        }
        // Search right subarray
        return kthSmallest(arr, pos+1, end, k-pos+start-1)
    }
    return math.MaxInt // Return max int if no valid k-th smallest found
}

func kthSmallest(arr []int, start, end, k int) int {
    if k > 0 && k <= end-start+1 {
        pos := partition(arr, start, end) // Partition the array
        // Check if pivot position is the k-1 index
        if pos-start == k-1 {
            return arr[pos] // Found the k-th smallest element
        }
        // Search left subarray
        if pos-start > k-1 {
            return kthSmallest(arr, start, pos-1, k)
        }
        // Search right subarray
        return kthSmallest(arr, pos+1, end, k-pos+start-1)
    }
    return math.MaxInt // Return max int if no valid k-th smallest found
}

The kthSmallest function uses the partition function to find the position of the pivot. It recursively searches the appropriate partition for the k-th smallest element. If the pivot's position aligns with the (k-1) index, the k-th smallest element has been found. Otherwise, it continues the search in the left or right subarray based on the pivot's position.

Finally, the findKthSmallest function:

func findKthSmallest(numbers []int, k int) (int, error) {
    if numbers == nil || len(numbers) < k {
        return math.MinInt, fmt.Errorf("invalid input")
    }
    return kthSmallest(numbers, 0, len(numbers)-1, k), nil
}

func findKthSmallest(numbers []int, k int) (int, error) {
    if numbers == nil || len(numbers) < k {
        return math.MinInt, fmt.Errorf("invalid input")
    }
    return kthSmallest(numbers, 0, len(numbers)-1, k), nil
}

The findKthSmallest function serves as the main interface, validating the input list and its size relative to k. It initiates the recursive search for the k-th smallest element by calling the kthSmallest function, ensuring robust handling of edge cases such as invalid input data.

Problem 2: Solution and Efficient Approach Explanation

Again we will build our solution little by little. We will first create a supporting structure that we will use in the solution:

type Result struct {
    sorted    []int  // slice to store the sorted version of the array
    inversions int   // count of inversions found
}

This structure will hold sorted slices as well as the count of inversions found.

Next, we will write the mergeAndCountInversions function:

// Merges subarrays while counting inversions.
func mergeAndCountInversions(left, right []int) Result {
    merged := make([]int, 0, len(left)+len(right))
    i, j, inversions := 0, 0, 0

    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            merged = append(merged, left[i]) // Append left element
            i++
        } else {
            merged = append(merged, right[j]) // Append right element
            j++
            inversions += len(left) - i // Count inversions
        }
    }
    // Append remaining elements
    merged = append(merged, left[i:]...)
    merged = append(merged, right[j:]...)

    return Result{sorted: merged, inversions: inversions}
}

The mergeAndCountInversions function merges two sorted subarrays while counting inversions. During the merge, if an element in the right subarray is smaller than an element in the left, every remaining element in the left subarray is an inversion with the right element. This function returns both the merged array and the count of inversions, maintaining an efficient $O(n \log n)$ complexity like the standard merge process.

Finally, we get to the countInversions function:

func countInversions(arr []int) Result {
    if len(arr) <= 1 {
        return Result{sorted: arr, inversions: 0}
    }
    middle := len(arr) / 2
    left := countInversions(arr[:middle])
    right := countInversions(arr[middle:])
    result := mergeAndCountInversions(left.sorted, right.sorted)
    return Result{sorted: result.sorted, inversions: left.inversions + right.inversions + result.inversions}
}

The countInversions function applies a modified merge sort to count inversions. It recursively splits the array into halves and sorts each while counting inversions in subarrays. Upon merging, it accumulates the inversions found via mergeAndCountInversions along with those identified individually in the left and right subarrays. This approach efficiently calculates the total number of inversions, maintaining the efficient $O(n \log n)$ complexity characteristic of merge sort.

// Merges subarrays while counting inversions. func mergeAndCountInversions(left, right []int) Result { merged := make([]int, 0, len(left)+len(right)) i, j, inversions := 0, 0, 0 for i < len(left) && j < len(right) { if left[i] <= right[j] { merged = append(merged, left[i]) // Append left element i++ } else { merged = append(merged, right[j]) // Append right element j++ inversions += len(left) - i // Count inversions } } // Append remaining elements merged = append(merged, left[i:]...) merged = append(merged, right[j:]...) return Result{sorted: merged, inversions: inversions} }

func countInversions(arr []int) Result { if len(arr) <= 1 { return Result{sorted: arr, inversions: 0} } middle := len(arr) / 2 left := countInversions(arr[:middle]) right := countInversions(arr[middle:]) result := mergeAndCountInversions(left.sorted, right.sorted) return Result{sorted: result.sorted, inversions: left.inversions + right.inversions + result.inversions} }