UVA 10327 - Flip Sort

題目:

排序在電腦科學中是一個重要的部分。已經有許多優秀的排序演算法被提出。在這個問題中我們將討論一種排序的方式，就是你只能交換相鄰的2個元素。如果你想一下的話，你會瞭解以這樣的方式總是可以將一些數字排序。（註：我們通常稱這種排序方式為Bubble Sort）

給你一串整數，請你用上述的方法來將之由小到大排序。要請你求出最少要交換幾次。例如給你"1 2 3"，那需要交換的次數為0，因為已經排好了。如果給你"2 3 1"，則最少需要交換2次才可排好序。（"2 3 1" -> "2 1 3" -> "1 2 3"）

Input
每組測試資料的第一列有1個整數N（N <= 1000）。代表以下會有N個待排序的整數。接下來的N個整數，就是那些待排序的數。請參考Sample Iutput

Output
如題目所述，請參考Sample Output

Sample Input #1
3
1 2 3
3
2 3 1

Sample Output #1
Minimum exchange operations : 0
Minimum exchange operations : 2

C++ code:

**Bubble sort**

#include<bits/stdc++.h>

using namespace std;

int main(){
    int t;
    while (cin >> t) {
       int sum = 0; 
       vector<int> a(t);
       for (int i = 0; i < t; ++i) {
           cin >> a[i]; 
       } 
       for (int i = 0; i < t - 1; ++i) {
           for (int j = i + 1; j < t; ++j) {
               if (a[i] > a[j]) {
                   sum++; 
               } 
           } 
       }
       cout << "Minimum exchange operations : " << sum << endl;
    }
}