Учебное пособие предназначено для подготовки к выполнению лабораторных работ по дисциплине «Технологии и методы программирования»

Метод «пузырька». Данный метод относится к сортировкам обменом. Метод «пузырька» получил своё название оттого, что продвижение максимальных элементов массива к его вершине происходит постепенно, подобно всплытию пузырька на поверхность воды. Этот метод требует нескольких проходов массива. На каждом проходе сравнивается пара соседних друг с другом элементов.
Если пара расположена в порядке возрастания, переставляем эти элементы местами. В противном случае элементы остаются на исходных позициях. Процедура должна быть повторена n-1 раз для гарантированного достижения результата. Пример поэтапной работы алгоритма показан на рис.3. Изображенные на каждом проходе перестановки должны выполняться последовательно слева направо.

проход 1	0	5	3	7	9
проход 2	5	3	7	9	0
проход 3	5	7	9	3	0
проход 4	7	9	5	3	0
итог	9	7	5	3	0

Рис.3 Алгоритм сортировки «пузырьком»

Листинг программы primer 3_11.c демонстрирует реализацию этого метода.

//primer 3_11.c
#include
#include
int main ()
{
int i,j, temp=0;
const int n=5;
int a[n]={0,5,3,7,9};
for (i=0; i{
for (j=0; jif (a[j]{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
printf ("\n");
for (i=0; iprintf ("%d ", a[i]);
getch ();
return 0;
}


Сортировка выбором. Алгоритм состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом, и так далее n-1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива). Последовательность шагов при n=5 изображена на рис 4. ниже.

Рис.4 Алгоритм сортировки выбором

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
Листинг программы primer 3_12.c демонстрирует реализацию этого метода:
//primer 3_12.c
#include
#include
int main ()
{
const int n=7;
int a[n]={1,3,4,5,6,7,1};
int i, j, index, temp;
for (i=0; i{
index=i;
for (j=i+1; jif (a[j]index=j;
temp=a[i];
a[i]=a[index];
a[index]=temp;}
}
for (i=0; iprintf("\n%d ",a[i]);
getch();
return (0);
}