Пузырьковая сортировка (сортировка обменом)
for(int a = 1; a < count; ++a)
for(int b = count-1; b >= a; --b) {
if(items[b-1] > items[b]) {
t = items[b-1];
items[b-1] = items[b];
items[b] = t;
}
}
Сортировка выбором
for(a = 0; a < count-1; ++a) {
exchange = 0;
c = a;
t = items[a];
for(b = a+1; b < count; ++b) {
if(items[b] < t) {
c = b;
t = items[b];
exchange = 1;
}
}
if(exchange) {
items[c] = items[a];
items[a] = t;
}
}
Сортировка вставками
for(a=1; a < count; ++a) {
t = items[a];
for(b=a-1; (b >= 0) && (t < items[b]); b--)
items[b+1] = items[b];
items[b+1] = t;
}
Задание 1.
1. На примере исходных данных объяснить различия указанных в вашем задании алгоритмов сортировки (в письменной форме).
2. Программа должна запрашивать из файла двумерный массив. Результат сортировки по желанию пользователя может сохраняться в файле. Имена файлов вводятся с клавиатуры.
3. Используемые массивы должны быть динамическими.
4. Каждый логически законченный фрагмент должен быть оформлен в виде отдельной функции (в том числе выделение и освобождение памяти).
5. Все необходимые данные для функции должны передаваться в качестве параметров (глобальные переменные запрещены).
6. Разработать модуль (отдельный cpp-файл, имена заголовочного и соответствующего cpp-файла должны различаться только расширением), включающий в себя:
- реализацию указанных алгоритмов сортировки;
- профайлер, позволяющий подсчитать количество «пересылок» и сравнений, произведенных во время сортировки.
7. Составить тесты (не менее 10 файлов) для отладки работы алгоритмов.
8. Составить сравнительную таблицу, позволяющую оценить эффективность работы каждого из алгоритмов на
- упорядоченной,
- случайной,
- упорядоченной в обратном порядке
последовательности чисел. Исходная последовательность получается путем считывания подряд строк (столбцов) упорядоченного двумерного массива (она будет считаться случайной последовательностью; после её упорядочения одним из методов получаем упорядоченную в прямом порядке, инвертировав её – в обратном порядке).
1.1.Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждой строки: А) сортировкой выбором; В) сортировкой обменом.
1.2. Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждого столбца: А) сортировкой выбором; В) сортировкой обменом
1.3. Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждой строки: А) сортировкой вставками; В) сортировкой обменом
1.4. Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждого столбца: А) сортировкой вставками; В) сортировкой обменом
1.5. Дана матрица, элементами которой являются латинские буквы.Отсортировать в обратном лексикографическом порядке элементы каждой строки: А) сортировкой выбором; В) сортировкой вставками.
1.6. Дана матрица, элементами которой являются латинские буквы.Отсортировать в обратном лексикографическом порядке элементы каждого столбца: А) сортировкой выбором; В) сортировкой вставками.
1.7. Дана матрица, элементами которой являются латинские буквы.Отсортировать в обратном лексикографическом порядке элементы каждой строки: А) сортировкой выбором; В) сортировкой обменом
1.8. Дана матрица, элементами которой являются латинские буквы.Отсортировать в обратном лексикографическом порядке элементы каждого столбца: А) сортировкой выбором; В) сортировкой обменом.
1.9. Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждой строки: А) сортировкой вставками; В) сортировкой обменом.
1.10. Дана матрица, элементами которой являются латинские буквы.Отсортировать в лексикографическом порядке элементы каждого столбца: А) сортировкой вставками; В) сортировкой обменом.
1.11. Отсортировать элементы диагоналей вещественной матрицы, параллельных главной диагонали, по не возрастанию:
А) сортировкой вставками; В) сортировкой обменом.
1.12.Отсортировать элементы диагоналей вещественной матрицы, параллельных побочной диагонали, по не убыванию:
А) сортировкой вставками; В) сортировкой обменом.
1.13. Отсортировать элементы строк вещественной матрицы по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.
1.14. Отсортировать элементы столбцов вещественной матрицы по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.
1.15. Отсортировать элементы строк вещественной матрицы по не возрастанию: А) сортировкой выбором; В) сортировкой обменом.
1.16. Отсортировать элементы столбцов вещественной матрицы по не возрастанию: А) сортировкой выбором; В) сортировкой обменом.
1.17. Отсортировать элементы строк вещественной матрицы по не убыванию: А) сортировкой выбором; В) сортировкой обменом.
1.18. Отсортировать элементы столбцов вещественной матрицы по не убыванию: А) сортировкой выбором; В) сортировкой обменом.
1.19. Отсортировать элементы строк вещественной матрицы по не убыванию: А) сортировкой выбором; В) сортировкой вставками.
1.20. Отсортировать элементы столбцов вещественной матрицы по не убыванию: А) сортировкой выбором; В) сортировкой вставками.
1.21. Отсортировать элементы диагоналей вещественной матрицы, параллельных главной диагонали, по не возрастанию:
А) сортировкой выбором; В) сортировкой вставками.
1.22. Отсортировать элементы нечетных строк вещественной матрицы по не убыванию, а элементы четных строк по не возрастанию: А) сортировкой выбором; В) сортировкой вставками.
1.23. Отсортировать элементы нечетных строк вещественной матрицы по не убыванию, а элементы четных строк по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.
1.24. Отсортировать элементы нечетных столбцов вещественной матрицы по не убыванию, а элементы четных столбцов по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.
1.25. Отсортировать элементы нечетных столбцов вещественной матрицы по не убыванию, а элементы четных столбцов по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.