Порівняння прямих методів сортування.

Наведені формули оцінки прямих методів сортування отримані Н.Віртом. Оскільки той самий метод можна реалізувати різноманітними алгоритмами, то загальний вигляд формул надає загальні тенденції в оцінці методів.

	Кількість порівнянь	(с) і пересувань	(р)
Метод сортування	Мінімальне (найкраща оцінка)	Середнє	Масимальне (найгірша оцінка)
Пряма вставка	С=n-1 R=2(n-1)	С=(n² +n-2)/4 R=(n²-9n-10)/4	С=(n²-n-2)/4 R=(n²-3n-4)/4
Прямий вибір	C=(n²-n)/2 R=3(n-1)	C=(n²-n)/2 R=n(ln(n)+0.57)	C=(n²-n)/2 R=n²/4+3(n-1)
Прямий обмін	C=(n²-n)/2 R=0	C=(n²-n)/2 R=3(n²-n)	C=(n²-n)/2 R=3(n²-n)/2

Висновок:

а) якщо відомо, що масив практично впорядкований, переваги можуть мати методи обміну;

б) метод прямого вибору єдиний, що по усередненій оцінці дає квадратичну залежність кількості обмінів від розмірності масиву. Тому його бажано використовувати у задачах, в яких пересувань більше ніж порівнянь.

Завдання

1. Надано матрицю n*m. Відсортувати останній рядок по

а)зростанню;

б)спаданню;

в)неспаданню.

2. Надано матрицю, відсортувати всі ії рядки

а) по зростанню;

б) по неспаданню.

3. Відсортувати головну діагональ матриці методом сортування "з бар'єром".

4. Відсортувати побічну діагональ:

а) пошуком справа "без бар'єру" (початок - правий верхній кут);

б) пошуком "з бар'єром" (початок - лівий нижній кут).

5. Упорядкувати по незростанню методом вибору всі елементи матриці m*n, обходячи її по рядках та вважаючи, що кожний наступний рядок є продовженням попереднього.

1 1 n

6. Надано послідоиність дійсних чисел довжиною n. Впорядкувати по незростанню методом шейкерного сортування елементи, що стоять на непарних позиціях (використати умовні цикли).

7. Надано послідовність цілих чисел довжиною n. Впорядкувати по неспаданню, методом обміну, із запам'ятовуванням місця останнього пересування, додатні елементи, не торкаючись від'ємних та нульових.

8. Те ж, що і у 7, але методом обрання.

9. Надано матрицю m*n. Упорядкувати по неспаданню методом обміну із флагом елементи матриці, обходячи її змійкою.

10. Упорядкувати по неспаданню побічну діагональ матриці методом шейкерного сортування.

11. Пересунути рядки матриці по незростанню сум елементів рядків методом вибору.

12. Пересунути стовбці матриці по неспаданню сум елементів методом обміну.

13. Упорядкувати по неспаданню методом вставки елементи кожного рядка, що стоять між максимальним та мінімальним елементами цього ж рядка.

14. Надано послідовність чисел довжиною n. Впорядкувати елементи, що перевищують надане число p, по незростанню методом вибору.

Питання для самоконтролю

1. На які группи розподіляються методи сортування(на підставі реалізованих принципів)?

2. У чому полягають принципи основних прямих методів сортування?

3. Які різновиди прямих методів сортування ви можете навести? Яка різниця між базовим методом та навединими вами варіантами?

4. Яка ідея реалізована у базовому методі прямого вибору?

5. В чому полягає ідея базового методу обміну?

6. Які ви можете навести варіанти методу обміну та в чому полягають покращення?

7. Поясніть базовий метод вставки та можливі модифікації.