The sorting algorithm should be O(N log N) instead of O(N^2) -- I
suggest Quicksort. Here is one version in C++:
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
int partition(int a[], int left, int right)
{
int pivot = a[left];
int i = left;
for (int j = left + 1; j <= right; j++) {
if (a[j] < pivot) {
i++;
swap(a[j], a[i]);
}
}
swap(a[left], a[i]);
return i;
}
void quicksort(int a[], int left, int right)
{
if (right <= left) return;
int i = partition(a, left, right);
quicksort(a, left, i - 1);
quicksort(a, i + 1, right);
}