Лабораторная работа № 16. Алгоритмы сортировок подсчетом, пирамидальных, слиянием,

Поразрядных

 

Задание	Краткие теоретические сведения
1. Написать программу, реализующую алгоритм сортировки подсчетом с использованием функции, приведенной в правой части. Проанализировать алгоритм.	При использовании сортировки подсчетом упорядоченный массив получается из исходного путем сравнения всех пар элементов массива. Для каждого из элементов подсчитывается количество элементов, меньших его. Например, пусть есть массив B = < 20, -5, 10, 8, 7> .Для первого числа имеется 4 элемента, которые меньше первого. Для второго - 0 элементов и т.д. Формируется таким образом массив счетчиков S = < 4, 0, 3, 2, 1>, элементы которого дают местоположе-ния элементов в результирующем массиве B’ = < -5, 7, 8, 10, 20>. Для сортировки требуются дополнительные массивы для размещения результатов и для счетчиков.   void CountSort(int in[], int out[], int n) { int i, j, count; for (i = 0; i < n; ++i) { for ( count = 0, j = 0; j < n; ++j) if (in[j] < in[i] || (in[j] == in[i] & & i< j)) count++; out[count] = in[i]; } }
2. Написать программу, реализующую алгоритм пирамидальной сортировки с использованием функций, приведенных в правой части. Проанализировать алгоритм.	Пи­ра­ми­да - это дво­ич­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ниям до­чер­них эле­мен­тов. За­пол­нив де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке, мож­но его от­сор­ти­ро­вать, пре­вра­тив в пи­ра­ми­ду. Са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся в её вер­ши­не. От­де­ля­ется вер­шин­ный эле­мент и за­пи­сы­ва­ется в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва. На ме­сто вер­шин­но­го эле­мен­та помещается эле­мент из са­мо­го ниж­не­го уров­ня де­ре­ва. Вос­ста­нав­ли­вается (пе­ре­сор­ти­ро­вы­ва­ется) пи­ра­ми­да. Са­мый боль­шой эле­мент из остав­ших­ся элементов сно­ва в вер­ши­не и так да­лее... void heapify (int A[], int pos, int n) { int t, tm; while (2*pos + 1 < n) { t = 2 * pos + 1; if (2 * pos + 2 < n & & A[2 * pos + 2] > = A[t]) t = 2*pos + 2; if (A[pos] < A[t]) { tm = A[pos]; A[pos] = A[t]; A[t] = tm; pos = t; } else break; } } void PiramSort(int A[], int n) { for (int i = n - 1; i > = 0; i--) heapify(A, i, n); while(n> 0) { int tm = A[0]; A[0] = A[n - 1]; A[n - 1] = tm; n--; heapify(A, 0, n); } }
3. Написать программу, реализующую алгоритм сортировки слиянием с использованием функций, приведенных в правой части. Проанализировать алгоритм.	При использовании алгоритма сортировкислиянием исходный массив делится пополам, затем рекурсивно упорядочиваются обе половины и объединяются в одно целое. В ходе слияния элементы, стоящие в разных частях массива, попарно сравниваются друг с другом, и меньший элемент отправляется во временный массив. Этот процесс продолжается до тех пор, пока не будет использована полностью одна из двух частей массива. Затем копируются оставшиеся элементы во временный массив, и далее содержимое временного массива копируется обратно в исходный. void InsOrd(int m[], int sm, int em, int e) { int buf; int i = sm; while(i < = em & & m[i] < e) { if (i - 1 > = sm) m[i - 1] = m[i]; i++; } m[i - 1] = e; } int* Merge(int m[], int sm, int cm, int em) { for(int i = 0; i < = sm; i++) { if (m[i] > m[cm + 1]) { int buf = m[i]; m[i] = m[cm + 1]; InsOrd(m, cm + 1, em, buf); } } return m; } int* SortMerge(int m[], int lm, int sm = 0) { if (lm > 1) { SortMerge(m, lm / 2, sm); SortMerge(m, lm – lm / 2, sm + lm / 2); Merge(m, sm, sm + lm / 2 - 1, sm + lm - 1); }; return m; }; Здесь m[] - массив чисел; sm - индекс 1-ого элемента массива (1-й элемент левой части); cm - индекс последнего элемента левой части; em - индекс последнего элемента массива (последний элемент правой части); sm - стартовый элемент для сортировки.
4. Написать программу, реализующую алгоритм сортировки слиянием с использованием функций, приведенных в правой части. Проанализировать алгоритм.	Поразрядная сортировкаоснована на том, что все числа сортируются при помощи устойчивой сортировки сначала по младшему разряду, затем по остальным в порядке их возрастания. При этом ключи сортировки рассматриваются как числа, представленные в сист. счисления с основанием r. Работа идет с отд. цифрами чисел. int VelichRazr(int chislo, int razr) { while(razr> 1) { chislo /= 10; razr--; } return chislo % 10; } void PorazrSort(int B[n][n], int A[n], int razr) { int C[n], i, j, temp = 0; for(i = 0; i < n; i++) C[i] = 0; for(i = 0; i < n; i++) { int a = VelichRazr(A[i], razr); B[C[a]][a] = A[i]; C[a]++; } for(i = 0; i < n; i++) { for(j = 0; j < C[i]; j++) { A[temp] = B[j][i]; temp++; } } } Здесь A[n] -исходный массивположительных чисел, имеющих одинаковое количество разрядов, B[n][n] - вспомогательный двумерный массив чисел; razr - количество разрядов в числах.

5. В соответствии со своим вариантом написать программу сортировок массивов указанными в таблице методами. Исходные массивы заполняются случайными числами. Определить зависимость времени выполнения алгоритмов от количества элементов для каждого из алгоритмов. Выполнить моделирование для массивов размером 1000, 2000, 3000, 4000, 5000. Произвести сравнение эффективности алгоритмов (построить график в приложении Excel).

 

№ варианта	Методы сортировки массивов
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, пирамидальной, подсчетом, Шелла.
	Ввести массив А, в массив В перенести все элементы массива А, имеющие четный индекс, справа от которых расположены элементы с нечетным значением. Массив В отсортировать по убыванию, используя алгоритмы сортировок поразрядной, простой вставки, подсчетом.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее максимального элемента и имеющие нечетный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, выбором, пирамидальной, Хоара.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые больше минимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок подсчетом, пирамидальной, поразрядной, вставками.
	Ввести массивы Аи В. В массивС перенести элементы массива А с четным значением и элементы массива В с нечетным значением. Массив С отсортировать по возрастанию, используя алгоритмы сортировок разделением, слиянием, пирамидальной, Шелла.
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четное значение. Массив В отсортировать по возрастанию, используя алгоритмы сортировок методом простой вставки, подсчетом, выбором, слиянием.
	Ввести массивы Аи В. В массивС перенести четные элементы массива А и нечетные элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок поразрядной, слиянием, подсчетом, Хоара.
	Ввести массивы Аи В. В массивС перенести элементы массива А с нечетным значением и элементы массива В с нечетным значением. Массив С отсортировать по возрастанию, используя алгоритмы подсчетом, пирамидальной, поразрядной, вставками.
	Ввести массив А, в массив В перенести все элементы массива А, имеющие нечетный индекс, справа от которых расположены элементы с нечетным значением. Массив В отсортировать по возрастанию, используя алгоритмы сортировок слиянием, выбором, поразрядной, разделением.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые больше максимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок разделением, выбором, пирамидальной, пузырьком.
	Ввести массивы Аи В. В массивС перенести элементы массива А с нечетным значением и элементы массива В с четным значением. Массив С отсортировать по возрастанию, используя алгоритмы сортировок пирамидальной, разделением, слиянием, Хоара.
	Ввести массив А, в массив В скопировать все элементы массива А, имеющие четный индекс. Массив В отсортировать по возрастанию, используя алгоритмы сортировок подсчетом, выбором, пирамидальной, шейкерной.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее максимального элемента и имеющие четный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок слиянием, пирамидальной, подсчетом, Шелла.
	Ввести массивы Аи В. В массивС перенести нечетные элементы массива А и четные элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок поразрядной, пирамидальной, подсчетом, вставками.
	Ввести массивы Аи В. В массивС перенести те элементы массива А, которые меньше максимального элемента массива В. Массив С отсортировать по убыванию, используя алгоритмы сортировок слиянием, выбором, пирамидальной, Хоара.
	Ввести массив А, в массив В перенести все элементы массива А, стоящие правее минимального элемента и имеющие нечетный индекс. Массив В отсортировать по убыванию, используя алгоритмы сортировок поразрядной, подсчетом, слиянием, пузырьком.

 

 

В начало практикума

 

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

Поделиться:

Популярное:

1. II. Работа с раздаточным материалом
2. III. Работа по теме урока Представление журналов
3. IV. Работа над пройденным материалом.
4. MS Excel. Расчеты с условиями. Работа со списками
5. MS Word. Работа с математическими формулами
6. V. Работа над пройденным материалом.
7. VI. Рефлексия Работа по учебнику
8. XXIV. Охрана труда при работах в зоне влияния
9. XXXIV. Охрана труда при работах на электрофильтрах
10. А. Программирование работы гирлянды, работающей в режиме бегущей волны
11. Автоклавы для обеспечения безопасной работы снабжаются, также как и сосуды, работающие под давление, предохранительной и запорной арматурой, контрольно-измерительными приборами.
12. Алгоритмы k-means и k-medians