Finding the k-th largest element from the array effectively and simply as well

benchmark.rb

require 'benchmark'

examples = []

res1 = []
res2 = []

def f1(arr, k)
  arr.sort[arr.size - k]
end

def f2(arr, k)
  left  = 0
  right = arr.size - 1
  f     = arr.size - k
  pivot = -1

  while left <= right do
    pivot = partition(arr, left, right)

    if pivot == f
      return arr[pivot]
    elsif pivot < f
      left = pivot + 1
    else
      right = pivot - 1
    end
  end
end

def partition(arr, left, right)
  pivot = left

  while left < right do
    if arr[left] < arr[right]
      arr[pivot], arr[left] = arr[left], arr[pivot]
      pivot += 1
    end

    left += 1
  end

  arr[pivot], arr[right] = arr[right], arr[pivot]

  return pivot
end

Benchmark.bm do |x|
  8.times do |i|
    x.report("populate##{i}") {  examples << Array.new(10**i) { rand(1..1_000_000) } }
  end

  examples.each_with_index do |a, i|
    x.report("sort##{i}") { res1 << f1(a, 3) }
  end

  examples.each_with_index do |a, i|
    x.report("partition##{i}") { res2 << f2(a, 3) }
  end
end

p res1
p res2
puts res1 == res2

find_kth_largest_element.go

package main

import "fmt"
// An algorithm to find the k-th largest element from the array
// Time complexity is O(2n)
// Space complexity is a few pointers and swaps the elements
func main() {
  fmt.Println(findKthLargestElement([]int{15, 16, 11, 18, 12, 3, 4, 5, 0, 6}, 3)) // The answer should be 15
}

// Assumptions:
// - K is in range [1, length]
// - The array has at least one element
func findKthLargestElement(arr []int, k int) int {
  left := 0
  right := len(arr) - 1

  for left <= right {
    pivatIndex := partition(arr, left, right)

    if pivatIndex == len(arr) - k {
      return arr[pivatIndex]
    } else if  pivatIndex < len(arr) - k {
      left = pivatIndex + 1
    } else {
      right = pivatIndex - 1
    }
  }

  return -1 // means error
}

func partition(arr []int, left, right int) int {
  fmt.Println("In: ", arr, left, right)
  index := left
  pivot := arr[right]

  for left < right {
    if arr[left] <= pivot {
      arr[left], arr[index] = arr[index], arr[left]
      index += 1
    }

    left += 1
  }

  arr[right], arr[index] = arr[index], arr[right]

  fmt.Println("Out: ", arr, index)
  return index
}

➜  t git:(master) ✗ ruby main.rb
       user     system      total        real
populate#0  0.000015   0.000008   0.000023 (  0.000014)
populate#1  0.000006   0.000001   0.000007 (  0.000006)
populate#2  0.000021   0.000001   0.000022 (  0.000020)
populate#3  0.000184   0.000000   0.000184 (  0.000184)
populate#4  0.001812   0.000011   0.001823 (  0.001843)
populate#5  0.019328   0.000751   0.020079 (  0.020552)
populate#6  0.165104   0.003294   0.168398 (  0.169463)
populate#7  1.692712   0.034309   1.727021 (  1.869228)
sort#0  0.000005   0.000000   0.000005 (  0.000006)
sort#1  0.000005   0.000000   0.000005 (  0.000006)
sort#2  0.000012   0.000000   0.000012 (  0.000012)
sort#3  0.000131   0.000005   0.000136 (  0.000159)
sort#4  0.001695   0.000274   0.001969 (  0.002252)
sort#5  0.018297   0.000565   0.018862 (  0.018984)
sort#6  0.217828   0.005129   0.222957 (  0.223939)
sort#7  2.148376   0.055332   2.203708 (  2.216425)
partition#0  0.000006   0.000000   0.000006 (  0.000007)
partition#1  0.000004   0.000000   0.000004 (  0.000005)
partition#2  0.000021   0.000001   0.000022 (  0.000022)
partition#3  0.000222   0.000023   0.000245 (  0.000270)
partition#4  0.001777   0.000241   0.002018 (  0.002293)
partition#5  0.013155   0.000123   0.013278 (  0.013398)
partition#6  0.130963   0.000616   0.131579 (  0.132249)
partition#7  0.979549   0.003607   0.983156 (  0.991038)
[nil, 607210, 968721, 997482, 999901, 999964, 999994, 1000000]
[nil, 607210, 968721, 997482, 999901, 999964, 999994, 1000000]
true
➜  t git:(master) ✗