Сортировка пузырьком
Содержание:
- Сортировка пузырьком Python
- C# с использованием лямбда-выражений
- D
- Таблица 2: Сортировка пузырьком в многопоточном режиме
- Сортировка массива методом пузырька- решение на C++
- Реализация пузырьковой сортировки в python:
- Как можно улучшить шейкер сортировку
- Пример работы алгоритма[править | править код]
- Метод Хоара — Быстрая сортировка(Quick-sort)
- Использовать
- Использовать
- Реализация
- Подробный разбор пузырьковой сортировки
- Turbo Basic 1.1
- Сортировка пузырьком
- Реализация [ править ]
- Анализ
Сортировка пузырьком Python
# Python реализация сортировки пузырьком
def bubbleSort(arr):
n = len(arr)
# Проход через все элементы массива
for i in range(n):
# Последние i элементы уже на месте
for j in range(0, n-i-1):
# проход массива от 0 до n-i-1
# Поменять местами, если найденный элемент больше
# чем следующий элемент
if arr > arr :
arr, arr = arr, arr
# Код тестирования
arr =
bubbleSort(arr)
print ("Сортированный массив:")
for i in range(len(arr)):
print ("%d" %arr),
Результат:
Сортированный массив: 11 12 22 25 34 64 90
Оптимизированная реализация
Приведенная выше сортировка методом пузырька всегда выполняется, даже если массив отсортирован. Ее можно оптимизировать путем остановки алгоритма, применяемой в том случае, если внутренний цикл не произвел никакой замены.
С/С++
// Оптимизированная реализация пузырьковой сортировки
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Оптимизированная версия пузырьковой сортировки
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr > arr)
{
swap(&arr, &arr);
swapped = true;
}
}
// Если в процессе прохода не было ни одной замены, то выход из функции
if (swapped == false)
break;
}
}
/* Функция вывода массива */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr);
printf("n");
}
// Программа тестирования функций, приведенных выше
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr);
bubbleSort(arr, n);
printf("Сортированный массив: n");
printArray(arr, n);
return 0;
}
C# с использованием лямбда-выражений
using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
{
if (!list.Any())
{
return Enumerable.Empty<T>();
}
var pivot = list.First();
var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();
return smaller.Concat(new[] { pivot }).Concat(larger);
}
//(тоже самое, но записанное в одну строку, без объявления переменных)
public static IEnumerable<T> shortQuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
{
return !list.Any() ? Enumerable.Empty<T>() : list.Skip(1).Where(
item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
.Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
}
}
D
array qsort(array)(array _a)
{
alias typeof(array.init) _type;
array filter(bool delegate(_type) dg, array a){
array buffer = null;
foreach(value; a) {
if(dg(value)){
buffer ~= value;
}
}
return buffer;
}
if(_a.length <= 1) {
return _a;
}
else {
return qsort( filter((_type e){ return _a >= e; }, _a ) ) ~ _a ~
qsort( filter((_type e){ return _a < e; }, _a ) );
}
}
Более короткий вариант с использованием стандартной библиотеки Phobos:
import std.algorithm;
T _qsort3(T)(T a) {
if( a.length <= 1 )
return a;
else
return _qsort3( a.filter!( e => a >= e ).array ) ~ a ~
_qsort3( a.filter!( e => a < e ).array );
}
Таблица 2: Сортировка пузырьком в многопоточном режиме
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 2 | 3 | 1 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 2 | 4 | 1 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 3 | 4 | 2 | 5 | 1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 3 | 5 | 2 | 6 | 1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 4 | 5 | 3 | 6 | 2 | 7 | 1 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 4 | 6 | 3 | 7 | 2 | 8 | 1 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 6 | 4 | 7 | 3 | 8 | 2 | 9 | 1 | 10 | 11 | 12 | 13 | 14 |
| 6 | 5 | 7 | 4 | 8 | 3 | 9 | 2 | 10 | 1 | 11 | 12 | 13 | 14 |
| 6 | 7 | 5 | 8 | 4 | 9 | 3 | 10 | 2 | 11 | 1 | 12 | 13 | 14 |
| 7 | 6 | 8 | 5 | 9 | 4 | 10 | 3 | 11 | 2 | 12 | 1 | 13 | 14 |
| 7 | 8 | 6 | 9 | 5 | 10 | 4 | 11 | 3 | 12 | 2 | 13 | 1 | 14 |
| 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | 14 | 1 |
| 8 | 9 | 7 | 10 | 6 | 11 | 5 | 12 | 4 | 13 | 3 | 14 | 2 | 1 |
| 9 | 8 | 10 | 7 | 11 | 6 | 12 | 5 | 13 | 4 | 14 | 3 | 2 | 1 |
| 9 | 10 | 8 | 11 | 7 | 12 | 6 | 13 | 5 | 14 | 4 | 3 | 2 | 1 |
| 10 | 9 | 11 | 8 | 12 | 7 | 13 | 6 | 14 | 5 | 4 | 3 | 2 | 1 |
| 10 | 11 | 9 | 12 | 8 | 13 | 7 | 14 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 10 | 12 | 9 | 13 | 8 | 14 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 11 | 12 | 10 | 13 | 9 | 14 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 11 | 13 | 10 | 14 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 12 | 13 | 11 | 14 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 12 | 14 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 13 | 14 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Сортировка массива методом пузырька- решение на C++
Сортировка массива методом пузырька- решение на C++
Алгоритм пузырьковой сортировки — это довольно простой в реализации алгоритм для сортировки массивов. Можно встретить и другие названия: пузырьковая сортировка, Bubble sort или сортировка простыми обменами — но все они будут обозночать один и тот же алгоритм. Назван так, потому что большее или меньшее значение «всплывает» (сдвигается) к краю массива после каждой итерации, это будет видно в примере.
Исходный код на языке C++
/*
* Ввести целочисленный массив из N целых чисел.
* Отсортировать этот массив по возрастанию методом пузырька
*/
#include <iostream>
using namespace std;
int main()
{
int *arr; // указатель для выделения памяти под массив
int size; // размер массива
// Ввод количества элементов массива
cout << «n = «;
cin >> size;
if (size <= 0) {
// Размер масива должен быть положитлеьным
cerr << «Invalid size» << endl;
return 1;
}
arr = new int; // выделение памяти под массив
// заполнение массива
for (int i = 0; i < size; i++) {
cout << «arr = «;
cin >> arr;
}
int temp; // временная переменная для обмена элементов местами
// Сортировка массива пузырьком
for (int i = 0; i < size — 1; i++) {
for (int j = 0; j < size — i — 1; j++) {
if (arr > arr) {
// меняем элементы местами
temp = arr;
arr = arr;
arr = temp;
}
}
}
// Вывод отсортированного массива на экран
for (int i = 0; i < size; i++) {
cout << arr << » «;
}
cout << endl;
delete [] arr; // освобождение памяти;
return 0;
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/* using namespacestd; intmain() { int*arr;// указатель для выделения памяти под массив intsize;// размер массива // Ввод количества элементов массива cout<<»n = «; cin>>size; if(size<=){ // Размер масива должен быть положитлеьным cerr<<»Invalid size»<<endl; return1; } arr=newintsize;// выделение памяти под массив // заполнение массива for(inti=;i<size;i++){ cout<<»arr = «; cin>>arri; } inttemp;// временная переменная для обмена элементов местами // Сортировка массива пузырьком for(inti=;i<size-1;i++){ for(intj=;j<size-i-1;j++){ if(arrj>arrj+1){ // меняем элементы местами temp=arrj; arrj=arrj+1; arrj+1=temp; } } } // Вывод отсортированного массива на экран for(inti=;i<size;i++){ cout<<arri<<» «; } cout<<endl; deletearr;// освобождение памяти; return; } |
Реализация пузырьковой сортировки в python:
Для сортировки в порядке возрастания:
# Python Bubble Sort program
def bubble_sort(list1):
for i in range(0,len(list1)-1): # The total number of passes,bubbles: i
for j in range(0,len(list1)-i-1): # The total number of iterations: j
if list1 > list1:
,list1 # swap elements
return list1
list1=
print(bubble_sort(list1))
ВЫХОД-
Пузырчатая сортировка python также работает со списком строк таким же образом.
list1= print(bubble_sort(list1))
При приведении приведенного выше списка функция возвращает вывод следующим образом:
Для сортировки в порядке убывания-
def bubble_sort_descending(list1):
for i in range(0,len(list1)-1):
for j in range(0,len(list1)-i-1):
if list1 < list1:# Observe '<' is used instead of '>'
,list1
return list1
list1=
print(bubble_sort_descending (list1))
OUTPUT-
Pass- 1 Pass- 2 Pass- 3 Pass- 4
Мы можем наблюдать, что получили правильный вывод 2-й проход итерации-2, но все же наш алгоритм продолжает сортировать уже отсортированный список. Это один из недостатков пузырьковой сортировки. Эта проблема может быть решена с помощью вставки или любого другого алгоритма сортировки. Для лучшего понимания Inserting sort посетите сайт http://pythonpool.com/insertion-sort-python/
Как можно улучшить шейкер сортировку
Вы наверно уже заметили, что самый большой элемент перемещается в конец массива (за первый цикл в ), а самый маленький элемент переместится вниз на одну ячейку.
В следующем цикле все уже произойдет наоборот: самый маленький элемент переместится в начала массива, а второй по размерам элемент переместится на одну ячейку вверх. Так же будет для оставшихся элементов.
- Поэтому ниже в строке 2: мы создали переменную , в ней будет находиться правая граница массива
- А в строке 3: создали переменную , в которой будет храниться начала массива.
Переменную мы будем уменьшать на один после первого цикла (который находится в строках 6 — 11), же будем уменьшать после второго цикла (ну или другими словами в самом конце цикла ).
Ниже, находится оптимизированная версия шейкер сортировки:
bool sort_or_not = true;
int right = n — 1; // n — размер массива
int left = 1;
do {
bool sort_or_not = true;
for (int i = left; i <= right; i++) {
if (chisla > chisla) {
swap (chisla, chisla);
sort_or_not = false;
}
}
right—;
for (int i = right; i >= left; i—) {
if (chisla < chisla) {
swap (chisla, chisla);
sort_or_not = false;
}
}
left++;
} while (sort_or_not == false);
|
1 |
boolsort_or_not=true; intright=n-1;// n — размер массива intleft=1; do{ boolsort_or_not=true; for(inti=left;i<=right;i++){ if(chislai-1>chislai){ swap(chislai-1,chislai); sort_or_not=false; } } right—; for(inti=right;i>=left;i—){ if(chislai<chislai-1){ swap(chislai,chislai-1); sort_or_not=false; } } left++; }while(sort_or_not==false); |
Пример работы алгоритма[править | править код]
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Наглядная демонстрация алгоритма.
Первый проход:
- (5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
- (1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5>4{\displaystyle 5>4}
- (1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5>2{\displaystyle 5>2}
- (1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8>5{\displaystyle 8>5}), алгоритм не меняет их местами.
Второй проход:
- (1 4 2 5 8) (1 4 2 5 8)
- (1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4>2{\displaystyle 4>2}
- (1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритму это неизвестно. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
- (1 2 4 5 8) (1 2 4 5 8)
- (1 2 4 5 8) (1 2 4 5 8)
Теперь массив отсортирован и алгоритм может быть завершён.
Метод Хоара — Быстрая сортировка(Quick-sort)
- Подробности
- Категория: Сортировка и поиск
Быстрая сортировка (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
| Худшее время |
O(n2) |
|---|---|
| Лучшее время |
O(n log n) (обычное разделение) или O(n) (разделение на 3 части) |
| Среднее время |
O(n log n) |
| Затраты памяти |
O(n) вспомогательных O(log n) вспомогательных |
Реализация алгоритма на различных языках программирования:
Использовать
Пузырьковая сортировка. Список был построен в декартовой системе координат, где каждая точка ( x , y ) указывает, что значение y хранится в индексе x . Затем список будет отсортирован пузырьковой сортировкой по значению каждого пикселя
Обратите внимание, что сначала сортируется самый большой конец, а меньшим элементам требуется больше времени, чтобы переместиться в правильное положение.
Хотя пузырьковая сортировка является одним из самых простых алгоритмов сортировки для понимания и реализации, ее сложность O ( n 2 ) означает, что ее эффективность резко снижается в списках, состоящих из более чем небольшого числа элементов. Даже среди простых алгоритмов сортировки O ( n 2 ) такие алгоритмы, как сортировка вставкой , обычно значительно более эффективны.
Из-за своей простоты пузырьковая сортировка часто используется для знакомства с концепцией алгоритма или алгоритма сортировки для начинающих студентов- информатиков . Тем не менее, некоторые исследователи, такие как Оуэн Астрахан , пошли на многое, чтобы осудить пузырьковую сортировку и ее неизменную популярность в образовании по информатике, рекомендуя даже не преподавать ее.
Жаргон Файл , который лихо звонков bogosort «архетипический извращенно ужасный алгоритм», также вызывает пузырьковую сортировку «общий плохой алгоритм». Дональд Кнут в своей книге «Искусство компьютерного программирования» пришел к выводу, что «пузырьковая сортировка, кажется, не имеет ничего, что могло бы ее рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает.
Пузырьковая сортировка асимптотически эквивалентна по времени работы сортировке вставкой в худшем случае, но эти два алгоритма сильно различаются по количеству необходимых перестановок. Экспериментальные результаты, такие как результаты Astrachan, также показали, что сортировка вставкой работает значительно лучше даже в случайных списках. По этим причинам многие современные учебники алгоритмов избегают использования алгоритма пузырьковой сортировки в пользу сортировки вставкой.
Пузырьковая сортировка также плохо взаимодействует с современным аппаратным обеспечением ЦП. Он производит как минимум вдвое больше записей, чем сортировка вставкой, вдвое больше промахов в кеш и асимптотически больше ошибочных прогнозов переходов . Эксперименты с сортировкой строк Astrachan в Java показывают, что пузырьковая сортировка примерно в пять раз быстрее сортировки вставкой и на 70% быстрее сортировки по выбору .
В компьютерной графике пузырьковая сортировка популярна благодаря своей способности обнаруживать очень маленькие ошибки (например, перестановку всего двух элементов) в почти отсортированных массивах и исправлять их с линейной сложностью (2 n ). Например, он используется в алгоритме заполнения многоугольника, где ограничивающие линии сортируются по их координате x в определенной строке сканирования (линия, параллельная оси x ), а с увеличением y их порядок изменяется (два элемента меняются местами) только в пересечения двух линий. Пузырьковая сортировка — это стабильный алгоритм сортировки, как и сортировка вставкой.
Использовать
Пузырьковая сортировка. Список был построен в декартовой системе координат, где каждая точка ( x , y ) указывает, что значение y хранится в индексе x . Затем список будет отсортирован пузырьковой сортировкой по значению каждого пикселя
Обратите внимание, что сначала сортируется самый большой конец, а меньшим элементам требуется больше времени, чтобы переместиться в правильное положение.
Хотя пузырьковая сортировка является одним из простейших алгоритмов сортировки для понимания и реализации, ее сложность O ( n 2 ) означает, что ее эффективность резко снижается в списках из более чем небольшого числа элементов. Даже среди простых алгоритмов сортировки O ( n 2 ) такие алгоритмы, как сортировка вставкой , обычно значительно более эффективны.
Из-за своей простоты пузырьковая сортировка часто используется для ознакомления с концепцией алгоритма или алгоритма сортировки для начинающих студентов- информатиков . Тем не менее, некоторые исследователи, такие как Оуэн Астрахан , пошли на многое, чтобы осудить пузырьковую сортировку и ее неизменную популярность в образовании по информатике, рекомендуя даже не преподавать ее.
Жаргон Файл , который лихо звонков bogosort «архетипический извращенно ужасный алгоритм», также вызывает пузырьковую сортировку «общий плохой алгоритм». Дональд Кнут в своей книге «Искусство компьютерного программирования» пришел к выводу, что «пузырьковая сортировка, кажется, не имеет ничего, что могло бы ее рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает.
Пузырьковая сортировка асимптотически эквивалентна по времени работы сортировке вставкой в худшем случае, но эти два алгоритма сильно различаются по количеству необходимых перестановок. Экспериментальные результаты, такие как результаты Astrachan, также показали, что сортировка вставкой работает значительно лучше даже в случайных списках. По этим причинам многие современные учебники алгоритмов избегают использования алгоритма пузырьковой сортировки в пользу сортировки вставкой.
Пузырьковая сортировка также плохо взаимодействует с современным аппаратным обеспечением ЦП. Он производит как минимум вдвое больше записей, чем сортировка вставкой, вдвое больше промахов в кеш и асимптотически больше ошибочных прогнозов переходов . Эксперименты с сортировкой строк Astrachan в Java показывают, что пузырьковая сортировка примерно в пять раз быстрее сортировки вставкой и на 70% быстрее сортировки по выбору .
В компьютерной графике пузырьковая сортировка популярна благодаря своей способности обнаруживать очень маленькую ошибку (например, замену всего двух элементов) в почти отсортированных массивах и исправлять ее с линейной сложностью (2 n ). Например, он используется в алгоритме заполнения многоугольника, где ограничивающие линии сортируются по их координате x в определенной строке сканирования (линия, параллельная оси x ), а с увеличением y их порядок изменяется (два элемента меняются местами) только при пересечения двух линий. Пузырьковая сортировка — это стабильный алгоритм сортировки, как и сортировка вставкой.
Реализация
Реализация псевдокода
В псевдокоде алгоритм может быть выражен как (массив на основе 0):
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if this pair is out of order */
if Ai-1 > Ai then
/* swap them and remember something changed */
swap(Ai-1, Ai])
swapped := true
end if
end for
until not swapped
end procedure
Оптимизация пузырьковой сортировки
Алгоритм пузырьковой сортировки можно оптимизировать, наблюдая, что n -й проход находит n-й по величине элемент и помещает его на свое последнее место. Таким образом, внутренний цикл может избежать просмотра последних n — 1 элементов при запуске в n -й раз:
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n - 1 inclusive do
if Ai - 1 > Ai then
swap(Ai - 1, Ai])
swapped := true
end if
end for
n := n - 1
until not swapped
end procedure
В более общем случае может случиться так, что более чем один элемент помещается в свое окончательное положение за один проход. В частности, после каждого прохода все элементы после последнего свопа сортируются и не нуждаются в повторной проверке. Это позволяет пропускать многие элементы, что в худшем случае приводит к увеличению количества сравнений примерно на 50% (хотя и без улучшения подсчетов подкачки), и добавляет очень небольшую сложность, потому что новый код включает переменную «подкачки»:
Для этого в псевдокоде можно записать следующее:
procedure bubbleSort(A list of sortable items)
n := length(A)
repeat
newn :=
for i := 1 to n - 1 inclusive do
if Ai - 1 > Ai then
swap(Ai - 1, Ai])
newn := i
end if
end for
n := newn
until n ≤ 1
end procedure
Альтернативные модификации, такие как сортировка с помощью шейкера для коктейлей, пытаются улучшить производительность пузырьковой сортировки, сохраняя при этом ту же идею многократного сравнения и замены соседних элементов.
Подробный разбор пузырьковой сортировки
Давайте разберем подробно как работает пузырьковая сортировка
Первая итереация (первый повтор алгоритма) меняет между собой 4 и 2 так как цифра два меньше чем четыре 2<4, повторюсь что алгоритм меняет значения между собой если, слева оно меньше чем справа. Далее происходит сверка между 4 и 3, и так как 3 меньше чем 4 (3<4) происходит обмен значениями. Потом проходит проверку между 4 и 8 и так как значение 4 меньше чем 8 то не происходит обмена, ведь уже и так всё на своих местах.
Далее сравнивается 8 и 1 и так как 1 меньше чем 8 (1<8) и оно не находиться слева то происходит обмен значениями.После это первый повтор алгоритма заканчивается, на анимации я выделил это зеленым фоном.
В итоге по окончанию работы алгоритма пузырьковой сортировки мы имеем следующий порядок числового массива: 2 3 4 1 8
и начинается второй повтор алгоритма.
Далее сравнивается 2 и 3 и так как два меньше чем три и оно находиться слева то просто идем дальше ничего не трогая. Также проверяем и 3 и 4 и тоже самое условие выполняется 3<4 и оно слева. Дальше проверяется 4 и 1 и тут мы видим что число 1<4 и не находиться слева, поэтому алгоритм меняет их местами. В крайний раз для второго повторения алгоритма проверяется 4 и 8, но тут всё в порядке, и мы дошли до конца начинаем третье повторение. Итоги для второго повторения такие : 2 3 1 4 8
Третье повторение пузырькового алгоритма начинается с сравнения 2 и 3, тут алгоритм проверяет что 2<3 и 2 находиться слева и оставляет их в покое и идет дальше. Сравнение же 3 и 1 показывает что 1 то меньше чем три, но почему то не слева и меняет их местами. Далее идет сравнение 3 и 4, тут всё в порядке и так далее до сравнения 4 и 8.
После этого получается следующий результат: 2 1 3 4 8
Как мы видим почти все цифры уже на своих местах и в порядке возрастания! Осталось только в последнем повторении пузырькового алгоритма поменять местами 2 и 1 и всё. После того как алгоритм закончил свою работу и проверил что цифры больше нельзя поменять местами он перестает работать с таким вот результатом: 1 2 3 4 8
Turbo Basic 1.1
DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
J=HIGH
X=Y[(LOW+HIGH)/2]
DO
WHILE Y<X:I=I+1:WEND
WHILE Y>X:J=J-1:WEND
IF I<=J THEN
TEMP=Y
Y=Y
Y=TEMP
I=I+1
J=J-1
END IF
LOOP WHILE I<=J
IF LOW<J THEN F=FN QSORT(LOW,J)
IF I<HIGH THEN F=FN QSORT(I,HIGH)
FN QSORT=TRUE
END DEF
Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y
LOW=N1 HIGH=N2 F=FN QSORT(LOW,HIGH)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет :
Youtube
Сортировка пузырьком
Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
3 нарушает порядок, меняем местами с 7
Возвращаемся к началу массива и проделываем то же самое
void bubbleSort(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j < size; j++) {
if (a > a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
После того, как были поменяны местами элемента a и a нет больше необходимости проходить этот участок массива
Примем это во внимание и переделаем алгоритм
void bubbleSort2(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = i; j > 0; j--) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
Ещё одна реализация
void bubbleSort2b(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j <= size-i; j++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
}
}
}
}
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
void bubbleSort3(int *a, size_t size) {
size_t i;
int tmp;
char flag;
do {
flag = 0;
for (i = 1; i < size; i++) {
if (a < a) {
tmp = a;
a = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
int intSort(const void *a, const void *b) {
return *((int*)a) > *((int*)b);
}
void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
char flag;
tmp = malloc(item);
do {
flag = 0;
for (i = 1; i < size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
void *prev, *cur;
char flag;
tmp = malloc(item);
do {
flag = 0;
i = 1;
prev = (char*)a;
cur = (char*)prev + item;
while (i < size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Теперь с помощью этих функций можно сортировать массивы любого типа, например
void main() {
int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5};
int i;
bubbleSort3gi(a, sizeof(int), 10, intSort);
for (i = 0; i < 10; i++) {
printf("%d ", a);
}
_getch();
}
Реализация [ править ]
Реализация псевдокода
В псевдокоде алгоритм может быть выражен как (массив на основе 0):
Процедура BubbleSort ( список из сортируемых элементов ) п : = длина ( ) повтор местами : = ложь для I : = 1 до п - 1 включительно Do / * если эта пара находится вне от порядка * / если я - 1 > A i затем / * поменять местами
их и запомнить, что что-то изменилось * /
swap ( A i - 1 , A i ])
swapped : = true
end if
end for
пока не поменяно местами
end procedure
Оптимизация пузырьковой сортировки
Алгоритм пузырьковой сортировки можно оптимизировать, наблюдая, что n -й проход находит n-й по величине элемент и помещает его на свое последнее место. Таким образом, внутренний цикл может избежать просмотра последних n — 1 элементов при запуске в n -й раз:
Процедура BubbleSort ( список из сортируемых элементов ) п : = длина ( ) повтор местами : = ложь для I : = 1 до п - 1 включительно делать , если я - 1 > я ] , то подкачки ( i - 1 , A i ])
swapped = true
end if
end for
n : = n - 1,
пока не будет заменен
конец процедуры
В более общем случае может случиться так, что более чем один элемент помещается в свое окончательное положение за один проход. В частности, после каждого прохода все элементы после последнего свопа сортируются и не нуждаются в повторной проверке. Это позволяет пропускать многие элементы, что в худшем случае приводит к увеличению количества сравнений примерно на 50% (хотя и без улучшения подсчетов подкачки), и добавляет очень небольшую сложность, потому что новый код включает переменную «подкачки»:
Для этого в псевдокоде можно записать следующее:
Процедура BubbleSort ( список из сортируемых элементов ) п : = длина ( ) повтор newn : = для I : = 1 до п - 1 включительно делать , если я - 1 > я ] , то подкачки ( i - 1 , A i ])
newn : = i
end if
end for
n : = newn
пока n ≤ 1
процедура завершения
Альтернативные модификации, такие как сортировка с помощью шейкер для коктейлей, пытаются улучшить производительность пузырьковой сортировки, сохраняя при этом ту же идею многократного сравнения и замены соседних элементов.
Анализ
Пример пузырьковой сортировки. Начиная с начала списка, сравните каждую соседнюю пару, поменяйте их местами, если они не в правильном порядке (последняя меньше первой). После каждой итерации необходимо сравнивать на один элемент меньше (последний), пока не останется больше элементов для сравнения.
Представление
Пузырьковая сортировка имеет наихудший случай и среднюю сложность О ( n 2 ), где n — количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют существенно лучшую сложность в худшем случае или в среднем, часто O ( n log n ). Даже другое О ( п 2 ) алгоритмы сортировки, такие как вставки рода , как правило , не работать быстрее , чем пузырьковой сортировки, а не более сложным. Следовательно, пузырьковая сортировка не является практическим алгоритмом сортировки.
Единственное существенное преимущество пузырьковой сортировки перед большинством других алгоритмов, даже быстрой сортировкой , но не сортировкой вставкой , заключается в том, что в алгоритм встроена способность определять, что список сортируется эффективно. Когда список уже отсортирован (в лучшем случае), сложность пузырьковой сортировки составляет всего O ( n ). Напротив, большинство других алгоритмов, даже с лучшей средней сложностью , выполняют весь процесс сортировки на множестве и, следовательно, являются более сложными. Однако сортировка вставкой не только разделяет это преимущество, но также лучше работает со списком, который существенно отсортирован (имеет небольшое количество инверсий ). Кроме того, если такое поведение желательно, его можно тривиально добавить к любому другому алгоритму, проверив список перед запуском алгоритма.
Следует избегать пузырьковой сортировки. Это не будет эффективно.
Кролики и черепахи
Расстояние и направление, в котором элементы должны перемещаться во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы перемещаются в разных направлениях с разной скоростью. Элемент, который должен двигаться к концу списка, может перемещаться быстро, потому что он может принимать участие в последовательных заменах. Например, самый большой элемент в списке будет выигрывать при каждом обмене, поэтому он перемещается в свою отсортированную позицию на первом проходе, даже если он начинается рядом с началом. С другой стороны, элемент, который должен двигаться к началу списка, не может двигаться быстрее, чем один шаг за проход, поэтому элементы перемещаются к началу очень медленно. Если наименьший элемент находится в конце списка, потребуется n −1 проход, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа о Черепахе и Зайце .
Были предприняты различные попытки уничтожить черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей — это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n 2 ) . Комбинированная сортировка сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам, чтобы сгладить список. Его средняя скорость сопоставима с более быстрыми алгоритмами вроде быстрой сортировки .
Пошаговый пример
Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему числу, используя пузырьковую сортировку. На каждом этапе сравниваются элементы, выделенные жирным шрифтом . Потребуется три прохода;
- Первый проход
- ( 5 1 4 2 8) → ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.
- (1 5 4 2 8) → (1 4 5 2 8), поменять местами, поскольку 5> 4
- (1 4 5 2 8) → (1 4 2 5 8), поменять местами, поскольку 5> 2
- (1 4 2 5 8 ) → (1 4 2 5 8 ). Теперь, поскольку эти элементы уже упорядочены (8> 5), алгоритм не меняет их местами.
- Второй проход
- ( 1 4 2 5 8) → ( 1 4 2 5 8)
- (1 4 2 5 8) → (1 2 4 5 8), поменять местами, поскольку 4> 2
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8 ) → (1 2 4 5 8 )
Теперь массив уже отсортирован, но алгоритм не знает, завершился ли он. Алгоритму требуется один дополнительный полный проход без какой-либо подкачки, чтобы знать, что он отсортирован.
- Третий проход
- ( 1 2 4 5 8) → ( 1 2 4 5 8)
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8) → (1 2 4 5 8)
- (1 2 4 5 8 ) → (1 2 4 5 8 )
