АЛГОРИТМЫ МЕТОДОВ СОРТИРОВКИ И ПОИСКА

 

Цель: Изучить существующие алгоритмы сортировки списков (массивов) и поиска их элементов и разработать программу для реализации этих методов.

 

Теоретические сведения

 

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них (рис.15.1).

 

		Прямые методы сортировки

 

Рис. 15.1 Виды прямых методов сортировки

Пример 15.1

Функция для перемены местами элементов:

void swap(int *х, int *y)

{

int t = *x; /*промежуточная переменная*/

/* Перемена данных местами */

*х = *у;

*y = t;

}

1. Пузырьковая сортировка (методом обмена).

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,..., K'n >, в котором для любого 1< =i< =n элемент K'(i) < = K'(i+1).

При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

 

Пример 15.2

Функция BubbleSort() реализует алгоритм сортировки методом «пузырька»:

void BubbleSort(int a[], int n)

{

/*функции передается массив и его размерность */

int i, j; /* переменные цикла */

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

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

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

/*если элемент " тяжелее" следующего

swap(& a[j-1], & a[j]) /*поменять их местами */

}

Анализ пузырьковой сортировки.

Пузырьковая сортировка обладает несколькими характеристиками:

• после каждой итерации только один элемент данных помещается в свою правильную позицию;

• сравнение и перестановка смежных элементов данных;

• в каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок;

• худший случай — когда элементы данных отсортированы в обратном порядке;

• лучший случай — когда элементы данных уже отсортированы в правильном порядке;

• легкость реализации.