Студопедия

КАТЕГОРИИ:

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



Алгоритм пузырьковой сортировки




Читайте также:
  1. Алгоритм RSA
  2. Алгоритм виконання часткового технологічного процесу
  3. Алгоритм выборки сообщений из очереди потока
  4. Алгоритм выполнения манипуляции
  5. Алгоритм выполнения манипуляции
  6. Алгоритм выполнения манипуляции
  7. Алгоритм вычисления выражений в обратной польской записи
  8. Алгоритм Дейкстры
  9. Алгоритм загрузки операционной системы
  10. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ

У нас имеется некоторая последовательность и требуется сделать так, чтобы эти числа стали упорядоченными по возрастанию. Как это делается в алгоритме пузырьковой сортировки. Мы начинаем с самого начала нашей последовательности и сравниваем последовательно два числа. Если правое число меньше левого, то мы меняем эти числа местами. В противном случае мы ничего не делаем.

Сравниваем первые два числа так как правое число больше левого, то мы соответственно ничего не делаем.

 

Сравниваем следующие два числа: так как 5<8, то мы меняем эти числа местами. Далее сравниваем 3 и 4 позиции: 7<8 -> меняем местами. Сравниваем 4 и 5 позиции 3<8, следовательно их тоже меняем местами.

 

Когда доходим до предпоследней позиции, то мы заканчиваем алгоритм сортировки пузырьком. И теперь начинаем снова с первой позиции, но при этом восьмерку уже не берем в рассмотрении( она уже на своем месте).

Теперь снова сравниваем первые два числа нашей последовательности: 5>1, поэтому ничего не меняем. Следующие два числа тоже оставляем на своих позициях. А вот последние два числа 3 и 7 меняем местами.

Опять уменьшаем количество рассматриваемых чисел нашей последовательности(цифры 7 и 8 уже на своих местах).

 

Снова начинаем с самого начала и проделываем то же самое.

И вот осталось сравнить два последних числа(3>1), поэтому ничего не делаем.

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

Вот ссылка на видео)) http://www.youtube.com/watch?v=5JMInXAtnQg

 

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

Сортировка вставками

Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.

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



1. первая и вторая карта меньше третьей;

2. первая и вторая карта больше третьей;

3. первая карта уступает значением третьей, а вторая превосходит ее;

4. первая карта превосходит значением третью карту, а вторая уступает ей.

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

Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.



C# (с возвратом результата)

public int[] InsertionSort(int[] array){ int[] result = new int[array.Length]; for (int i = 0; i < array.Length; i++) { int j = i; while (j > 0 && result[j - 1] > array[i]) { result[j] = result[j - 1]; j--; } result[j] = array[i]; } return result;}

C# (без дополнительной памяти 1)

public void InsertionSort(int[] array){ for (int i = 1; i < array.Length; i++) { int cur = array[i]; int j = i; while (j > 0 && cur < array[j - 1]) { array[j] = array[j - 1]; j--; } array[j] = cur; }}

C# (без дополнительной памяти 2)

public void InsertionSort(int[] array){ for (int i = 1; i < array.Length; i++) { int j; int buf = array[i]; for (j = i - 1; j >= 0; j--) { if (array[j] < buf) break; array[j + 1] = array[j]; } array[j + 1] = buf; }}

Вот видео для наглядности))) http://www.youtube.com/watch?v=ROalU379l3U

 

5) Пирамидальная сортировка.

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

Пирамидой (кучей) называется двоичное дерево такое, что

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

Подробнее

a[0] — минимальный элемент пирамиды.

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

Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды. Определяем правую часть дерева, начиная сn/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.



Например, массив для сортировки

24, 31, 15, 20, 52, 6

Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 - это элемент 15.

Результат просеивания элемента 15 через пирамиду.

Следующий просеиваемый элемент – 1, равный 31.

Затем – элемент 0, равный 24.

Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.

2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.

Продолжим процесс. В итоге массив будет отсортирован по убыванию.

C#[править]

static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N) { Int32 imax; Int32 buf; if ((2 * i + 2) < N) { if (arr[2 * i + 1] < arr[2 * i + 2]) imax = 2 * i + 2; else imax = 2 * i + 1; } else imax = 2 * i + 1; if (imax >= N) return i; if (arr[i] < arr[imax]) { buf = arr[i]; arr[i] = arr[imax]; arr[imax] = buf; if (imax < N / 2) i = imax; } return i; } static void Pyramid_Sort(Int32[] arr, Int32 len) { //step 1: building the pyramid for (Int32 i = len / 2 - 1; i >= 0; --i) { long prev_i = i; i = add2pyramid(arr, i, len); if (prev_i != i) ++i; } //step 2: sorting Int32 buf; for (Int32 k = len - 1; k > 0; --k) { buf = arr[0]; arr[0] = arr[k]; arr[k] = buf; Int32 i = 0, prev_i = -1; while (i != prev_i) { prev_i = i; i = add2pyramid(arr, i, k); } } } static void Main(string[] args) { Int32[] arr = new Int32[100]; //заполняем массив случайными числами Random rd = new Random(); for(Int32 i = 0; i < arr.Length; ++i) { arr[i] = rd.Next(1, 101); } System.Console.WriteLine("The array before sorting:"); foreach (Int32 x in arr) { System.Console.Write(x + " "); } //сортировка Pyramid_Sort(arr, arr.Length); System.Console.WriteLine("\n\nThe array after sorting:"); foreach (Int32 x in arr) { System.Console.Write(x + " "); } System.Console.WriteLine("\n\nPress the <Enter> key"); System.Console.ReadLine(); }

C# (другой вариант)[править]


Дата добавления: 2015-01-05; просмотров: 26; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты