Суть «пузырькового» метода

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

Существует много методов сортировки данных, все эти методы можно отнести к одному из следующих классов: 1) перестановка

2) отбор

3) вставка

Преимущества при выборе метода:

- скорость исполнения сортировки

- многие методы сортировки обладают уникальными характеристиками, влияющими на их применимость в том или ином случае

Критерии, используемые при выборе сортировки:

- средняя скорость сортировки

- скорость сортировки в наилучшем и наихудшем случаях

- естественно или нет поведение алгоритма

- выполняет ли он сортировку элементов с совпадающими ключами

Скорость сортировки зависит от количества выполняемых сравнений и следующих за ними перестановок.

Наилучшая и наихудшая скорость важны в том случае, если вы имеете основание ожидать повторения одной их этих ситуаций.

Очень часто при хорошей средней скорости алгоритмы обладают неприемлемой наихудшей.

Под естественностью поведения понимают следующее: если список уже упорядочен, алгоритм должен выполнять минимальное количество операций; если не упорядочен, алгоритм выполняет больший объем работы; и большую работу он должен выполнять, если список отсортирован в обратном порядке.

Самым известным методом сортировки является - “ пузырьковый” метод.

Пусть элементы массива а: 8 3 6 4 2

1 2 3 4 5

Пусть i=1, тогда а>асравнивают, если да, то перестановка.

p=а

а=2

а=p

если а>a, то снова перестановка и т.д.

т.е. 3 8 6 4 2

. . . . . . .

если а>а, снова перестановка.

т.е. 2 8 6 4 3

На первом месте должен стоять самый “легкий” элемент.

Для i=2.

Организуется цикл для i=1,n-1

цикл для j=i+1,n

если а>a, то перестановка p=a

а=a

a=p

Пример:

#include <stdio.h>

#include <conio.h>

#define size 50

void main( )

{ // Сортировка массивов различными методами.

int i, j, n;

float a[size], b[size], c[size], d[size];

float prom; // Промежуточная переменная.

crscr( );

// Ввод массива.

printf (“\n Введите размер массива n=”);

scanf (“%d”,&n);

printf (“\n Введите элементы массива:\n”);

for (i=0; i<n; i++)

scanf (“%f”,&a[i]);

printf (“\n Исходный массив:\n”);

for (i=0; i<n; i++)

printf (“%.2f “,a[i]);

// Копируем массив а в b,c,d.

for (i=0; i<n; i++)

b[i]=c[i]=d[i]=a[i];

. . . } // Печать массивов b, c, d.

// Простая версия “пузырьковой” сортировки.

for (i=0; i<n-1; i++)

for (j=i+1; j<n; j++)

if ( a[i]>a[j] )

{ prom=a[i];

a[i]=a[j];

a[j]=prom;

}

printf (“\n \t Отсортирован массив а: \n”);

. . . . .}Печать массивов.

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

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

Всего сравнений: , где n-количество элементов.

В наилучшем случае количество перестановок = 0.

Количество перестановок в среднем случае:

В худшем случае:

Пузырьковая сортировка называется n-квадратичным алгоритмом, т.к. время выполнения пропорционально квадрату количества элементов массива, поэтому при работе с большими массивами не используется.