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

import "sort"

func kthSmallestNaive(inputArray []int, k int) int {
    sort.Ints(inputArray)
    return inputArray[k-1]
}

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
}

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
}

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
}

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

// 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}
}

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 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 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
}

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

// 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}
}

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}
}

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}
}