Глава 1
Пузырьковая сортировка - основана на методе перестановки.
Ее смысл заключается в постоянном сравнении смежных элементов
и при необходимости - их перестановке.
Для начала реализуем непараметризованную форму пузырьковой сортировки.
Ниже приведенная программа может использоваться для сортировки символьных
массисвов.
//Г.Шилдт стр 23 Программа.
//простейшая реализация пузырьковой сортироки для символов
#include
#include
void bubble(char *item,int count);
main()
{
char str[] = "dcab";
bubble(str, (int) strlen(str));
cout<<"Otsortirovannyi massiv - " << str << endl;
return 0;
}
//простая версия пузырьковой сортировки
void bubble(char *item, int count)
{
register int a,b;
char t;
for(a=1; a < count; ++a)
{
for(b=count-1; b >= a; --b)
{
//перестановка значений
t=item[b-1];
item[b-1] = item[b];
item[b] = t;
}
}
}
Анализ:
В функции bubble(),item представляет собой указатель на массив символов.
который должен подвергнуться сортировке.А параметр count представляет собой
количество элементов массива.
Метод пузырьковой сортировки управляется двумя вложенными циклами.
При условии, что массив содержит count элементов,внешний цикл вызывает сканирование массива count-1 раз.Это гарантирует что даже в наихудшем случае,после завершения функции каждый элемент будет находиться на
своем месте.Внутренний цикл фактически выполняет сравнения и перестановки.
Данная версия программы выполняет сравнение на каждом проходе через
внутренний цикл.Эту версию пузырьковой сортировки можно использовать
для сортировки массива символов в восходящем порядке.
Вот шаги программы:
1-я итерация Otsortirovannyi massiv - dcab
2-я итерация Otsortirovannyi massiv - bdca
3-я итерация Otsortirovannyi massiv - badc
4-я итерация Otsortirovannyi massiv - bacd
АВ:Как видим отсортировало не совсем правильно.
Анализируя алгоритм сортировки,вы должны определить сколько сравнений
и перестановок будет выполнено в лучшем,среднем и наихудшем случае.
Для алгоритма пузырьковой сортировки количество выполняемых сравнений
всегда одинаково,так как оба цикла for повторяются указанное количество раз
вне зависимости от того,отсортирован список или нет.
Это означает что если n- количество сортируемых элементов,то внешний цикл выполняется n-1 раз,а внутренний цикл -n/2 раза.
Перемножив эти значения получаем 1/2(n^2-n)
Преобразовать непараметризованную версию пузырьковой сортировки
в шаблон достаточно просто.Для этого необходимо параметризовать тип сортируемых данных.
Ниже приведена параметризованная версия пузырьковой сортировки:
//параметризованная версия пузырьковой сортироки для символов
#include
#include
template void bubble(Stype *item,int count);
main()
{
//сортировка массива символов
char str[] = "dcab";
bubble(str, (int) strlen(str));
cout<<"Otsortirovannyi massiv simvolov- " << str << endl;
//сортировка массивов целых чисел
int nums[] =
{
5,7,3,9,6,1,8};
int i;
bubble(nums,7);
cout<<" Otsortirovannyi massiv chisel : ";
for(i=0;i<7;i++) cout << nums[i] << " ";
return 0;
}
//параметризованная версия пузырьковой сортировки
template void bubble(Stype *item,int count)
{
register int a,b;
Stype t;
for(a=1;a
{
for(b=count-1;b>=a;--b)
{
//перестановка значений
t=item[b-1];
item[b-1] = item[b];
item[b] = t;
}
}
}
Otsortirovannyi massiv simvolov- bacd
Otsortirovannyi massiv chisel : 8 1 6 9 3 7 5
Анализ:
АВ:Вижу пока что отсортировались числа неправильно.
Как видите сейчас тип сортируемых данных указывается с помощью
параметризованного типа Stype. Кроме того в пределах функции
bubble() временная переменная t так же декларируется как принадлежащая
к типу Stype .
Назад |
Начало урока |
Вверх |
Вперед
Содержание