Сортировка методом вставки.

ЛАБОРАТОРНАЯ РАБОТА №7.

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

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

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

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

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

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

Пример 7.1

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

void swap(int *х, int *y) {

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

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

*х = *у;

*y = t;

}

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

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=, в котором для любого 1

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

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

Пример 7.1

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

void BubbleSort(int a[],int n)

{ /*функции передается массив */

/* и его размерность */

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

for (i=0; i

for (j=n-1; ji; j—)

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

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

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

}

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

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

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

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

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

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

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

• Пузырьковая сортировка легко реализуется.

Сортировка методом выбора.

Алгоритм:

  • Находится наименьший элемент в массиве.
  • Найденный элемент меняется с первым элементом.
  • Процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее, пока в конце не останется самый большой элемент, который перемещать уже не нужно.

Пример 7.2

void MinSort(int a[], int n)

{

int i, j, k;

for (i=0; i

{

for (k=i; j=i+1; j

if (a[j] a[k]) // минимальный элемент

{

k = j; // запоминаем его номер в к

swap(a[k],a[i]);// меняем местами минимальный и

} // элем, с которого начинался цикл

}

}

Сортировка методом вставки.

Сортировка вставками — очень простой метод сортировки, при котором элементы данных используются как ключи для сравнения. Этот алгоритм сначала упорядочивает А[0] и А[1], вставляя А[1] перед А[0], если А[0] А[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный список. После k-й итерации элемент A[k] оказывается в своей правильной позиции и элементы от А[0] до A[k] уже отсортированы.

Пример 7.3

Функция InsertSort() реализует алгоритм сортировки методом вставки:

void InsertSort (int a[], int n)

{

int i, j

for (i=1; i

{ j=i;

while (a[j]=1)

{

Swap(a[j],a[j-1]);

j—; }

}

}

Анализ сортировки вставками.

Сортировка вставками обладает следующими характеристиками:

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

• При сортировке вставками выполняется меньше перестановок, чем в пузырьковой сортировке.

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

• Сортировка вставками легко реализуется.

Сортировка вставками (Insertion Sort). Фрагмент 7 лекции cs50


Похожие статьи.

Понравилась статья? Поделиться с друзьями: