Сравнить и отсортировать отсортированные разделы массива

Я распараллелил алгоритм, чтобы найти k самых больших чисел в массиве int[], не создавая новый массив и не уничтожая ни одно из существующих чисел. Вместо этого массив разбивается на секции, и каждая секция находит свои k самых больших чисел.

Например, список [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] разделить на две части (дано k = 5) будет выглядеть так:

[10, 9, 8, 7, 6, 1, 2, 3, 4, 5, 20, 19, 18, 17, 16, 11, 12, 13, 14, 15],

Конечно, цифры на самом деле гораздо больше и случайнее. Кроме того, не будет только двух разделов, но потенциально, например. 8. с отсортированными частями 0+start -> k+start (например, 0, 4 / 10, 14 в примере выше).

Мой вопрос: как мне сравнить любое количество таких разделов, чтобы первый раздел списка, в конце концов, содержал k самых больших чисел списка?

Моя текущая попытка не решает проблему, но, пожалуйста, не стесняйтесь предлагать решения. Я не заинтересован в сортировке слиянием, так как это требует объединения всех списков - я хочу сравнить только первый раздел со всеми остальными.

Код:

public void sammenlignOmraader()
{
if (n/k < startListe.length)  //If the amount of numbers to find is greater than what can be stored in one area only
{

}
else
{
  int hovedStart = startListe[0];
  for(int i = 1; i < startListe.length; i++)
  {
    int annenStart = startListe[i];
    for(int ii = annenStart; ii < k + annenStart; ii++)
    {
      System.out.println("ii er " + ii + ", k er " + k + ", k + annenstart er " + (k + annenStart));
      System.out.println("hovedStart er " + hovedStart + ", annenStart er " + annenStart);
      if (a[hovedStart] < a[ii])
      {
        int temp1 = a[hovedStart];
        a[hovedStart] = a[ii];
        for(int iii = hovedStart+1; iii < iii+k; iii++)
        {
          //System.out.println("iii er " + iii + ", a.length er " + a.length);
          if (iii == a.length)
          {
            return;
          }
          int temp2 = a[iii];
          a[iii] = temp1;
          temp1 = temp2;
        }
      }
      hovedStart++;
    }
  }
}
}

0 ответов

Другие вопросы по тегам