Гайки и болты
Здравствуйте.
С помощью метода быстрой сортировки работающего по принципу разделяй и властвуй решить следующую задачу. "Гайки и болты": Неорганизованный плотник имеет смешанный набор N гаек и N болтов. Цель состоит в том, чтобы найти соответствующие пары гаек и болтов. Каждая гайка соответствует точно одному болту, и каждый болт соответствует точно одной гайке. Соединяя гайку и болт между собой, плотник может узнать из них больше (однако он не может сравнивать непосредственно две гайки или два болта). Разработайте алгоритм для этой задачи, который использует в среднем N log(N) сравнений.
Метод быстрой сортировки:
private void quickSort(int[] array, int start, int end)
{
if (start >= end) return;
int pivot = array[start];
int i = start;
int j = end;
int temp = 0;
while (i <= j)
{
while (array[i] < pivot)
{
i++;
}
while (array[j] > pivot)
{
j--;
}
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (start < j)
{
quickSort(array, start, j);
}
if (i < end)
{
quickSort(array, i, end);
}
}
Прошу помощи в решении задачи, буду очень благодарен.