ページ 1 ／ 1
昇順ソートと降順ソート
Posted: 2015年5月23日(土) 00:10
by RaiseBB
現在visualstudio2010という環境の下でプログラムを組んでいます。
現在、入力された数値を配列に保存して、その配列を昇順、降順に並べ替える処理を考えています。
例えば入力された数値が配列の小さい方から, 2 9 3 7 4 だとすると、
出力は 2 3 4 7 9 となります。
今考えているソートの手順としては
29374
23974
23794
23749
23479
という風な足取りをたどって、ソートしたいと考えています。
理想としては、最大数から順番に決まっていく方式です(下に書き記す)
29374
23749
23479
という風に記述することができれば上に書いた方式よりも処理速度が向上すると考えています。
上記処理、理想でも、今考えているソートでもいいので、書き記すためのヒントをいただけないでしょうか
現在考えているコードはこちらになります。
for (int k = 0; k < 5; k++)
{
if (a[k]>a[k + 1])
{
hozon = a[k];
a[k] = a[k + 1];
a[k + 1] = hozon;
}
}
まだ、あまり練れていないのでかなりのミスを犯していると思います。
よろしくおねがいします
Re: 昇順ソートと降順ソート
Posted: 2015年5月23日(土) 00:18
by みけCAT
RaiseBB さんが書きました:今考えているソートの手順としては
29374
23974
23794
23749
23479
という風な足取りをたどって、ソートしたいと考えています。
理想としては、最大数から順番に決まっていく方式です(下に書き記す)
29374
23749
23479
という風に記述することができれば上に書いた方式よりも処理速度が向上すると考えています。
「今考えているソート」「理想」ともにバブルソートでしょうか？
バブルソートなのでどちらもO(N^2)ですが、「理想」は出力の量が少ない分処理速度が向上しそうですね。
RaiseBB さんが書きました:上記処理、理想でも、今考えているソートでもいいので、書き記すためのヒントをいただけないでしょうか
二重ループを用います。
外側のループは単純に(配列の要素数)回繰り返します。
内側のループは簡単のため(配列の要素数-1)回回し、配列の「小さい方」から順にチェックし、次の要素の方が大きければ入れ替えます。
「今考えているソート」では入れ替えたら配列の内容を出力し、
「理想」では内側のループが終了し、かつ今回の内側のループで入れ替えが起きていたら配列の内容を出力すればいいと思います。
Re: 昇順ソートと降順ソート
Posted: 2015年5月23日(土) 00:22
by RaiseBB
みけCATさん素早い回答をありがとうございます。
考えているソート方法はバブルソートで間違いないです。
二重ループを利用したコードを書いてみます！
Re: 昇順ソートと降順ソート
Posted: 2015年5月23日(土) 00:25
by みけCAT
実装例です。
► スポイラーを表示
コード:
#include <stdio.h>
void print_array(const int a[], int n) {
int k;
for (k = 0 ; k < n; k++) {
printf("%d", a[k]);
}
putchar('\n');
}
void sort1(int a[], int n) {
int j, k, hozon;
print_array(a, n);
for (j = 0; j < n; j++) {
for (k = 1; k < n; k++) {
if (a[k - 1] > a[k]) {
hozon = a[k - 1];
a[k - 1] = a[k];
a[k] = hozon;
print_array(a, n);
}
}
}
}
void sort2(int a[], int n) {
int j, k, hozon, irekawatta;
print_array(a, n);
for (j = 0; j < n; j++) {
irekawatta = 0;
for (k = 1; k < n; k++) {
if (a[k - 1] > a[k]) {
hozon = a[k - 1];
a[k - 1] = a[k];
a[k] = hozon;
irekawatta = 1;
}
}
if (irekawatta) {
print_array(a, n);
}
}
}
int main(void) {
int array1[5] = {2, 9, 3, 7, 4};
int array2[5] = {2, 9, 3, 7 ,4};
puts("----- sort1 -----");
sort1(array1, 5);
puts("----- sort2 -----");
sort2(array2, 5);
return 0;
}
Re: 昇順ソートと降順ソート
Posted: 2015年5月23日(土) 00:27
by RaiseBB
無事に出力することが出来ました。
降順は昇順の手順を少しいじればできそうなので、自力で取り組もうと思います。
素早い回答本当にありがとうございました！