Глава 1 (продолжение )
Усовершенствованные методы сортировки.
Сортировка методом Шелла.
//параметризованная версия сортироки алгоритмом Шелла
#include <iostream.h>
#include <string.h>
template <class Stype> void shell(Stype *item,int count);
main()
{
//сортировка массива символов
char str[] = "dcab";
shell(str, (int) strlen(str));
cout<<"Otsortirovannyi massiv simvolov- " << str << endl;
char enterchar;
cout<<endl<<endl<<"Type any character to finish:";
cin>>enterchar;
//сортировка массивов целых чисел
int nums[] = {
5,7,3,9,5,1,8};
int i;
shell(nums,7);
cout<<" Otsortirovannyi massiv chisel : ";
for(i=0;i<7;i++) cout <<nums[i] <<" ";
//char enterchar;
cout<<endl<<endl<<"Type any character to finish:";
cin>>enterchar;
return 0;
}
//параметризованная функция сортировки методом Шелла
template <class Stype> void shell(Stype *item,int count)
{
register int i,j,gap,k;
Stype x;
char a[5];
a[0]=9;a[1]=5;a[2]=3;a[3]=2;a[4]=1;
for(k=0;k<5;k++)
{
gap = a[k];
for(i=gap;i<count;++i)
{
x=item[i];
for(j=i-gap;x<item[j] && j>=0; j=j-gap)
item[j+gap] = item[j];
item[j+gap] = x;
}
}
}
Результат:
Otsortirovannyi massiv simvolov- abcd
Otsortirovannyi massiv chisel : 1 3 5 5 7 8 9
Функция сортировки работает правильно!
Внутренний цикл for имеет два условия проверки.
Очевидно что сравнение x<item[j] необходимо по условиям процесса
сортировки.Условие j>=0; предотвращает выход за пределы массива item.
Эти дополнительные проверки в некоторой степени снизят производительность
алгоритма Шелла.Улучшенные версии алгоритма используют специальные
элементы массива,называемые стражами (sentinels),Стражи не являются
частью сортируемого массива.Они содержат завершающие элементы,обозначающие
наибольший и наименьший возможные элементы массива.Это делает ненужной
проверку границ массива,но требует конкретной информации о данных,
что ограничивает общность функции сортировки.
Назад |
Начало урока |
Вверх |
Вперед
Содержание