• Поиск

    Введите ваш запрос для начала поиска.

  • Об авторах

    Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.

    Основные цели сайта

      Сайт предназанчен для максимально эффективного и быстрого доступа ко всем материалам курса "Алгоритмы и структуры данных", имеющимся на кафедре компьютерных технологий и систем КубГАУ. Основной задачей его создания является повышения эффективности освоения дисциплины студентами и всеми желающими.

Алгорим сортировки методом прямого обмена (пузырковой сортировки) :

for i = 2 to n

  for j = n to i step -1

    if a(j) < a(j - 1) then

                            x = a(j - 1)

                            a(j - 1) = a(j)

                            a(j) = x

    endif

   next j

next i

return

 

Рассмотрим пример.

Пусть дан массив из  следующих элементов: 4, 3, 7, 2, 1, 6.

На нижеприведенном рисунке изображена иллюстрация алгоритма пузырьковой сортировки для рассматриваемого массива.  

В данном случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а, значит, не проводить сравнения, затрачивая на это время, можно ввести флажок fl, который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. Ниже приведен усовершенствованный алгоритм.

fl = true

for i = 2 to n

if fl = false then return

endif

fl = false

  for j = n to i step -1

    if a(j) < a(j - 1) then

      fl = true

      x = a(j - 1)

      a(j - 1) = a(j)

      a(j) = x

    endif

  next j

next i

return

 

Еще одним усовершенствованием алгоритма является так называемая шейкерная сортировка, где после каждого прохода меняется направление во внутреннем цикле.

В случае, если реализовывать алгоритм пузырьковой сортировки без усовершенствований, то

Количество сравнений:

Cmax = n(n-1)/2              

Количество перемещений:      

Мmax=3Cmax=3n(n-1)/2           

Из приведенных расчетов следует, что эффективность сортировки данным методом также имеет порядок n2.

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