Сортировка простым обменом.

Алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Проходя по массиву, каждый раз просеивается наименьший элемент оставшегося множества, двигаясь к левому концу массива (или наибольший - к правому концу). Этот метод широко известен как сортировка методом пузырька.

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

void Sort_Bubble (int m[],

int n)

{

int i, j, k ;

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

for ( j = n; j >= i; j ++)

if ( m[j - 1] > m[j] )

{

k = m[j];

m[k] = m[j - 1];

m[j - 1] = k;

}

}

void Sort_Shaker (int m[],

int n)

{

int i, k, l=0, r=n-1, x;

while(l < r)

{

for ( i = r; i > l; i --)

if( m[i-1] > m[i])

{

x=m[i-1];m[i-1] = m[i];

m[i] = x; k = i; }

l = k + 1;

for ( i = l; i < r; i ++)

if( m[i-1] > m[i])

{x=m[i-1];m[i-1]= m[i];

m[i] = x; k = i; }

r = k - 1;

}}

Анализ сортировки методом пузырька. Число сравнений в алгоритме простого обмена равно C = ½ (n² - n), а минимальное, среднее и максимальное количества пересылок элементов равны: M _min = 0, M _ср. = ¾ (n² - n), M _max = 3/2 (n² - n).

3. Пример программной реализации

Сортировка массива методом «пузырька». Массив представляет собой строку символов. Используются библиотечные функции: позиционирования курсора на экране - gotoxy(у, х); вывода символа на экран - putch(с); задержка по времени вывода символов на экран - delay(PAUSE).

#define S 3

#define PAUSE 500

void sort(char *s)

{

char tmp;

int i,j, n = strlen(s);

// отключаем курсор

_setcursortype(_NOCURSOR);

for(i = n-1; i > 0; i --)

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

if (s[j] > s[j+1])

{

// меняем символы на экране

gotoxy(j+1, S); putch(' ');

gotoxy(j+1, S+1); putch(s[j]);

gotoxy(j+2, S); putch(' ');

gotoxy(j+2,S-1);putch(s[j+1]);

delay(PAUSE);

gotoxy(j+1, S+1); putch(' ');

gotoxy(j+2, S+1); putch(s[j]);

gotoxy(j+2, S-1); putch(' ');

gotoxy(j+1,S-1);putch(s[j+1]);

delay(PAUSE);

gotoxy(j+2, S+1);putch(' ');

gotoxy(j+2, S); putch(s[j]);

gotoxy(j+1, S-1);putch(' ');

gotoxy(j+1,S);putch(s[j+1]);

delay(PAUSE);

// меняем элементы в памяти

tmp=s[j]; s[j]=s[j+1]; s[j+1]=tmp;

}

}

void main()

{

char str[80];

clrscr();

puts("Enter string:\n");

sort(gets(str));

getch();

}

4. Варианты заданий.

1. Сортировка выбором (процесс сортировки отображать на экране):

а) Минимальный элемент переносится в начало массива.

б) Максимальный элемент переносится в конец массива.

2. Сортировка подсчетом: путем попарного сравнения в отдельном массиве подсчитывается количество элементов меньше данного, что определяет место размещения элемента в выходном массиве (процесс сортировки отображать на экране):

а) Результирующий массив формируется слева направо.

б) Элементы исходного массива выбираются слева направо.

3. Сортировка вставками (процесс сортировки отображать на экране):

а) Метод «погружения»: очередной элемент путем последовательности обменов «погружается» до требуемой позиции в уже упорядоченную часть массива.

б) Метод «включения»: определяется место в отсортированной части массива, куда должен помещаться элемент. Элементы от данной позиции сдвигаются вправо, и на освободившееся место помещается включаемый элемент.

4. Оптимизированный метод пузырька (процесс сортировки отображать на экране).

5. Шейкер – сортировка (процесс сортировки отображать на экране).

5. Контрольные вопросы

   1. Что такое сортировка? Перечислите основные типы сортировок.

   2. Приведите примеры практического использования сортировки.

3. Проведите сравнительный анализ эффективности основных алгоритмов сортировки.