Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




 

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

 

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

 

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них (рис.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) перестановок;

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

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

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







Дата добавления: 2014-11-10; просмотров: 138. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.007 сек.) русская версия | украинская версия