並べ替え（ソート）には、様々なアルゴリズムが考案されています。その代表的なもののうちの幾つかを以下に紹介します。
＜基本交換法（バブルソート）＞
基本交換法は，最大の要素が順次移動して配列の最後に押し出されてくる様子が，泡（バブル）が水面から出てくる様子に似ているのでバブルソートとも呼ばれ，最も有名なソート法です。
やっていることは「ある要素を次の要素と比較して，それより大きければ（小さければ）入れ替える」の繰り返しです。最終的には最も大きい（小さい）ものが最後に，最も小さい（大きい）ものが最初の要素にきます。ソートのアルゴリズムの中で最も理解しやすいもののひとつですが、反面ステップ数が多いために、要素数が多いときには実行速度が遅くなるという欠点があります。
どのような挙動になるかは、例えばこちらを参考にしてください。
以下の例は、dataの要素を昇順に並び替えるものです。
（例１）
#include <stdio.h>
#define N 8
int main(void) {
int
data[N] = {16, 41, 28, 33, 64, 2, 75, 59};
int
i, j, temp, exchange;
for
(i = 0; i < N-1; i++) {
exchange
= 0; /*
交換回数のカウンタexchangeを0で初期化 */
for
(j = 0; j < N-i-1; j++) { /*
N-1個目までの要素について... */
if
(data[j] > data[j+1]) { /
*次の要素より大きかったら、その要素と次の要素を入れ替える */
temp
= data[j];
data[j]
= data[j+1];
data[j+1]
= temp;
exchange++; /* 交換回数カウンタをインクリメント */
}
}
if
(exchange == 0) /*
一度も交換が行われなかったらソート終了 */
break;
}
for
(i = 0; i < N; i++)
printf("%d
", data[i]);
printf("\n");
return
0;
}
＜基本挿入法＞
基本挿入法は、まず始めに配列の０番目と１番間のデータを昇順に並べ、次に２番目のデータを０番目から２番目で昇順になる場所を探して挿入し、以下同様に３番目のデータを０番目から３番目で昇順になるように挿入し...という手順でソートしていきます。
下の例では、（例１）と同じデータを基本挿入法で昇順にソートしています。
（例２）
#include
<stdio.h>
#define N 8
int main(void)
{
int
data[N] = {16, 41, 28, 33, 64, 2, 75, 59};
int
i, j, temp;
for
(i = 1; i < N; i++) { /*
iを1からN-1までループ */
for
(j = i-1; j >= 0; j--) { /* jをi-1から0までループ */
/*
data[i]を、すでにソートされている範囲（data[0]~data[i-1]）のなかの適切な場所に挿入する */
if
(data[j] > data[j+1]) {
temp
= data[j];
data[j]
= data[j+1];
data[j+1]
= temp;
}
else
break;
}
}
for
(i = 0; i < N; i++)
printf("%d
", data[i]);
printf("\n");
return
0;
}
＜クイックソート＞
クイックソートは、基本交換法や基本挿入法にくらべてステップ数が少なくなるので、特にデータ量が多い場合に有効です。
クイックソートは、要素のある値（例えば中央位置の要素など）を軸にして、要素を振り分けることを繰り返してソートを行います。具体的には、軸の左側に軸より小さな要素を配置し、軸の右側には軸より大きな要素を配置します。それを区間を小さくしながら繰り返し、区間が一つになったら整列が完了していることになります。
クイックソートについては例えばこちらに図解があります。
下の例は、上の２つの例と同じデータをクイックソートでソートするものです。「関数の再帰呼び出し」（ある関数から自分自身の関数をコールする）というテクニックを使うことで、すっきりとしたプログラムになります。軸（pivot）には中央の要素を使ってます。
（例３）
#include
<stdio.h>
#define N 8
void qsort(int
*p, int left, int right);
int main(void)
{
int
data[N] = {16, 41, 28, 33, 64, 2, 75, 59};
int
i;
qsort(data,
0, N-1); /* クイックソートする関数qsortを呼び出し */
for
(i = 0; i < N; i++)
printf("%d
", data[i]);
printf("\n");
return
0;
}
/* クイックソート関数qsort */
/* pが指す配列のleftからrightまでの要素を昇順にソートする */
void qsort(int
*p, int left, int right) {
int
i, j, c, pivot, temp;
c
= (left+right)/2;
pivot
= *(p+c); /*
pivotの値としてleftとrightの中間の要素を使う */
i
= left; j = right;
while
(1) { /*
無限ループ */
while
(*(p+i) < pivot) /* pivotより左要素が小さい間ループして右に進む */
i++;
while
(pivot < *(p+j)) /* pivotより右要素が大きい間ループして左に進む */
j--;
if
(i >= j) /*
左右の添字が逆転したらループ終了 */
break;
temp
= *(p+i); /*
左右要素の入れ替え */
*(p+i)
= *(p+j);
*(p+j)
= temp;
i++;
j--;
}
if
(left < i-1) /*
まだ左側の要素があれば再帰呼び出し */
qsort(p,
left, i-1);
if
(j+1 < right) /*
まだ右側の要素があれば再帰呼び出し */
qsort(p,
j+1, right);
}