Пузырьковая сортировка (сортировка обменом)

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. Отсортировать элементы нечетных столбцов вещественной матрицы по не убыванию, а элементы четных столбцов по не возрастанию: А) сортировкой вставками; В) сортировкой обменом.