OJブラシ問題の「二元選択ソート」
Description
注意:この問題は、修正部分としてマークされたコードを提出するだけです.C++言語で提出してください.
2元選択ソート:従来の選択ソートアルゴリズムを改良し、1回の比較過程で、同時に最大値と最小値の位置を記録し、最小値を最初の要素と交換し、最大値と最後の要素と交換し、すなわち1回の比較で2つの要素を決定し、残りのシーケンスに対して上述の過程を繰り返し、シーケンスが空になるまで.
#include using namespace std; int main() { int a[100],i,n; cin>>n; for(i=0; i> a[i]; int j , minpos ,maxpos, tmp; for (i=0 ; i a[maxpos]) { maxpos = j ; continue ; } if (a[j]< a[minpos]) minpos = j ; }/*****修正の開始行******/tmp=a[i]; a[i] = a[minpos]; a[minpos] = tmp; tmp = a[n-i]; a[n-i] = a[maxpos]; a[maxpos] = tmp;/*****修正の終了行*****/}for(i=0;iInput
nとn個の整数
Output
小から大へのソート後の数列
Sample Input
Sample Output
HINT
コードは次のとおりです.
実行結果:
注意:この問題は、修正部分としてマークされたコードを提出するだけです.C++言語で提出してください.
2元選択ソート:従来の選択ソートアルゴリズムを改良し、1回の比較過程で、同時に最大値と最小値の位置を記録し、最小値を最初の要素と交換し、最大値と最後の要素と交換し、すなわち1回の比較で2つの要素を決定し、残りのシーケンスに対して上述の過程を繰り返し、シーケンスが空になるまで.
#include
nとn個の整数
Output
小から大へのソート後の数列
Sample Input
8
12 35 69 84 52 54 75 65
Sample Output
12 35 52 54 65 69 75 84HINT
コードは次のとおりです.
#include<iostream>
using namespace std;
int main()
{
int a[100],i,n;
cin>>n;
for(i=0; i<n; i++)
cin>> a[i];
int j , minpos ,maxpos, tmp;
for (i=0 ; i <n/2; i++)
{
minpos = i;
maxpos = i ;
for (j= i+1; j<= n-i-1; j++)
{
if (a[j] > a[maxpos])
{
maxpos = j ;
continue ;
}
if (a[j]< a[minpos])
minpos = j ;
}
tmp = a[i];
a[i] = a[minpos];
a[minpos] = tmp;
if (maxpos==i)
{
tmp = a[minpos];
a[minpos] = a[n-i-1];
a[n-i-1] = tmp;
}
else
{
tmp = a[maxpos];
a[maxpos] = a[n-i-1];
a[n-i-1] = tmp;
}
}
for(i = 0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
実行結果: