 |
|
Сортировка вставками.
Сортировка простыми вставками в чем-то похожа на методы изложенные в предыдущих разделах урока. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.
Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда найден элемент, меньший x или достигнуто начало последовательности.
Реализация метода
| #include <iostream>#include <stdlib.h>#include <time.h> using namespace std; template <typename T>void insertSort(T a[], long size) { T x; long i, j; for(i=0;i<size;i++){ // цикл проходов, i - номер прохода x=a[i]; // поиск места элемента в готовой последовательности for (j=i-1;j>=0&&a[j]>x;j--) a[j+1]=a[j]; // сдвигаем элемент направо, пока не дошли // место найдено, вставить элемент a[j+1] = x; }} void main(){ srand(time(NULL)); const long SIZE=10; int ar[SIZE]; // до сортировки for(int i=0;i<SIZE;i++){ ar[i]=rand()%100; cout<<ar[i]<<"\t"; } cout<<"\n\n"; insertSort(ar,SIZE); // после сортировки for(int i=0;i<SIZE;i++){ cout<<ar[i]<<"\t"; } cout<<"\n\n";} |
Принципы метода
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Однако, алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный "сторожевой элемент". Он должен быть заведомо меньше всех остальных элементов массива.
Тогда при j=0 будет заведомо верно a[0] <=x. Цикл остановится на нулевом элементе, что и было целью условия j>=0. Таким образом, сортировка будет происходить правильным образом, а во внутреннем цикле станет на одно сравнение меньше. Однако, отсортированный массив будет не полон, так как из него исчезло первое число. Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]...a[n].
| #include <iostream>#include <stdlib.h>#include <time.h> using namespace std; template <typename T>void setMin(T a[],long size){ T min=a[0]; for(int i=1;i<size;i++) if(a[i]<min) min=a[i]; a[0]=min; } template <class T>void insertSortGuarded(T a[], long size) { T x; long i, j; T backup = a[0]; // сохранить старый первый элемент setMin(a,size); // заменить на минимальный // отсортировать массив for(i=1;i<size;i++){ x = a[i]; for (j=i-1;a[j]>x;j--) a[j+1]=a[j]; a[j+1] = x; } // вставить backup на правильное место for(j=1;j<size&&a[j]<backup;j++) a[j-1]=a[j]; // вставка элемента a[j-1] = backup;} void main(){ srand(time(NULL)); const long SIZE=10; int ar[SIZE]; // до сортировки for(int i=0;i<SIZE;i++){ ar[i]=rand()%100; cout<<ar[i]<<"\t"; } cout<<"\n\n"; insertSortGuarded(ar,SIZE); // после сортировки for(int i=0;i<SIZE;i++){ cout<<ar[i]<<"\t"; } cout<<"\n\n";} |
| Предыдущая | Оглавление | Следующая | |||
| Предыдущая | Оглавление | Следующая | |||
Домашнее задание
1. Дан массив чисел размерностью 10 элементов. Написать функцию, которая сортирует массив по возрастанию или по убыванию, в зависимости от третьего параметра функции. Если он равен 1, сортировка идет по убыванию, если 0, то по возрастанию. Первые 2 параметра функции - это массив и его размер, третий параметр по умолчанию равен 1.
2. Дан массив случайных чисел в диапазоне от -20 до +20. Необходимо найти позиции крайних отрицательных элементов (самого левого отрицательного элемента и самого правого отрицательного элемента) и отсортировать элементы, находящиеся между ними.
3. Дан массив из 20 целых чисел со значениями от 1 до 20.
Необходимо:
- написать функцию, разбрасывающую элементы массива произвольным образом;
- создать случайное число из того же диапазона и найти позицию этого случайного числа в массиве;
- отсортировать элементы массива, находящиеся слева от найденной позиции по убыванию, а элементы массива, находящиеся справа от найденной позиции по возрастанию.
| Предыдущая | Оглавление | Следующая |
| Предыдущая | Оглавление | Следующая |
Урок №11.
- Знакомство с рекурсией.
- Рекурсии или итерации?
- Быстрая сортировка.
- Двоичный поиск.
- Домашнее задание
| Предыдущая | Оглавление | Следующая | |||
| Предыдущая | Оглавление | Следующая | |||