[演算法] 以UVA第10107程式題目複習Insertion Sort

首先複習一下 Insertion Sort。

Insertion Sort       
Insertion Sort的精神是當在排序一個數字陣列時，每當處理一個數字，就代表在這個數字之前的數都已經排序好了。因此只需要將這個數字跟前面排好的數字序列比較，並將目前處理的這個數字insert到之前排序好的序列中，就像一般在玩撲克牌時通常會使用的排序法。

        以下是我練習將InsertionSort的Code用C++寫出：
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
UVA #10107(What is the median)
這個題目給的Sample Input跟Sample Output如下：

Sample Input

1
3
4
60
70
50
2

Sample Output

1
2
3
3
4
27
4

        本題的目標為每從Sample Input讀進一個數字到序列中，就找出當下的中位數(median)，如果總共有奇數個數字，則將取排序好的數列的中間兩個數字相加除以2，除以2後只取整數部分。

思考方式：
        使用Insertion Sort的原因，是因為這題是每讀到一個數字就做排序，所以當讀進一個新數字時，之前的讀過的數字都已經排序好了，所以只須將新讀入的數字Insert到前面排序好的序列的適當位置，這很符合Insertion Sort的基本概念。

以下是我解決此題目的Code：(implement using C++)

//main.cpp
//The excution result is correct, and is accepted by UVA Online Judge.
//This is the code for UVA Online Judge #10107
//This code was created by Uncle on 2012/03/03
#include<iostream>
#include<sstream>
#include<fstream>
using namespace std;
int *data = NULL;
int size = 0;

int *Expand(int *arrReceive,int &s,int key)
{
    int *newArr = new int [s+1];
    for(int i=0;i<s;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[s] = key;
    delete []arrReceive;
    s++;
    return newArr;
}
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
int main()
{
    int key;
    ifstream inputFile;
    //inputFile.open("input.txt",ifstream::in);
    while(cin >> key)
    {
                    data = Expand(data,size,key);
                    InsertionSort();
                    if(size%2)  //total size is odd
                    {
                              cout << data[size/2] << endl;
                    }
                    else
                    {
                        int tmp = data[(size/2)-1] + data[size/2];
                        tmp = tmp/2;
                        cout << tmp << endl;
                    }
    }
    //getchar();
    return 0;
}

---