Сравнить и отсортировать отсортированные разделы массива
Я распараллелил алгоритм, чтобы найти 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++;
}
}
}
}