Виды сортировки
Работа добавлена на сайт samzan.net: 2015-07-05
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Сортировка. Виды сортировки. Пример алгоритма сортировки.
Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Основное требование к методам сортировки – экономное использование времени процессора и памяти. Существующие методы сортировки обычно разбивают на три класса в зависимости от лежащего в их основе приема: сортировка выбором, сортировка обменом, сортировка вставками.
- Пузырьковая сортировка:. Используется принцип пузырьковой сортировки, но массив просматривается не от начала до конца, а от начала до последнего перемещенного элемента (после которого все элементы уже упорядочены). Вначале этим «последним» элементом выбирается последний элемент массива.
- Простой выбор. Выбрать наибольший элемент массива и поменять его местами с последним (n–ным) элементом массива. Затем из n–1 первых элементов опять выбрать наибольший и опять поменять его местами с (n–1)–м. И так далее, пока весь массив не будет упорядочен.
- Простые вставки. Так обычно сортируют карты: из веера карт берут одну, стоящую не по старшинству и помещают между двумя уже упорядоченными картами. Массив просматривают с начала до конца. Рассматривается i–тый элемент массива и вставляется на нужную позицию в ряду первых (i–1) уже упорядоченных элементов. Если i–тый элемент перемещается в j–тую позицию, то все элементы с j–того по (i–1)–ый элемент должны быть сдвинуты на одну позицию вправо.
- Метод подсчета. Если для какого–то элемента массива известно, что если он больше, чем i других элементов этого массива, то он должен стоять на (i+1)–ом месте после упорядочивания. Для каждого i–го элемента массива считают, сколько чисел меньше его, и результат заносят в массив индексов с[i]. Это делается следующим образом. Сравнивают попарно все элементы массива: i–тый и j–тый. (Одна пара чисел может сравниваться только один раз.) Если i–тый больше, то с[i] увеличивают на единицу, иначе c[j] увеличивают на единицу. После формирования массива индексов с, формируют результирующий массив.
- Метод распределяющего подсчета. Используется, если в массиве много одинаковых элементов. Создается массив индексов d[i]. Размерность массива – число различных между собой элементов исходного массива. Затем в элемент массива d[i] заносят количество элементов массива, равных i, и в результирующий массив записывают по d[i] элементов i–того типа. Например, исходный массив 0010101031; d[0]=5, d[1]=4, d[2]=0, d[3]=1. Результирующий массив 0000011113.
Сортировка массива
Пример. Реализовать пузырьковую сортировку случайным образом генерируемого массива. Сравниваются i–тое и (i+1)–ое числа. Если i–тое число больше (сортировка по возрастанию), то они меняются местами. Массив просматривается до тех пор, пока от начала до конца массива не сделано ни одной перестановки соседних чисел.
void main ()
{
const int N=100;
int a[N],n;
printf("Enter n< %d",N);
scanf("%d",&n);
printf("\nArray:\n");
for (int i=0;i<n;i++) (//Генерируем массив случайных чисел в диапазоне [0..50] и выводим на экран)
{
a[i]=rand()%51;
printf("%d%s",a[i]," ");
}
printf("\nSotr:\n");
bool f; int b;
do
{
f=false;
for(int i=0;i<n-1;i++)(// Просматриваем весь массив)
if (a[i]>a[i+1])
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
f=true; (//Был обмен)
}
}
while (f); (// Проверяем, был ли хоть один обмен)
for (int i=0;i<n;i++) (// Выводим на экран отсортированный)
//массив
printf("%d%s",a[i]," ");
getch();
}