Метод пузырьков в информатике
Содержание:
Таблица 1: Сортировка пузырьком в однопоточном режиме
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 1 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 1 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 1 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 | 11 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 1 | 12 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 1 | 13 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 1 | 14 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| 3 | 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 2 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 2 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 2 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 2 | 9 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 2 | 10 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 2 | 11 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 2 | 12 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 2 | 13 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 2 | 14 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | ||
| 4 | 3 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 3 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 3 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 3 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 3 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 3 | 10 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 3 | 11 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 3 | 12 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 3 | 13 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 3 | 14 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 1 | ||
| 5 | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 4 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 4 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 4 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 4 | 11 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 4 | 12 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 4 | 13 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 4 | 14 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 2 | 1 | ||
| 6 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 5 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 5 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 5 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 5 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 11 | 5 | 12 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 5 | 13 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 5 | 14 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 3 | 2 | 1 | ||
| 7 | 6 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 6 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 6 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 6 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 11 | 6 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 11 | 12 | 6 | 13 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 6 | 14 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 4 | 3 | 2 | 1 | ||
| 8 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 7 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 7 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 11 | 7 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 11 | 12 | 7 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 11 | 12 | 13 | 7 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 5 | 4 | 3 | 2 | 1 | ||
| 9 | 8 | 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 8 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 11 | 8 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 11 | 12 | 8 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 11 | 12 | 13 | 8 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 9 | 10 | 11 | 12 | 13 | 14 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 10 | 9 | 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 9 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 12 | 9 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 12 | 13 | 9 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 12 | 13 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 11 | 10 | 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 10 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 13 | 10 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 13 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 12 | 11 | 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 13 | 11 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 13 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 13 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 13 | 12 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 14 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
1.2 Выбор программного обеспечения по реализации ИТ
При написании программ для реализации сортировок массивов был использован язык программирования С++. Это один из широко используемых языков программирования, который можно использовать для написания программ, работающих в операционной среде Windows. Среда Borland C++ Builder 6- это сложный механизм, обеспечивающий высокоэффективную работу программиста
Интегрированная среда разработки C++ Builder представляет собой многооконную систему. Вид интегрированной среды разработки (интерфейс) может различаться в зависимости от настроек. Кроме стандартных окон, на экране могут присутствовать и другие окна, отображаемые при вызове соответствующих средств, например, Image Editor (Редактор изображений). Окна C++ Builder (но не главное) можно перемещать, убирать с экрана, а также изменять их размеры.
Несмотря на наличие многих окон, C++ Builder является одно-документной средой, т.е. позволяет одновременно работать только с одним приложением (проектом приложения). Название проекта приложения выводится в строке заголовка главного окна в верхней части экрана.
Если свернуть главное окно, то происходит минимизация всего интерфейса C++ Builder и, соответственно, всех открытых окон. При закрытии главного окна работа с C++ Builder прекращается.
Borland C++ Builder 6, вобрав в себя всё самое лучшее от предыдущих версий, предоставляет ряд новых возможностей. Так, например, стал более удобным и современным интерфейс среды программирования, создаваемые C++ Builder программы учитывают архитектуру современных процессоров, существенно расширены возможности отладчика.
Borland C++ Builder 6 может работать в среде операционных систем от Windows 95 до Windows XP. Особенных требований к компьютеру система не предъявляет, за исключением того, что процессор должен быть типа Pentium, оперативной памяти — не менее 32 Мбайт и достаточное количество свободной дисковой памяти.
Сортировка пузырьком
Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
3 нарушает порядок, меняем местами с 7
Возвращаемся к началу массива и проделываем то же самое
void bubbleSort(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j < size; j++) {
if (a > a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
После того, как были поменяны местами элемента a и a нет больше необходимости проходить этот участок массива
Примем это во внимание и переделаем алгоритм
void bubbleSort2(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = i; j > 0; j--) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Ещё одна реализация
void bubbleSort2b(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j <= size-i; j++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
void bubbleSort3(int *a, size_t size) {
size_t i;
int tmp;
char flag;
do {
flag = 0;
for (i = 1; i < size; i++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
int intSort(const void *a, const void *b) {
return *((int*)a) > *((int*)b);
}
void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
char flag;
tmp = malloc(item);
do {
flag = 0;
for (i = 1; i < size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
void *prev, *cur;
char flag;
tmp = malloc(item);
do {
flag = 0;
i = 1;
prev = (char*)a;
cur = (char*)prev + item;
while (i < size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Теперь с помощью этих функций можно сортировать массивы любого типа, например
void main() {
int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5};
int i;
bubbleSort3gi(a, sizeof(int), 10, intSort);
for (i = 0; i < 10; i++) {
printf("%d ", a);
}
_getch();
}
2.8 Теоретическое сравнение сортировок методом простых вставок и методом пузырька
Выполним по рекомендованной литературе теоретическое сравнение алгоритмов сортировок, рассматриваемых в данном курсовом проекте. Основным критерием сравнения сортировок является их эффективность, то есть число сравнений и число пересылок. Данные показатели также влияют на время сортировки. Укажем основные формулы, использующиеся для вычисления эффективности данных сортировок:
− число сравнений ключей элементов при i-ом просеивании;
−минимальное число сравнений ключей;
− максимальное число сравнений ключей;
− среднее число сравнений ключей;
− число пересылок (присваиваний) элементов при i-ом просеивании;
− минимальное число пересылок
− максимальное число пересылок
− среднее число пересылок
− размер массива;
Рассмотрим сортировку методом простых вставок
Рассмотрим сортировку методом пузырька
На основе данных методических формул составим сравнительную таблицу для сортировок методом простых вставок и методом пузырька:
Таблица 2. Сравнительный анализ сортировок методом простых вставок и методом пузырька
|
Размер массива |
Метод простых вставок |
Метод пузырька |
||
|
Число сравнений ключей (среднее значение) |
Число пересылок (среднее значение) |
Число сравнений ключей (среднее значение) |
Число пересылок (среднее значение) |
|
|
32 |
263 |
329 |
256 |
384 |
|
64 |
1039 |
1163 |
1024 |
1536 |
|
128 |
4127 |
4379 |
4096 |
6144 |
|
256 |
16447 |
16953 |
16384 |
24576 |
|
512 |
65663 |
131835 |
65536 |
98304 |
|
1024 |
262399 |
264443 |
262144 |
393216 |
На основе полученных в таблице 2 значений составим сравнительные графики, для числа сравнений ключей и для числа пересылок по обоим методам сортировки:
Рисунок 10. Графики числа сравнений ключей: число сравнений ключей П — для метода пузырька, число сравнений ключей В — для метода простых вставок.
На основе полученных графиков можно сказать, что число сравнений ключей в сортировке методом пузырька число сравнений больше, чем в сортировке методом вставок. Следовательно по данному критерию эффективность сортировки методом простых вставок выше, чем методом пузырька.
Рисунок 11. Графики числа пересылок в сортировках: число пересылок П — для метода пузырька, число пересылок В — для метода простых вставок.
Основываясь на полученных графиках можно сказать, что при малых значениях размерности массива число пересылок для обоих методов примерно одинаково. При относительно больших размерах массива (от 512 и более) число пересылок в методе
пузырька возрастает быстрее, чем в методе простых вставок. Следовательно, эффективность метода вставок выше по данной характеристике.
Ссылаясь на таблицу 1 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.
Из чего следует, что в целом сортировка методом простых вставок эффективнее сортировки методом пузырька.
Реализация
Реализация псевдокода
В псевдокоде алгоритм может быть выражен как (массив на основе 0):
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if this pair is out of order */
if Ai-1 > Ai then
/* swap them and remember something changed */
swap(Ai-1, Ai])
swapped := true
end if
end for
until not swapped
end procedure
Оптимизация пузырьковой сортировки
Алгоритм пузырьковой сортировки можно оптимизировать, наблюдая, что n -й проход находит n-й по величине элемент и помещает его на свое последнее место. Таким образом, внутренний цикл может избежать просмотра последних n — 1 элементов при запуске в n -й раз:
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n - 1 inclusive do
if Ai - 1 > Ai then
swap(Ai - 1, Ai])
swapped = true
end if
end for
n := n - 1
until not swapped
end procedure
В более общем смысле может случиться так, что более чем один элемент помещается в свое окончательное положение за один проход. В частности, после каждого прохода все элементы после последнего свопа сортируются и не нуждаются в повторной проверке. Это позволяет пропускать многие элементы, что в худшем случае приводит к увеличению количества сравнений примерно на 50% (хотя и без улучшения подсчета подкачки), и добавляет очень небольшую сложность, поскольку новый код включает переменную «подкачки»:
Для этого в псевдокоде можно записать следующее:
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
newn :=
for i := 1 to n - 1 inclusive do
if Ai - 1 > Ai then
swap(Ai - 1, Ai])
newn := i
end if
end for
n := newn
until n ≥ 1
end procedure
Альтернативные модификации, такие как сортировка с помощью шейкер для коктейлей, пытаются улучшить производительность пузырьковой сортировки, сохраняя при этом ту же идею многократного сравнения и замены соседних элементов.
Алгоритмы сортировки на собеседовании
Алгоритмов сортировки достаточно много, и вряд ли можно встретить программиста, который может по памяти написать реализацию хотя бы половины из них.
На самом деле, программисты просто гуглят необходимую реализацию. Конечно, они имеют представление о принципах их работы, потому что в своё время рассмотрели несколько алгоритмов, как, например, сортировка пузырьком.
Кроме того, в Python и других языках программирования существуют встроенные функции, которые производят сортировку быстро и эффективно.
На собеседованиях спрашивают про алгоритмы сортировки, но это не значит, что от будущего работника требуют написать их реализацию или придумать свой. Работодатель требует от специалиста следующее:
- Уметь классифицировать алгоритмы сортировки.
- Знать преимущества и недостатки популярных алгоритмов, чтобы понимать, когда каждый из них лучше использовать.
- Понимать, что такое сложность алгоритма и как с её помощью определять, подходит ли он для решения данной задачи.
Таблица 2: Сортировка пузырьком в многопоточном режиме
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 1 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 2 | 4 | 1 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 4 | 2 | 5 | 1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 3 | 5 | 2 | 6 | 1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 5 | 3 | 6 | 2 | 7 | 1 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 4 | 6 | 3 | 7 | 2 | 8 | 1 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 6 | 4 | 7 | 3 | 8 | 2 | 9 | 1 | 10 | 11 | 12 | 13 | 14 |
| 6 | 5 | 7 | 4 | 8 | 3 | 9 | 2 | 10 | 1 | 11 | 12 | 13 | 14 |
| 6 | 7 | 5 | 8 | 4 | 9 | 3 | 10 | 2 | 11 | 1 | 12 | 13 | 14 |
| 7 | 6 | 8 | 5 | 9 | 4 | 10 | 3 | 11 | 2 | 12 | 1 | 13 | 14 |
| 7 | 8 | 6 | 9 | 5 | 10 | 4 | 11 | 3 | 12 | 2 | 13 | 1 | 14 |
| 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | 14 | 1 |
| 8 | 9 | 7 | 10 | 6 | 11 | 5 | 12 | 4 | 13 | 3 | 14 | 2 | 1 |
| 9 | 8 | 10 | 7 | 11 | 6 | 12 | 5 | 13 | 4 | 14 | 3 | 2 | 1 |
| 9 | 10 | 8 | 11 | 7 | 12 | 6 | 13 | 5 | 14 | 4 | 3 | 2 | 1 |
| 10 | 9 | 11 | 8 | 12 | 7 | 13 | 6 | 14 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 9 | 12 | 8 | 13 | 7 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 10 | 12 | 9 | 13 | 8 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 10 | 13 | 9 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 11 | 13 | 10 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 13 | 11 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 12 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 14 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
2. Обзор алгоритмов сортировки
Сортировка — это процесс перестановки объектов данного множества в определённом порядке. Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки присутствуют во многих задачах прикладного программирования.
Рассмотрим алгоритмы сортировки «на месте», то есть те алгоритмы в которых не используется копирование массива.
Удобной мерой эффективности алгоритмов сортировки «на месте» является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов.
Эффективные алгоритмы сортировки требуют порядка
сравнений, где N — число элементов, а С — число необходимых сравнений.
Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка
Методы сортировки «на месте» можно разбить на три основных класса:
сортировка выбором
сортировка вставками
сортировка обменом
В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется
Рисунок 1. Сортировка простым выбором
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная — укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).
Рисунок 2. Сортировка простыми включениями
Основная характеристика сортировки обменом — перестановка местами двух соседних элементов, если они расположены не так, как требует отсортированный массив.
Рисунок 3. Сортировка простым обменом
В рассмотренной классификации существуют разные алгоритмы. Они отличаются сложностью, быстротой выполнения, последовательностью операций.
Например:
сортировка вставками;
пузырьковая сортировка;
корневая сортировка;
пирамидальная сортировка;
сортировка слиянием;
быстрая сортировка;
сортировка Шелла и др.
Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).
Сортировка массива простым выбором
Метод основан на следующем правиле:
Выбирается элемент с наибольшим значением ключа
Он меняется местами с последним элементом arr . Затем эти операции повторяются с оставшимися первыми s-1 элементами, затем — с s-2 первыми элементами и т.д. до тех пор, пока не останется только первый элемент — наименьший. Пример сортировки методом простого выбора показан на рисунке 4:
Рисунок 4. Сортировка массива простым выбором
Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Операция сравнения выполняется в теле цикла с управляющей переменной k
и средним числом повторений size/2. Этот цикл, в свою очередь, находится в теле цикла с управляющей переменной L
и числом повторений size −1. Таким образом, число сравнений
С= (size −1) * size −1/2
Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по k
дает результат «истина» в половине случаев, то среднее число пересылок в этом цикле равно size/4. Цикл по L
, как указывалось выше, выполняется size −1 раз и в теле цикла выполняется три пересылки и цикл по k
. С учетом этого число пересылок:
М= (3+ size/4) * (size −1)
Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально .
Метод пузырька
Сортировка пузырьком в основном применяется в учебных проектах. В реальной практике её заменяют более эффективные алгоритмы, однако сортировка пузырьком лежит в основе некоторых из них.
В общем случае алгоритм сортировки пузырьком следующий:
- Сравнить текущий элемент со следующим.
- Если следующий элемент меньше/больше текущего, поменять их местами.
- Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.
В алгоритме используется два цикла: основной и вложенный. В результате одного прохода вложенного цикла наибольший элемент помещается в конец массива, а наименьший смещается на одну позицию ближе к началу.
Внешний цикл в худшем случае совершает N (кол-во элементов) – 1 проходов, то есть внутренний цикл выполняется N-1 раз.
Таким образом, в каждом проходе совершается серия обменов элементов так, что наибольший элемент передвигается в конец массив перед элементом, который переместился туда в прошлой итерации. Процесс происходит до тех пор, пока массив не будет отсортирован.
Если рассмотреть реализацию алгоритма, то можно легко заметить, что время его работы (количество операций) значительно возрастает с увеличением количества элементов сортируемой последовательности.
Проточная порометрия
Перенос жидкости или газа через пористую
среду связан с параметрами этой среды.
Проточный метод изучения пористой
структуры основан на зависимости
удельной производительности от параметров
пористости. Расчет основан на уравнении
Пуазейля:
π r4∆P
V= ———— (4.25)
8ηδ
Модель упрощена до представления
мембраны как пористого тела с прямыми
цилиндрическими порами. Реальность
поры, т.е. ее извилистость, шероховатость,
анизотропность, учитывается эмпирическими
коэффициентами.
Рис. 4.67. Ячейка для определения среднего
размера пор в мембранах:1-верхняя
крышка;
2-уплотнителъное кольцо;
3-мембрана;
4-пористая подложка;
5-сетка; 6-нижняя крышка;
7-корпус ячейки;
8-уплотнительная прокладка (резиновое
кольцо)
Для стандартизации условий испытаний
используют ячейки с постоянной площадью
мембраны (рис.4.67).
На дно нижней крышки 6 помещают
металлическую сетку 5, затем подложку
4, испытываемую мембрану 3, уплотнительное
кольцо 2. Толщину мембраны предварительно
измеряют микрометром. Регулируют
давление сжатого воздуха и измеряют
производительность образца по жидкости,
заливаемой в ячейку.
Если бы поры в мембране были все одинаковы,
мы имели бы графическую зависимость
проницаемости от давления как на левой
части рис.4.68.
Сначала мембрана остается непроницаемой,
поскольку для продавливания жидкости
через любую пору необходимо некоторое
давление. ВеличинаРminопределяется смачиваемостью мембраны
жидкостью и размером самых больших пор.
Рис. 4.68. Зависимость удельной
производительности мембраны от
приложенного давления для идеальной
(слева) и реальной (справа) мембраны
В реальной мембране всегда существует
некоторое распределение пор по размерам,
поэтому кривая проницаемости сначала
имеет S-образный участок, а затем линейный.
Уравнение Пуазейля можно записать для
выражения количества жидкости, прошедшей
через мембрану площадью S с числом пор
N на единице площади за время t:
π r4∆PtSN
V= ————— (4.26)
8ηδ
В свою очередь N= П/ πr3,
где П — общая пористость мембраны, отсюда
8 ηδV8 ηG
r= ————— = ———— (4.27)
П∆PtSП∆P
Расчет, проведенный по данным линейного
участка зависимости на рис.4.68,
даст величину среднего размера пор
мембраны, что для мембран с узким
распределением пор является достаточной
характеристикой.
Принимаемые в методе допущения (о
цилиндричности и неизвилистости пор,
постоянстве сечения по всей длине
отдельных пор, равенстве общей и
эффективной, т.е. участвующей в транспорте
жидкости, пористости мембраны) вносят
определенные погрешности в оценку
среднего размера пор ультрафильтрационных
мембран. В частности, извилистость
реальных пор приводит при расчетах к
заниженным значениям их размеров. К
заниженным результатам приводит и
различие в общей и эффективной пористости
мембран вследствие ориентационной
упорядоченности пор.
К уменьшению величины эффективной
пористости по сравнению со значениями,
используемыми в расчетах, а, следовательно,
и занижению результатов, приводит
наличие в мембранах не участвующих в
течении пристенных слоев связанной
воды.
Толщина таких гидродинамически
неподвижных слоев составляет примерно
1 нм и, следовательно, вклад этого фактора
становится весьма ощутимым для
сравнительно тонкопористых мембран.С
другой стороны, асимметрия структуры
мембраны приводит к завышенным значениям
средних размеров пор. Это в определенной
мере нивелирует их занижение вследствие
неучета пристенных слоев воды, извилистости
и ориентационной упорядоченности пор.
Итак, в реальной мембране существуют
поры разного размера, поэтому зависимость
Gот ΔР на рисунке 4.67 имеетS-образный характер, т.е.
по мере повышения давления в работу
включаются все меньшие поры. Если
проводить ступенчатое по ΔР исследование,
то на каждый прирост ΔР наложится
прирост вG(рисунок 4.69).
Рис. 4.69. Графическая дифференциация
зависимости удельной производительности
мембраны от приложенного давления
В расчете будем использовать
модифицированные уравнения Пуазейля
и Лапласа:
π∙r4i—jt∙S∙Ni—j
Vi—j= ────────── ∙Pj(4.28)
8 ηδ
Pj=
2σ/ri—j(4.29)
Из них получим расчетные выражения для
rиN:
r∙δ
Ni—j= ──── ∙P3j∙ΔGi—j(4.30)
2πσ4
ri—j= 2σ/Pj(4.31)
Рассчитав для каждого интервала i-jэти две величины, получим информацию
для построения зависимостиNi—jдля каждого интервалаri—j(рис. 4.70).
Рис. 4.70. Зависимость «количество пор
– радиус пор»,
т.е. кривая распределения пор по размеру
Распределение пор по размеру является
наиболее объективной характеристикой
пористой мембраны.
Тестирование разработанных функций сортировки методом простых вставок и методом пузырька
В ходе работы над курсовым проектом было разработано 2 функции: функция сортировки массива методом простых вставок, и функция сортировки массива методом пузырька. Так же в разработанной программе использована функция подсчета времени работы программы clock (), содержащаяся в библиотеке time. h. Массив формируется автоматически с помощью встроенной функции randomize (), пользователю нужно лишь задать число элементов в массиве и выбрать метод сортировки. После чего будет выполнена сортировка выбранным методом, выведен на экран упорядоченный массив и время сортировки в миллисекундах.
Для тестирования работы программы совершим несколько прогонов с разными значениями. В качестве отчета о работе программы приведены скриншоты:
Рисунок 12. Скриншот работающей программы, сортировка методом простых вставок
Рисунок 13. Скриншот работающей программы, сортировка методом пузырька
Как видно на скриншотах программа успешно выполняет сортировку методом простых вставок и методом пузырька и выводит время сортировки.
Анализ
Пример пузырьковой сортировки. Начиная с начала списка, сравните каждую соседнюю пару, поменяйте их местами, если они не в правильном порядке (последняя меньше первой). После каждой итерации нужно сравнивать на один элемент меньше (последний), пока не останется больше элементов для сравнения.
Производительность
Пузырьковая сортировка имеет наихудший случай и среднюю сложность О ( n 2 ), где n — количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют существенно лучшую сложность в худшем случае или в среднем, часто O ( n log n ). Даже другое О ( п 2 ) алгоритмы сортировки, такие как вставки рода , как правило , не работать быстрее , чем пузырьковой сортировки, а не более сложным. Следовательно, пузырьковая сортировка не является практическим алгоритмом сортировки.
Единственное существенное преимущество пузырьковой сортировки перед большинством других алгоритмов, даже быстрой сортировкой , но не сортировкой вставкой , заключается в том, что в алгоритм встроена способность определять, что список сортируется эффективно. Когда список уже отсортирован (в лучшем случае), сложность пузырьковой сортировки составляет всего O ( n ). Напротив, большинство других алгоритмов, даже с лучшей средней сложностью , выполняют весь свой процесс сортировки на множестве и, следовательно, являются более сложными. Однако сортировка вставкой не только разделяет это преимущество, но также лучше работает со списком, который существенно отсортирован (с небольшим количеством инверсий ).
В случае больших коллекций следует избегать пузырьковой сортировки. Это не будет эффективно в случае коллекции с обратным порядком.
Кролики и черепахи
Расстояние и направление, в котором элементы должны перемещаться во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы перемещаются в разных направлениях с разной скоростью. Элемент, который должен переместиться в конец списка, может перемещаться быстро, потому что он может принимать участие в последовательных заменах. Например, самый большой элемент в списке будет выигрывать при каждом обмене, поэтому он перемещается в свою отсортированную позицию на первом проходе, даже если он начинается с начала. С другой стороны, элемент, который должен двигаться к началу списка, не может перемещаться быстрее, чем один шаг за проход, поэтому элементы перемещаются к началу очень медленно. Если наименьший элемент находится в конце списка, потребуется n -1 проход, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа о Черепахе и Зайце .
Были предприняты различные усилия по устранению черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей — это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n 2 ) . Комбинированная сортировка сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам для сглаживания списка. Его средняя скорость сопоставима с более быстрыми алгоритмами вроде быстрой сортировки .
Пошаговый пример
Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему с помощью пузырьковой сортировки. На каждом этапе сравниваются элементы, выделенные жирным шрифтом . Потребуется три прохода;
- Первый проход
- ( 5 1 4 2 8) → ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.
- (1 5 4 2 8) → (1 4 5 2 8), поменять местами, поскольку 5> 4
- (1 4 5 2 8) → (1 4 2 5 8), поменять местами, поскольку 5> 2
- (1 4 2 5 8 ) → (1 4 2 5 8 ). Теперь, поскольку эти элементы уже в порядке (8> 5), алгоритм не меняет их местами.
- Второй проход
- ( 1 4 2 5 8) → ( 1 4 2 5 8)
- (1 4 2 5 8) → (1 2 4 5 8), поменять местами, поскольку 4> 2
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8 ) → (1 2 4 5 8 )
Теперь массив уже отсортирован, но алгоритм не знает, завершился ли он. Алгоритм нужен один весь проход без какой — либо свопа знать сортируется.
- Третий проход
- ( 1 2 4 5 8) → ( 1 2 4 5 8)
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8 ) → (1 2 4 5 8 )
Заключение
Метод пузырька гораздо менее эффективен других алгоритмов, однако он имеет простую и понятную реализацию, поэтому часто используется в учебных целях. Кроме того, пузырьковая сортировка может использоваться для работы с небольшими массивами данных.
На самом деле, вместо самостоятельного написания алгоритмов сортировки программисты на Python используют стандартные функции и методы языка, такие как и . Эти функции отлажены и работают быстро и эффективно.
Знания особенностей алгоритмов сортировки, их сложности и принципов реализации в общем виде пригодятся каждому программисту, желающему пройти собеседование и стать Python-разработчиком.
