Динамические массивы c++

[cheef]

Задание:
Дана матрица целых чисел. Упорядочить ее строки по возрастанию значений их наибольших элементов.

Я всё реализовал, кроме самого сложного, сортировки, не могу придумать алгоритм, может быть подкинете идей, или примеров.

#include<stdio.h> 
#include<math.h>
#include<stdlib.h>

void sort(int **array, int dim1, int dim2)
{

}

int** submain(int &dim1, int &dim2)
{
    int wDim,i,j;
    printf("Введите размерность M: ");
    scanf("%d",&dim1);
    printf("Введите размерность N: ");
    scanf("%d",&dim2);
    wDim = dim2;
    int **array = new int*[dim1];
    for (i = 0; i < dim1; i++, wDim--) array[i] = new int[wDim];
    for (i = 0; i < dim1; i++) 
        for(j = 0; j < dim2; j++) scanf("%d",&array[i][j]);
    system("clear");
    printf("Ваша матрица: \n");
    for (i = 0; i < dim1; i++) {
        for(j = 0; j < dim2; j++)  printf("%d ",array[i][j]);
        printf("\n");
    }
    return array;
}

int main()
{
    system("clear");
    int dim1, dim2;
    int **pr = submain(dim1,dim2);
    sort(pr, dim1, dim2);
}

[cheef]

Помощь нужна поскорее, поэтому подниму тему.

[p51x]

а что придумывать создаете массив и в него пишете ваши максимумы, потомего сортируете и раставляете строки

[cheef]

Я сам пробовал писать, смог найти максимальные элементы строк. И добавить их во второй массив с индексами строк, в которых они находятся, потом отсортировал полученный массив по возрастанию элементов:

void sort(int **array, int dim1, int dim2)
{
    int i,j,a[2][dim2],dump,max,k = 0;
    for(i = 0; i < dim1; i++) {
        max = array[i][0];
        for(j = 1; j < dim2; j++)
            if (array[i][j] > max) {
                max = array[i][j];
                a[0][i] = max;
                a[1][i] = i;
            }
    }
    for (i = 0; i < dim1; i++) 
        for(j = 0; j < dim2 - 1; j++)
        if (a[0][j] > a[0][j+1])
        {
            dump = a[0][j];
            a[0][j] = a[0][j+1];
            a[0][j+1] = dump;
            dump = a[1][j];
            a[1][j] = a[1][j+1];
            a[1][j+1] = dump;
        }
    for (i = 0; i < dim1; i++)
        printf("%d | %d\n",a[0][i],a[1][i]);
}

Получилось примерно такое:
На вводе:
3 5 7
0 0 1
4 5 9
На выходе:
1 столбик максимальный элемент, 2-ой № строки этого элемента.
1 | 1
7 | 0
9 | 2
И вот тут я встаю в ступор, не могу придумать алгоритм, даже не знаю с чего начать, и начинаю делать другую лабу, мне бы простой пример, или наводку.
Осталось почти самое лёгкое, а у меня мозг кончился.

[cheef]

Пардоньте, решил не маяться и не сортировать массив, просто добавил в конец:

   
for (i = 0; i < dim1; i++) {
        max = a[1][i];
        for(j = 0; j < dim2; j++)
            printf("%d ",array[max][j]);
        printf("\n");
    }

Надеюсь препод не станет придираться.