選択ソート
整列
整列 バブルソート、選択ソートの演習
選択ソート（ここ）
バブルソート
整列 文字列のソートの演習
整列 クイックソート、ヒープソートの演習
選択ソートで配列の sからe までをならべかえるプログラムの本体(プログラムの断片)はつぎのようになる
選択して取り出し、残りをソートする。
code:sortselectrecursivefunction.c
void sort_select(int dat[], int s, int e){
int maxi, w;
if( s == e ) return;
maxi = dat_max(dat, s, e); // 最大のデータがある添字
// swap datmaxi<->dats 最大のデータを dats に置き
w = datmaxi;
datmaxi = dats;
dats = w;
sort_select(dat, s+1, e); // 残り（s+1 から e まで）をソートする
}
メモ　dat 5, | 3, 1, 2, 4 , s=0, maxi=1, w=5, e=4 sort_select(dat, 1, 4)
全体は次のとおり
code:sortselectrecursive.c
#include<stdio.h>
#include<stdlib.h>
#define DATNUM 10 //ソートするデータ数
/* ----- prototypes ----- */
void dat_print(int dat[], int n);
void dat_set(int dat[], int n);
int dat_max(int dat[], int s, int e);
void sort_select(int dat[], int s, int e);
/* ----- main ----- */
int main(void){
int datDATNUM;
dat_set(dat, DATNUM);
dat_print(dat, DATNUM);
sort_select(dat, 0, DATNUM-1);
dat_print(dat, DATNUM);
}
/* ----- functions ----- */
// 選択ソートの本体
void sort_select(int dat[], int s, int e){
int maxi, w;
if( s == e ) return;
maxi = dat_max(dat, s, e);
// swap datmaxi<->dats
w = datmaxi;
datmaxi = dats;
dats = w;
sort_select(dat, s+1, e);
}
// s から e までの中で最大値を探す
int dat_max(int dat[], int s, int e){
int i, maxi;
maxi = s;
for(i=s; i<=e; i++){
if(dati > datmaxi){
maxi = i;
}
}
return maxi;
}
void dat_set(int dat[], int n){
int i;
for(i=0; i<n; i++){
dati = rand()%100; // データの個数にあわせて100を変更するとよい
}
}
void dat_print(int dat[], int n){
int i;
for(i=0; i<n; i++){
printf("%d ", dati);
}
printf("\n");
}
for文を使って書くと次のようになる。（普通はこちら）
code:sortselectloop.c
#include<stdio.h>
#include<stdlib.h>
#define DATNUM 10
/* ----- prototypes ----- */
void dat_print(int dat[], int n);
void dat_set(int dat[], int n);
int dat_max(int dat[], int s, int e);
void sort_select(int dat[], int s, int e);
/* ----- main ----- */
int main(void){
int datDATNUM;
dat_set(dat, DATNUM);
dat_print(dat, DATNUM);
sort_select(dat, 0, DATNUM-1);
dat_print(dat, DATNUM);
}
/* ----- functions ----- */
void sort_select(int dat[], int s, int e){
int maxi, w, i, j;
for(i=s; i<=e; i++){
maxi=i;
for(j=i; j<=e; j++){
if(datj > datmaxi){
maxi = j;
}
}
w = dati;
dati = datmaxi;
datmaxi = w;
}
}
void dat_set(int dat[], int n){
int i;
for(i=0; i<n; i++){
dati = rand()%100;
}
}
void dat_print(int dat[], int n){
int i;
for(i=0; i<n; i++){
printf("%d ", dati);
}
printf("\n");
}
クイズ
最大値のかわりに最小値を探すようにするとどうなるか
演習
1) ソートするデータ数を 10、100、1000、10000 などと変更し、計算時間を考察しよう。
プログラムの実行時間は $ time ./sortselectrecursive で計測できる。
整列
整列 バブルソート、選択ソートの演習　( ここ)
整列 文字列のソートの演習
整列 クイックソート、ヒープソートの演習
#Cプログラミングの演習