Пузырьковая сортировка
Содержание:
- Анализ
- Сортировка массива методом пузырька- решение на C++
- Реализация пузырьковой сортировки на языке Java
- Программа упорядочения строк в алфавитном порядке[править]
- Common Lisp
- Сложность алгоритма
- Метод пузырька
- C++
- VB.NET
- Сортировка методом пузырька на C#
- Как улучшить пузырьковую сортировку
- Алгоритмы сортировки на собеседовании
- Использовать
- Сортировка пузырьком
- Варианты алгоритма
- Как создать шейкер сортировку в C++
- Сортировка многомерного массива
- Заключение
Анализ
Пример пузырьковой сортировки. Начиная с начала списка, сравните каждую соседнюю пару, поменяйте их местами, если они не в правильном порядке (последняя меньше первой). После каждой итерации необходимо сравнивать на один элемент меньше (последний), пока не останется больше элементов для сравнения.
Представление
Пузырьковая сортировка имеет наихудший случай и среднюю сложность О ( 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 )
Сортировка массива методом пузырька- решение на 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; } |
Реализация пузырьковой сортировки на языке Java
программный код
- создает массив на 5 элементов;
- загружает в него рост мстителей;
- выводит на экран содержимое массива;
- реализует пузырьковую сортировку;
- осуществляет повторный вывод на экран отсортированного массива.
IntelliJ IDE//ссылка на массив
//количество элементов в массиве
//конструктор класса
//создание массива размером max
//при создании массив содержит 0 элементов
//метод вставки элемента в массив
//вставка value в массив a
//размер массива увеличивается
//метод вывода массива в консоль
//вывести в консоль
новой строки»—-Окончание вывода массива—-»
//метод меняет местами пару чисел массива
//во временную переменную помещаем первый элемент
//на место первого ставим второй элемент
//вместо второго элемента пишем первый из временной памяти
//Создаем массив array на 5 элементов
//заполняем массив
//выводим элементы до сортировки
//ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
//снова выводим отсортированный йсписок
- into – метод вставки элементов в массив;
- printer – выводит содержимое массива построчно;
toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов;
и, наконец, главный метод:
bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно:
public
void
bubbleSorter
()
{
//МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
for
(int
out =
elems —
1
;
out >=
1
;
out—
)
{
//Внешний цикл
for
(int
in =
0
;
in //Внутренний цикл
if
(a
>
a
)
//Если порядок элементов нарушен
toSwap
(in,
in +
1
)
;
//вызвать метод, меняющий местами
}
}
}
Внешний счетчик out
правую частьВнутренний счетчик in
большее число
Программа упорядочения строк в алфавитном порядке[править]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define N 100
#define M 30
int main(int argc, char* argv[]) {
char aN];
int n, i;
scanf("%d", &n);
for (i=; i<n; i++)
scanf("%s", &ai]);
qsort(a, n, sizeof(charM]), (int (*)(const void *,const void *)) strcmp);
for (i=; i<n; i++)
printf("%s\n", ai]);
return ;
}
Обратите внимание на сложное приведение типов.
Функция strcmp, объявленная в файле string.h имеет следующий прототип:
int strcmp(const char*, const char*);
То есть функция получает два аргумента — указатели на кусочки памяти, где хранятся элементы типа char,
то есть два массива символов, которые не могут быть изменены внутри функции strcmp (запрет на изменение задается с помощью модификатора const).
В то же время в качестве четвертого элемента функция qsort хотела бы иметь функцию типа
int cmp(const void*, const void*);
В языке Си можно осуществлять приведение типов являющихся типами функции. В данном примере тип
int (*)(const char*, const char*); // функция, получающая два элемента типа 'const char *' и возвращающая элемент типа 'int'
приводится к типу
int (*)(const void*, const void*); // функция, получающая два элемента типа 'const void *' и возвращающая элемент типа 'int'
Common Lisp
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является «честной» — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, «на том же месте». При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует «императивные» макросы Common Lisp’а.
(defun quickSort (array l r)
(let ((i l)
(j r)
(p (svref array (round (+ l r) 2))))
(while (<= i j)
(while (< (svref array i) p) (incf i))
(while (> (svref array j) p) (decf j))
(when (<= i j)
(rotatef (svref array i) (svref array j))
(incf i)
(decf j)))
(if (>= (- j l) 1) (quickSort array l j))
(if (>= (- r i) 1) (quickSort array i r)))
array)
Сложность алгоритма
Сложность алгоритма позволяет дать ему оценку по времени выполнения, то есть определяет его эффективность. Можно выражать сложность по-разному, но чаще всего используется асимптотическая сложность, которая определяет его эффективность при стремлении входных данных к бесконечности.
Точное время выполнения алгоритма не рассматривается, потому что оно зависит слишком от многих факторов: мощность процессора, тип данных массива, используемый язык программирования.
Алгоритм сортировки пузырьком имеет сложность , где – количество элементов массива. Из формулы видно, что сложность сортировки пузырьком квадратично зависит от количества сортируемых элементов. Это значит, что он неэффективен при работе с большими массивами данных.
Следует понимать, что с помощью асимптотической функции нельзя точно вычислить время работы алгоритма. Например, дана последовательность «6 5 4 3 2 1», для её сортировки придется сделать максимальное количество проходов. Такой случай называют наихудшим. Если дана последовательность «3 1 2 4 5», то количество проходов будет минимально, соответственно сортировка пройдет гораздо быстрее. Если же дан уже отсортированный массив, то алгоритму сортировки и вовсе не нужно совершать проходов. Это называется наилучшим случаем.
Метод пузырька
Сортировка пузырьком в основном применяется в учебных проектах. В реальной практике её заменяют более эффективные алгоритмы, однако сортировка пузырьком лежит в основе некоторых из них.
В общем случае алгоритм сортировки пузырьком следующий:
- Сравнить текущий элемент со следующим.
- Если следующий элемент меньше/больше текущего, поменять их местами.
- Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.
В алгоритме используется два цикла: основной и вложенный. В результате одного прохода вложенного цикла наибольший элемент помещается в конец массива, а наименьший смещается на одну позицию ближе к началу.
Внешний цикл в худшем случае совершает N (кол-во элементов) — 1 проходов, то есть внутренний цикл выполняется N-1 раз.
Таким образом, в каждом проходе совершается серия обменов элементов так, что наибольший элемент передвигается в конец массив перед элементом, который переместился туда в прошлой итерации. Процесс происходит до тех пор, пока массив не будет отсортирован.
Если рассмотреть реализацию алгоритма, то можно легко заметить, что время его работы (количество операций) значительно возрастает с увеличением количества элементов сортируемой последовательности.
C++
Быстрая сортировка на основе библиотеки STL.
#include <functional>
#include <algorithm>
#include <iterator>
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
if( first != last ) {
BidirectionalIterator left = first;
BidirectionalIterator right = last;
BidirectionalIterator pivot = left++;
while( left != right ) {
if( cmp( *left, *pivot ) ) {
++left;
} else {
while( (left != --right) && cmp( *pivot, *right ) )
;
std::iter_swap( left, right );
}
}
--left;
std::iter_swap( first, left );
quick_sort( first, left, cmp );
quick_sort( right, last, cmp );
}
}
// для вещественных
int partition (double *a, int p, int r)
{
double x = *(a+r);
int i = p - 1;
int j;
double tmp;
for (j = p; j < r; j++)
{
if (*(a+j) <= x)
{
i++;
tmp = *(a+i);
*(a+i) = *(a+j);
*(a+j) = tmp;
}
}
tmp = *(a+r);
*(a+r) = *(a+i+1);
*(a+i+1) = tmp;
return i + 1;
}
void quicksort (double *a, int p, int r)
{
int q;
if (p < r)
{
q = partition (a, p, r);
quicksort (a, p, q-1);
quicksort (a, q+1, r);
}
}
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
quick_sort( first, last,
std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
);
VB.NET
Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort’ом
Sub Swap(ByRef Val1, ByRef Val2)
Dim Proc
Proc = Val1
Val1 = Val2
Val2 = Proc
End Sub
Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer)
Dim i
Dim piv
Dim store
piv = a(pivot)
Swap(a(right - 1), a(pivot))
store = left
For i = left To right - 2
If a(i) <= piv Then
Swap(a(store), a(i))
store = store + 1
End If
Next
Swap(a(right - 1), a(store))
Return store
End Function
Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Return New System.Random().Next(left, right - 1)
End Function
Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Dim pivot As Integer
If right - left > 1 Then
pivot = getpivot(a, left, right)
pivot = partition(a, left, right, pivot)
quicksort(a, left, pivot)
quicksort(a, pivot + 1, right)
End If
End Sub
Sub qSort(ByVal a() As Integer)
Dim i
Dim ii
For i = 0 To a.Length() - 1
ii = New System.Random().Next(0, a.Length() - 1)
If i <> ii Then
Swap(a(i), a(ii))
End If
Next
quicksort(a, 0, a.Length())
End Sub
Вызов функции:
qSort(имя сортируемого массива)
Сортировка методом пузырька на C#
В данной статье мы рассмотрим сортировку методом пузырька, реализованную на языке C#.
Описание алгоритма:
Идея данной сортировки заключается в попарном сравнении соседних элементов, начиная с нулевого в массиве. Больший элемент при этом в конце первой итерации оказывается на месте последнего элемента массива, и в следующих итерациях мы его уже не сравниваем его с остальными элементами (то есть у нас будет n-1 сравнений). Затем таким же образом мы находим второй по максимальности элемент и ставим его на предпоследнее место, и т. д. После всех итераций получится, что на месте нулевого элемента окажется элемент с наименьшим числовым значением, а на месте последнего – с наибольшим числовым значением. Таким образом у нас как бы “всплывают” элементы от большего к меньшему.
Примечание: можно также реализовать последовательность от меньшего к большему. В коде это лишь замена знака “>” на знак “ 2 9 4 1 0
Так как 7 больше, чем 2, мы меняем эти элементы местами. Получается массив:
2 7 9 4 1 0
Далее мы сравниваем 7 и 9.
2 79 4 1 0
Число 9 больше, чем 7. Значит 7 остаётся на своём месте. Теперь мы будем сравнивать число 9 с остальными числами и, если 9 будет больше, чем соседние с ним числа, то будет меняться местами с ними.
2 7 94 1 0
2 7 4 91 0
2 7 4 1 90
2 7 4 1 0 9
Большего числа, чем 9 в нашем массиве не оказалось, поэтому 9 занимает последний элемент в массиве. На этом первая итерация окончена. Теперь мы найдём следующее число, которое по значению будет меньше 9, но больше остальных чисел. Причём нам незачем больше трогать 9, так как оно уже на своём месте и в любом случае у него самое больше числовое значение. Поэтому количество шагов в итерации у нас уменьшается на 1 (n-1).
Вторая итерация. Мы опять “захватываем” нулевой элемент массива (2) и сравниваем его с соседним.
27 4 1 0 9
Число 2 меньше, чем 7, поэтому они не будут меняться местами, а на следующем шаге будет сравниваться число 7 со следующим соседним элементом.
2 74 1 0 9
2 4 71 0 9
2 4 1 70 9
Отлично, мы нашли второй элемент, и он занимает предпоследнее место в массиве. Вторая итерация окончена. Опять уменьшаем шаги итерации на 1, так как нам не надо больше сравнивать оставшиеся числа с 7.
После второй итерации наш массив выглядит так:
2 4 1 0 7 9
Третья итерация. Повторяем всё точно так же. Начинаем с нулевого элемента и ищем большее значение среди оставшихся чисел.
24 1 0 7 9
2 41 0 7 9
2 1 40 7 9
2 1 0 4 7 9
Третья итерация окончена. Начинаем четвертую и не забываем уменьшить шаги итерации на 1.
21 0 4 7 9
1 20 4 7 9
1 0 2 4 7 9
Осталась последняя итерация и сравнение лишь двух чисел:
10 2 4 7 9
Сортировка окончена. Наш упорядоченный массив теперь выглядит вот так:
0 1 2 4 7 9
Код программы:
Программу будем делать в консоли. Для начала создадим функцию самой сортировки (перед функцией main):
Как улучшить пузырьковую сортировку
Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.
for (int i = 0; i < 10; i++) {
bool flag = true;
for (int j = 0; j < 10 — (i + 1); j++) {
if (digitals > digitals) {
flag = false;
swap (digitals, digitals);
}
}
if (flag) {
break;
}
}
|
1 |
for(inti=;i<10;i++){ boolflag=true; for(intj=;j<10-(i+1);j++){ if(digitalsj>digitalsj+1){ flag=false; swap(digitalsj,digitalsj+1); } } if(flag){ break; } } |
Давайте посмотрим, что мы сделали для ее оптимизации:
- В строке 17: изменили условие внутреннего цикла на .Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 1, после каждого полного прохода внешнего цикла.
- Вы могли заметить, что если даже массив стал отсортирован (или сразу был отсортирован) алгоритм все равно продолжает сравнивать элементы.
Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение , но она меняется на:
false, если результат условия в строке 4: положительный.
А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:
- Если булева переменная равна , значит массив уже полностью отсортирован и можно выйти. Для этого используем оператор .
- Если же значение равно , то продолжаем сортировать массив.
В строке 6: вы (возможно) увидели незнакомую функцию . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки и . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:
int b = digitals;
digitals = digitals;
digitals = b;
|
1 |
intb=digitalsj; digitalsj=digitalsj+1; digitalsj+1=b; |
Использовать ее необязательно, потому что она не сделает код быстрее. Но как мы сказали выше, кода станет меньше.
Алгоритмы сортировки на собеседовании
Алгоритмов сортировки достаточно много, и вряд ли можно встретить программиста, который может по памяти написать реализацию хотя бы половины из них.
На самом деле, программисты просто гуглят необходимую реализацию. Конечно, они имеют представление о принципах их работы, потому что в своё время рассмотрели несколько алгоритмов, как, например, сортировка пузырьком.
Кроме того, в Python и других языках программирования существуют встроенные функции, которые производят сортировку быстро и эффективно.
На собеседованиях спрашивают про алгоритмы сортировки, но это не значит, что от будущего работника требуют написать их реализацию или придумать свой. Работодатель требует от специалиста следующее:
- Уметь классифицировать алгоритмы сортировки.
- Знать преимущества и недостатки популярных алгоритмов, чтобы понимать, когда каждый из них лучше использовать.
- Понимать, что такое сложность алгоритма и как с её помощью определять, подходит ли он для решения данной задачи.
Использовать
Пузырьковая сортировка. Список был построен в декартовой системе координат, где каждая точка ( x , y ) указывает, что значение y хранится в индексе x . Затем список будет отсортирован пузырьковой сортировкой по значению каждого пикселя
Обратите внимание, что сначала сортируется самый большой конец, а меньшим элементам требуется больше времени, чтобы переместиться в правильное положение.
Хотя пузырьковая сортировка является одним из простейших алгоритмов сортировки для понимания и реализации, ее сложность O ( n 2 ) означает, что ее эффективность резко снижается в списках из более чем небольшого числа элементов. Даже среди простых алгоритмов сортировки O ( n 2 ) такие алгоритмы, как сортировка вставкой , обычно значительно более эффективны.
Из-за своей простоты пузырьковая сортировка часто используется для ознакомления с концепцией алгоритма или алгоритма сортировки для начинающих студентов- информатиков . Тем не менее, некоторые исследователи, такие как Оуэн Астрахан , пошли на многое, чтобы осудить пузырьковую сортировку и ее неизменную популярность в образовании по информатике, рекомендуя даже не преподавать ее.
Жаргон Файл , который лихо звонков bogosort «архетипический извращенно ужасный алгоритм», также вызывает пузырьковую сортировку «общий плохой алгоритм». Дональд Кнут в своей книге «Искусство компьютерного программирования» пришел к выводу, что «пузырьковой сортировке, похоже, нечего рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает.
Пузырьковая сортировка асимптотически эквивалентна по времени работы сортировке вставкой в худшем случае, но эти два алгоритма сильно различаются по количеству необходимых перестановок. Экспериментальные результаты, такие как результаты Astrachan, также показали, что сортировка вставкой работает значительно лучше даже в случайных списках. По этим причинам многие современные учебники алгоритмов избегают использования алгоритма пузырьковой сортировки в пользу сортировки вставкой.
Пузырьковая сортировка также плохо взаимодействует с современным аппаратным обеспечением ЦП. Он производит как минимум вдвое больше записей, чем сортировка вставкой, вдвое больше промахов в кеш и асимптотически больше ошибочных прогнозов переходов . Эксперименты с сортировкой строк Astrachan в Java показывают, что пузырьковая сортировка примерно в пять раз быстрее сортировки вставкой и на 70% быстрее сортировки по выбору .
В компьютерной графике пузырьковая сортировка популярна благодаря своей способности обнаруживать очень маленькие ошибки (например, перестановку всего двух элементов) в почти отсортированных массивах и исправлять их с линейной сложностью (2 n ). Например, он используется в алгоритме заполнения многоугольника, где ограничивающие линии сортируются по их координате x в определенной строке сканирования (линия, параллельная оси x ), а с увеличением y их порядок изменяется (два элемента меняются местами) только при пересечения двух линий. Пузырьковая сортировка — это стабильный алгоритм сортировки, как и сортировка вставкой.
Сортировка пузырьком
Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {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();
}
Варианты алгоритма
Сорт коктейлей
Производной пузырьковой сортировки является сортировка коктейлей или шейкерная сортировка. Этот метод сортировки основан на следующем наблюдении: при пузырьковой сортировке элементы могут быстро перемещаться в конец массива, но перемещаются в начало массива только по одной позиции за раз.
Идея сортировки коктейлей состоит в чередовании направления маршрута. Получается несколько более быстрая сортировка, с одной стороны, потому что она требует меньшего количества сравнений, с другой стороны, потому что она перечитывает самые последние данные при изменении направления (поэтому они все еще находятся в кэш-памяти ). Однако количество обменов, которые необходимо произвести, идентично (см. Выше). Таким образом, время выполнения всегда пропорционально n 2 и, следовательно, посредственно.
Три прыжка вниз
Код для этой сортировки очень похож на пузырьковую сортировку. Подобно пузырьковой сортировке, при этой сортировке первыми отображаются самые крупные элементы. Однако это не работает с соседними элементами; он сравнивает каждый элемент массива с тем, который находится на месте большего, и обменивается, когда находит новый, больший.
tri_jump_down(Tableau T)
pour i allant de taille de T - 1 à 1
pour j allant de 0 à i - 1
si T < T
échanger(T, T)
Сортировка combsort
Вариант пузырьковой сортировки, называемый гребенчатой сортировкой ( combsort ), был разработан в 1980 году Влодзимежем Добосевичем и вновь появился в апреле 1991 года в журнале Byte Magazine . Он исправляет главный недостаток пузырьковой сортировки, которой являются «черепахи», и делает алгоритм столь же эффективным, как и быстрая сортировка .
Как создать шейкер сортировку в C++
Ниже вы можете увидеть реализацию шейкер сортировки:
bool sort_or_not = true;
do {
sort_or_not = true;
for (int i = 0; i < n; i++) { // n — размер сортируемого массива
if (chisla > chisla) {
swap (chisla, chisla);
sort_or_not = false;
}
}
for (int i = 4; i >= 1; i—) {
if (chisla < chisla) {
swap (chisla, chisla);
sort_or_not = false;
}
}
} while (sort_or_not == false);
|
1 |
boolsort_or_not=true; do{ sort_or_not=true; for(inti=;i<n;i++){// n — размер сортируемого массива if(chislai>chislai+1){ swap(chislai,chislai+1); sort_or_not=false; } } for(inti=4;i>=1;i—){ if(chislai<chislai-1){ swap(chislai,chislai-1); sort_or_not=false; } } }while(sort_or_not==false); |
Давайте разберем как этот код работает:
С помощью булевой переменной , которую мы создали в первой строчке и сразу же присвоили значение , мы будем узнавать меняли ли ячейки свое значение (за два цикла):
sort_or_not принимает значение false, если результаты условий, которые находятся в строках 6 и 12 равны true.
Весь смысл заключается в том, что в условии цикла do while написано (пока) . Это значит пока меняются значения ячеек между собой, мы заканчивать сортировку не собираемся.
Если же булева переменная за цикл не стала равна , то мы спокойно выходим из цикла.
Внутри цикла вы можете увидеть две поочередно стоящие алгоритмы пузырьковой сортировки, только с разными направлениями сортировки (мы это упомянули выше).
Как видите реализация не такая уж и сложная, как могла показаться в начале. Также этот алгоритм можно сделать быстрее, но об этом ниже.
Сортировка многомерного массива
Сортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.
void main() {
int a = {1, 9, 2, 8, 3, 7, 4, 6, 5};
int i, j;
bubbleSort3gi(a, sizeof(int), 9, intSort);
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a);
}
}
}
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bubbleSort2d(int **a, size_t m, size_t n) {
int tmp;
size_t i, j, k, jp, ip;
size_t size = m*n;
char flag;
do {
flag = 0;
for (k = 1; k < size; k++) {
//Вычисляем индексы текущего элемента
j = k / m;
i = k - j*m;
//Вычисляем индексы предыдущего элемента
jp = (k-1) / m;
ip = (k-1) - jp*m;
if (a > a) {
tmp = a;
a = a;
a = tmp;
flag = 1;
}
}
} while(flag);
}
#define SIZE_X 3
#define SIZE_Y 4
void main() {
int **a = NULL;
int i, j;
a = (int**) malloc(sizeof(int*) * SIZE_X);
for (i = 0; i < SIZE_X; i++) {
a = (int*) malloc(sizeof(int) * SIZE_Y);
for (j = 0; j < SIZE_Y; j++) {
a = rand();
printf("%8d ", a);
}
printf("\n");
}
printf("\nafter sort\n");
bubbleSort2d(a, SIZE_X, SIZE_Y);
for (i = 0; i < SIZE_X; i++) {
for (j = 0; j < SIZE_Y; j++) {
printf("%8d ", a);
}
printf("\n");
}
for (i = 0; i < SIZE_X; i++) {
free(a);
}
free(a);
_getch();
}
Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.
void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) {
size_t size = m*n, sub_size = n*item;
size_t i, j, k;
void *arr = malloc(size * item);
char *p1d = (char*)arr;
char *p2d = (char*)a;
//Копируем двумерный массив типа void в одномерный
for (i = 0; i < m; i++) {
memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size);
}
bubbleSort3gi(arr, item, size, cmp);
//Копируем одномерный массив обратно в двумерный
for (i = 0; i < m; i++) {
memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size);
}
}
Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера
bubbleSort3gi2d((void**)a, sizeof(int), SIZE_X, SIZE_Y, intSort);
Q&A
Всё ещё не понятно? – пиши вопросы на ящик
Заключение
Метод пузырька гораздо менее эффективен других алгоритмов, однако он имеет простую и понятную реализацию, поэтому часто используется в учебных целях. Кроме того, пузырьковая сортировка может использоваться для работы с небольшими массивами данных.
На самом деле, вместо самостоятельного написания алгоритмов сортировки программисты на Python используют стандартные функции и методы языка, такие как и . Эти функции отлажены и работают быстро и эффективно.
Знания особенностей алгоритмов сортировки, их сложности и принципов реализации в общем виде пригодятся каждому программисту, желающему пройти собеседование и стать Python-разработчиком.
