Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка вставками. Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании
|
|
Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.
Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:
1. первая и вторая карта меньше третьей;
2. первая и вторая карта больше третьей;
3. первая карта уступает значением третьей, а вторая превосходит ее;
4. первая карта превосходит значением третью карту, а вторая уступает ей.
В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В предпоследнем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.
Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.
Ниже на анимированном изображении показан еще один пример работы алгоритма сортировки вставками. Здесь, как и в предыдущем примере, последовательность сортируется по возрастанию.
Таким образом, получается, что на каждом этапе выполнения алгоритма сортируется некоторая часть массива, размер которой с шагом увеличивается, и в конце сортируется весь массив целиком.
Код программы на C++:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include " stdafx.h" #include < iostream> using namespace std; int i, j, key=0, temp=0; void InsertSort(int *mas, int n) //сортировка вставками { for (i=0; i< n-1; i++) { key=i+1; temp=mas[key]; for (j=i+1; j> 0; j--) { if (temp< mas[j-1]) { mas[j]=mas[j-1]; key=j-1; } } mas[key]=temp; } cout< < endl< < " Результирующий массив: "; for (i=0; i< n; i++) //вывод массива cout< < mas[i]< < " "; } //главная функция void main () { setlocale(LC_ALL, " Rus"); int n; cout< < " Количество элементов в массиве > "; cin> > n; int *mas=new int[n]; for (i=0; i< n; i++) //ввод массива { cout< < i+1< < " элемент > "; cin> > mas[i]; } InsertSort(mas, n); //вызов функции delete[] mas; system(" pause> > void"); } |
Обе программы сортируют массив по возрастанию. В их основной части выполняются три операции: определение количества элементов в массиве, ввод этих элементов и вызов подпрограммы. Подпрограмма состоит из алгоритма сортировки и цикла, выводящего результирующую упорядоченную последовательность. Алгоритм включает в себя классическую для многих алгоритмов сортировки структуру вложенных циклов. Количество итераций внешнего цикла не превышает n-1, где n – число элементов в массиве; внутренний цикл, начиная с шага i+1, заканчивает свое выполнение при j=0 (значение переменной-счетчика j уменьшается с каждым шагом на 1). Переменным key и temp на i-ом шаге присваиваются значения, зависящие от шага и значения элемента массива mas на этом шаге. В переменной temp храниться значение элемента массива mas[i+1], оно во внутреннем цикле сравнивается со значениями других элементов. Key запоминает индекс элемента, который последним был больше temp, и ему, по завершению работы внутреннего цикла, присваивается значение переменной temp.