氣泡排序
請實作 bubble sort 並計算出排序完成至少需要 swap 幾次
Input
第一行請輸入測資比數 N
每一筆的測資都會有兩行,第一行為總長度 L (0 ≤ L ≤ 50),第二行為從 1 到 L 的排列組合
現在要將此序列由小到大重新排列。
Output
每組測資請輸出”Optimal swapping takes S swaps.” ,S 為 swap 次數
範例輸入:
3
3
1 3 2
4
4 3 2 1
2
2 1
範例輸出:
Optimal swapping takes 1 swaps.
Optimal swapping takes 6 swaps.
Optimal swapping takes 1 swaps.
/*----- ----- ----- -----*/ //1-bubble //Made by 105502555 Teemo Hsu(Synasaivaltos) //Date: 2018/03/21 /*----- ----- ----- -----*/ #include <iostream> #include <vector> using namespace std; int main(void) { int n; cin >> n; vector<int> ans; while(--n>=0) { int m; cin >> m; vector<int> l; ans.push_back(0); for(int i=0,j;i<m;cin>>j,l.push_back(j),i++); for(int i=l.size()-1;i>=0;i--) { for(int j=0;j<i;j++) { if(l.at(j)>l.at(j+1)) { swap(l.at(j),l.at(j+1)); ans.at(ans.size()-1)++; } } } } for(int i=0;i<ans.size();cout<<"Optimal swapping takes "<<ans.at(i)<<" swaps.\n",i++); return 0; } |