Мой код быстрого выбора не работает так, как должен - PullRequest
Новая
       27

Мой код быстрого выбора не работает так, как должен

1 голос
/ 21 сентября 2019

Мой алгоритм быстрого выбора должен быть быстрее, чем seq.sort + seq(k).Я думаю, что else if (low.length == 0) a(pivot) неверно, и я думаю, что мой алгоритм слишком медленный для тестов.

Некоторые результаты для кода: 

Running performance tests on almost-sorted sequences
 Test 1
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 2
  quickSelect vs Arrays.sort: 0,0156 vs 0,0313
 Test 3
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 4
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 5
  quickSelect vs Arrays.sort: 0,0469 vs 0,0156

Testing quickSelect.find(List(1), 0)
Testing quickSelect.find(List(1, 1, 1, 1), 0)
Testing quickSelect.find(List(1, 1, 1, 1), 1)
Testing quickSelect.find(List(1, 1, 1, 1), 2)
Testing quickSelect.find(List(1, 1, 1, 1), 3)
Testing quickSelect.find(List(1, 2, 3), 0)
Testing quickSelect.find(List(1, 2, 3), 1)
- should compute correct results on some selected inputs *** FAILED ***
  1 was not equal to 2

  val rand = new scala.util.Random(21)

def find(seq: Seq[Int], k: Int): Int = {
  require(0 <= k && k < seq.length)
  val a: Array[Int] = seq.toArray[Int]
  val pivot = rand.nextInt(a.length)     
  val (low, high) = a.partition(_ < a(pivot))
  if (low.length == k-1) a(pivot)
  else if (low.length == 0) a(pivot)
  else if (low.length <= k) find(high, k - low.length)
  else find(low, k) 
}
...