Главная->Інформатика та програмування->Содержание->Сортировка методом пузырька

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В C++ (4-Е ИЗДАНИЕ) (часть 10) онлайн

Сортировка методом пузырька

Функция bsort() при сортировке массива использует вариацию метода пузырька. Это простая сортировка (хотя довольно медленная). Рассмотрим ее алгоритм. Допустим, что мы хотим расставить элементы массива в порядке возрастания. Сначала первый элемент массива (arr [ 0 ]) сравнивается по очереди с остальны- ми элементами (начиная со второго). Если он больше, чем какой-либо из эле- ментов массива, то эти элементы меняются местами. Когда это будет проделано, то нам будет известен первый элемент последовательности, самый маленький. Затем мы сравниваем второй элемент по очереди со всеми остальными, начиная с третьего, и вновь меняем местами элементы, если найдется элемент в массиве меньший, чем второй. После этих действий нам будет уже известен второй эле- мент последовательности, второй по величине. Этот процесс продолжается далее для всех остальных элементов до предпоследнего, затем массив будет считаться упорядоченным. На рис. 10.8 показана сортировка методом пузырька в действии (с несколькими элементами из PTRSORT).

В PTRSORT на первом месте стоит число 37, оно сравнивается с каждым элементом по очереди и меняется местами с числом 11. На втором месте стоит число 84, которое тоже сравнивается со всеми элементами. Оно меняется места- ми с числом 62, затем число 62 (которое оказалось теперь на втором месте) ме- няется местами с числом 37, 37 меняется местами с 28, а 28 с 19. На третьем месте вновь оказывается число 84, оно меняется с 62, которое меняется с 57, затем 57 с 37 и 37 с 28. Процесс продолжается до тех пор, пока массив не будет отсортирован.

Функция bsort() состоит из двух вложенных циклов, каждый из которых кон- тролирует указатель. Внешний цикл использует переменную j, внутренний — переменную к. Выражения ptr+j и ptr+k указывают на различные элементы мас- сива, которые определяются переменными цикла. Выражение ptr+j используется для перемещения по массиву, начиная с первого элемента до предпоследнего. Для каждой позиции, на которую указывает ptr+j во внешнем цикле, выражение ptr+k внутреннего цикла перемещается, начиная со следующего элемента и до конца массива. Элементы внешнего и внутреннего цикла ptr+j и ptr+k сравнива-

ются с использованием функции order(), и если первый больше, чем второй, то они меняются местами. На рис. 10.9 показан этот процесс.

Внешний цикл

Рис. 10.8. Действия при сортировке методом пузырька

Рис. 10.9. Действия программы PTRSORT

Пример PTRSORT позволяет оценить механизм указателей. Они предостав- ляют возможность последовательно и эффективно работать с элементами мас-

 

внутренний цикл

сива и другими переменными, имена которых нам не известны в определенной функции.

Указатели на строки

Как мы заметили в главе 7, строки — это просто массивы элементов типа char. Таким образом, доступ через указатели может быть применен к элементам стро- ки так же, как и к элементам массива.

 

17