Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

⇐ ПредыдущаяСтр 2 из 2

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

· прост в реализации;

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

· эффективен на наборах данных, которые уже частично отсортированы;

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

· может сортировать массив по мере его получения;

· не требует временной памяти, даже под стек.

На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора.

//Описание функции сортировки методом простого включения

void InsertSort (int k,int x[max]) { int i,j, temp; for (i=0;i<k;i++) { //цикл проходов, i - номер прохода temp=x[i]; //поиск места элемента for (j=i-1; j>=0 && x[j]>temp; j--) x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли //место найдено, вставить элемент x[j+1]=temp; }}

В отличие от пузырьковой сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1 ; в противном случае его производительность является величиной порядка n².

Задания для выполнения

1. Отсортируйте по неубыванию методом "пузырька" одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100). Выведите на экран исходный и отсортированный массивы.

2. Отсортируйте по невозрастанию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

3. Отсортируйте по возрастанию методом простого включения одномерный целочисленный массив, заданный с клавиатуры различными числами. Выведите на экран исходный и отсортированный массивы.

4. Массив размером 2m + 1, где m – натуральное число, заполнен случайным образом. Найдите в массиве медиану. Медианой называется элемент ряда, делящий его на две равные части: в одной находятся элементы, которые не меньше медианы, в другой – не больше медианы.

5. Массив размером m, где m – натуральное число, заполнен случайным образом. Найдите в массиве моду. Модой называется элемент ряда, который встречается наиболее часто.

6. Дан массив 15 целых чисел на отрезке [-5;5]. Упорядочить массив, удалив повторяющиеся элементы.

7. Индивидуальное задание. Все массивы генерируются случайным образом.

№	Задание
1.	Сгенерировать массив из N элементов. Исключить из него все элементы, значения которых меньше K.
2.	Сгенерировать массив из N элементов. Определить количество элементов, значение которых больше, чем у соседних элементов массива.
3.	В массиве, состоящем из положительных и отрицательных чисел, определить, сколько элементов превосходят по модулю максимальный элемент.
4.	В одномерном массиве найти максимальный из отрицательных элементов и поменять его местами с последним элементом массива.
5.	В одномерном массиве найти минимальный из положительных элементов и поменять его местами с последним элементом массива.
6.	Сгенерировать массив из N элементов. Найти самую длинную последовательность чисел, упорядоченную по возрастанию. Вывести ее на экран. Если таких последовательностей несколько (самых длинных с одинаковой длиной), то вывести первую.
7.	Сгенерировать массив из N элементов. Определить количество элементов в заданном массиве, отличающихся от минимального на 5.
8.	Сгенерировать массив из N элементов. В массиве найти (посчитать) количество положительных, отрицательных и нулевых элементов.
9.	Сгенерировать массив из N элементов. В массиве удалить все четные элементы и оставить только нечетные.
10.	Сгенерировать массив из N элементов. Найти самую длинную последовательность из нулей и выводит на экран ее длину и номер ее начала в массиве.
11.	Сгенерировать массив из N элементов. Добавить элемент L в к-ое место массива.
12.	Даны два массива с различным количеством элементов. Перераспределить их элементы так, чтобы в первом массиве были наименьшие из двух массивов, а во втором - наибольшие.
13.	Сгенерировать массив из N элементов. В массиве чисел найти два максимальных элемента.
14.	Сгенерировать массив из N элементов. Вывести суммы элементов массива – с первого до элемента с номером К и от элемента с номером К+1 до последнего.
15.	Сгенерировать массив из N элементов. Получить среднее арифметическое всех чётных элементов массива, стоящих на нечётных местах.
16.	Сгенерировать массив из N элементов. Найдите сумму и количество элементов массива, попавших в интервал [a; b]. Границы интервала вводятся с клавиатуры.
17.	Из одномерного массива удалить все повторяющиеся элементы (дубликаты) так, чтобы каждое значение встречалось в массиве только один раз.
18.	Сгенерировать два массива. Требуется получить третий упорядоченный по возрастанию массив, путем слияния первых двух.
19.	Сгенерировать два массива. Требуется получить третий упорядоченный по убыванию массив, путем слияния первых двух.
20.	Сгенерировать массив из N элементов. В массиве чисел найти два минимальных элемента.
21.	Сгенерировать массив из N элементов. В массиве удалить все нечетные элементы и оставить только четные.
22.	Сгенерировать массив из N элементов. Определить количество элементов в заданном массиве, отличающихся от максимального на 7.
23.	Сгенерировать массив из N элементов. Проверить, есть ли в нем одинаковые элементы.
24.	Сгенерировать массив из N элементов. Найти самую длинную последовательность чисел, упорядоченную по убыванию. Вывести ее на экран. Если таких последовательностей несколько (самых длинных с одинаковой длиной), то вывести первую.
25.	Сгенерировать массив из N элементов. Исключить из него все элементы, значения которых больше K.
26.	Сгенерировать массив из N элементов. Исключить из него все элементы, значения которых равные K.
27.	Сгенерировать массив из N элементов. Определить количество элементов, значение которых меньше, чем у соседних элементов массива.
28.	В массиве, состоящем из положительных и отрицательных чисел, определить, сколько элементов превосходят по модулю максимальный элемент.
29.	В одномерном массиве найти максимальный из отрицательных элементов и поменять его местами с последним элементом массива.
30.	В одномерном массиве найти минимальный из положительных элементов и поменять его местами с последним элементом массива.

Дата добавления: 2021-07-19; просмотров: 137; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!