Structure

d550 : 物件排序

內容：

Excel 的排序，使用上真是有點麻煩
現在請你先對第一列先做排序，
若還是相同，再比較第二列 ...類推 ( 由小→大 )

輸入說明：

每組輸入的第一行會有兩個數字 N M  ( 1 ≦ N ≦ 1,0000 , 1 ≦ M ≦ 200 )

分別代表接下來有 N 行 , 每行上有 M 個數字 P ( 0 ≦ P ≦ 2147483647 )

輸出說明：

請輸出排序後的結果。

範例輸入：

8 3
1 1 2
1 0 1
1 1 1
1 3 2
1 3 5
2 1 1
2 3 2
2 1 4

範例輸出：

1 0 1
1 1 1
1 1 2
1 3 2
1 3 5
2 1 1
2 1 4
2 3 2

題目連結 ： https://zerojudge.tw/ShowProblem?problemid=d550

思考 ： 用之前教的二維陣列跟排序該怎麼做呢？

• Insertion Sort, Selection Sort, Bubble Sort....
• 二維陣列該怎麼存輸入呢
• 怎麼比較兩筆資料的大小
• 兩筆資料要交換時，該怎麼交換

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[10005][205];

int main(){

    cin >> N >> M;

    //輸入二維陣列的每個值
    for ( int i = 0 ; i < N ; i++ )
        for ( int j = 0 ; j < M ; j++ )
            cin >> arr[i][j];


    for ( int i = 0 ; i < N ; i++ ){
        //看到先取最小值的sort，應該是seletion sort
        int mPtr = i;

        for ( int j = i+1 ; j < N ; j++ )

            if ( 比較 arr[j] ? arr[mPtr] ) // 這邊要怎麼改
                ...
                ... 交換兩個



    }

    //輸出結果
    for ( int i = 0 ; i < N ; i++ ){
        for ( int j = 0 ; j < M ; j++ )
            cout << arr[i][j] << " ";
        cout << endl;
    }


    return 0;
}

比較兩個大小方法

bool isBigger( int i , int j ){
    // 看看 arr[i] 是否比 arr[j] 大

    for ( int k = 0 ; k < M ; k++ )
        if ( arr[i][k] != arr[j][k]  ){
            if ( arr[i][k] > arr[j][k] )
                return true;
            else
                return false;
        }

    // 到這裡代表兩個完全一樣，回傳 true or false 都可

    return false;

}

更精簡一點的寫法

bool isBigger( int i , int j ){
    // 看看 arr[i] 是否比 arr[j] 大

    for ( int k = 0 ; k < M ; k++ )
        if ( arr[i][k] != arr[j][k]  )
            return arr[i][k] > arr[j][k];

    // 到這裡代表兩個完全一樣，回傳 true or false 都可

    return false;

}

所以我們現在可以用 isBigger( i , j ) 來查看 arr[i] 這筆資料 是否比 arr[j] 大

如果知道 arr[i] > arr[j]，要怎麼把這兩筆資料交換呢？

交換兩排陣列方法

void arraySwap( int i , int j ){

    // 交換 arr[i] 整排與 arr[j] 整排
    for ( int k = 0 ; k < M ; k++ )
        swap( arr[i][k], arr[j][k] );
        //逐一交換

}

我們現在把他們整合在一起

完整版

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[10005][205];

bool isBigger( int i , int j ){
    // 看看 arr[i] 是否比 arr[j] 大

    for ( int k = 0 ; k < M ; k++ )
        if ( arr[i][k] != arr[j][k]  )
            return arr[i][k] > arr[j][k];

    // 到這裡代表兩個完全一樣，回傳 true or false 都可

    return false;

}


void arraySwap( int i , int j ){

    // 交換 arr[i] 整排與 arr[j] 整排
    for ( int k = 0 ; k < M ; k++ )
        swap( arr[i][k], arr[j][k] );
        //逐一交換

}

int main(){

    cin >> N >> M;

    for ( int i = 0 ; i < N ; i++ )
        for ( int j = 0 ; j < M ; j++ )
            cin >> arr[i][j];

    for ( int i = 0 ; i < N ; i++ ){
        int mPtr = i;

        for ( int j = i+1 ; j < N ; j++ )
            if ( isBigger( mPtr, j ) ) 
               mPtr = j;

        arraySwap( i, mPtr );

    }

    for ( int i = 0 ; i < N ; i++ ){
        for ( int j = 0 ; j < M ; j++ )
            cout << arr[i][j] << " ";
        cout << endl;
    }


    return 0;
}

到這裡，有沒有覺得頭昏眼花？

沒關係，我們要來介紹一個新的寫法，先來看下一章範例：