Новости

Алгоритм сортировки методом пузырька

Работа добавлена:






Алгоритм сортировки методом пузырька на http://mirrorref.ru

Лабораторная работа №2

Теория алгоритмов

Алгоритм сортировки методом пузырька

Теория:

Сортировка методом пузырька - самый простой алгоритм сортировки. Правда, и самый медленный. В будущем мы рассмотрим и другие алгоритмы сортировки.

Сортировка - это размещение информации в определённом порядке. Например, элементы массива можно разместить по возрастанию, тогда в начале массива окажется наименьшее значение, а в конце - наибольшее.

Сортировка методом пузырька работает следующим образом: в итерации цикла берётся самый первый элемент и сравнивается со следующим. Если первый элемент больше, то элементы меняются местами. Затем происходит сравнение второго с третьим и т.д. После первой итерации цикла в конце оказывается самый большой элемент. После второй итерации на предпоследней позиции оказывается второй по величине элемент. Всего в цикле необходимо произвести на одну итерацию меньше количества элементов в массиве.

Выдержка из wikipedia

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n-1], A[n]

t := истина

цикл пока t:

 t := ложь

 цикл для j = 1, 2, ..., n − 1:

   если A[j] > A[j+1],то:

обменять местами элементы A[j] и A[j+1]

     t := истина

Булевая переменная t используется для того, чтобы определить, был ли произведён хотя бы один обмен на очередной итерации внешнего цикла. Алгоритм останавливается, когда таких обменов не было.

Можно показать, что для сортировки требуется сделать не более n − 1 итераций внешнего цикла, поэтому в некоторых реализациях внешний цикл всегда выполняется ровно n − 1 или n раз, и не отслеживается, были ли обмены или нет на каждой итерации.

Задание:

Необходимо реализовать блок-схему описанного алгоритма и сделать сортировку вручную по данному алгоритму заданных по варианту массивов.

Исходные данные:

Массив элементов размера N.

Сортировка осуществляется методом, описанным в теории.

Пример 1 сортировка по убыванию:

# Начало алгоритма

A=[3,1,2]

# [первый проход]

3 < 1 #false, переход к следующей итерации [3,1,2]

1 < 2 #true, меняем местами   [3,2,1]

# [/первый проход]

# [второй проход]

3 < 2 #false

2 < 1 #false

# [/второй проход]

# Конец алгоритма

Пример 2 сортировка по возрастанию:

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 14 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(15 4 2 8) (14 5 2 8), Меняет местами, так как 5 > 4

(1 45 2 8) (1 42 5 8), Меняет местами, так как 5 > 2

(1 4 25 8) (1 4 25 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 42 5 8) (1 42 5 8)

(14 2 5 8) (12 4 5 8), Меняет местами, так как 4 > 2

(1 24 5 8) (1 24 5 8)

(1 2 45 8) (1 2 45 8)

Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(12 45 8) (12 4 5 8)

(1 24 58) (1 24 5 8)

(1 2 45 8) (1 2 45 8)

Теперь массив отсортирован и алгоритм может быть завершён.

Варианты

  1. [1,7,4,9,8,6] - алгоритм сортировки пузырьком по возрастанию + блок-схема.
  2. [4,5,7,8,3,5] - алгоритм сортировки пузырьком по убыванию + блок-схема.
  3. [1,2,7,4,8,9] - алгоритм сортировки пузырьком по возрастанию + блок-схема.
  4. [9,1,8,2,7,3] - алгоритм сортировки пузырьком по возрастанию + блок-схема.
  5. [5,5,4,9,8,9] - алгоритм сортировки пузырьком по убыванию + блок-схема.

Задание на +5 балов.

Как поменять местами значения 2-х переменных без привлечения 3-ей?

Пример:

а=3

b=5

// ваши действия

итог: a=5, b=3

Алгоритм сортировки методом пузырька на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Алгоритм обчислення кореня рівняння методом ітерацій

2. Хорнівські диз’юнкти. Принцип резолюцій. Алгоритм уніфікації. Процедура доказу теорем методом резолюцій для хорнівських диз’юнктів. Особливості роботи з негативними знаннями в Пролозі

3. Алгоритм жазу жолдарымен құрылымымен таныстыру. Алгоритм құруға үйрету

4. Алгоритм Прямого поиска. Алгоритм Бойера-Мура

5. Алгоритм стиснення з втратами. Фрактальний алгоритм

6. Алгоритмы поиска и сортировки

7. IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных

8. Понятие сортировки. Виды сортировок

9. Приложение для сортировки числового массива с помощью кучи

10. ОСНОВНЫЕ ПРИНЦИПЫ МЕДИЦИНСКОЙ СОРТИРОВКИ ПРИ МАССОВОМ ПОСТУПЛЕНИИ РАНЕНЫХ И БОЛЬНЫХ