Метод сортировки пузырьком c описание. Пузырьковая сортировка и все-все-все. Усовершенствованный алгоритм сортировки пузырьком в Pascal

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

Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 7 чисел (см. Таблица 1).
исходный массив: 3 3 7 1 2 5 0

Для того чтобы отсортировать массив хватило пяти запусков внутреннего цикла, for . Запустившись, цикл for срабатывал 6 раз, так как элементов в массиве 7, то итераций (повторений) цикла for должно быть на одно меньше. На каждой итерации сравниваются два соседних элемента массива. Если текущий элемент массива больше следующего, то меняем их местами. Таким образом, пока массив не будет отсортирован, будет запускаться внутренний цикл и выполняться операция сравнения. Обратите внимание на то, что за каждое полное выполнение цикла for как минимум один элемент массива находит своё место. В худшем случае, понадобится n-2 запуска внутреннего цикла, где n – количество элементов массива. Это говорит о том, что сортировка пузырьком крайне не эффективна для больших массивов.

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

// bu_sort.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include #include #include using namespace std; void bubbleSort(int *, int); // прототип функции сортировки пузырьком int main(int argc, char* argv) { srand(time(NULL)); setlocale(LC_ALL, "rus"); cout << "Введите размер массива: "; int size_array; // длинна массива cin >> size_array; int *sorted_array = new int ; // одномерный динамический массив for (int counter = 0; counter < size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; system("pause"); return 0; } void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком { int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован { exit = true; for (int int_counter = 0; int_counter < (length_array - 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию - знак > //сортировка пузырьком по убыванию - знак < if (arrayPtr > arrayPtr) // сравниваем два соседних элемента { // выполняем перестановку элементов массива temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = temp; exit = false; // на очередной итерации была произведена перестановка элементов } } }

Результат работы программы показан на рисунке 1.

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

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

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

Template void bubbleSort(T a, long size) { long i, j; T x; for(i=0; i < size; i++) { // i - номер прохода for(j = size-1; j > i; j--) { // внутренний цикл прохода if (a > a[j]) { x=a; a=a[j]; a[j]=x; } } } }

Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n 2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит?

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

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой ".

Template void shakerSort(T a, long size) { long j, k = size-1; long lb=1, ub = size-1; // границы неотсортированной части массива T x; do { // проход снизу вверх for(j=ub; j>0; j--) { if (a > a[j]) { x=a; a=a[j]; a[j]=x; k=j; } } lb = k+1; // проход сверху вниз for (j=1; j<=ub; j++) { if (a > a[j]) { x=a; a=a[j]; a[j]=x; k=j; } } ub = k-1; } while (lb < ub); }

Насколько описанные изменения повлияли на эффективность метода? Среднее количество сравнений, хоть и уменьшилось, но остается O(n 2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.

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

Решение

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька , который также называют методом простого обмена . В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Алгоритм и особенности этой сортировки таковы:

1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const m = 10 ; var arr: array [ 1 .. m ] of integer ; i, j, k: integer ; begin randomize; write ("Исходный массив: " ) ; for i : = 1 to m do begin arr[ i] : = random(256 ) ; write (arr[ i] : 4 ) ; end ; writeln ; writeln ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; write ("Отсортированный массив: " ) ; for i : = 1 to m do write (arr[ i] : 4 ) ; writeln ; readln end .

Теги: Сортировка пузырьком си, си пузырьковая сортировка, сортировка пузырьком двумерного массива

Сортировка пузырьком

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

Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 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[j] > a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Этот алгоритм всегда будет делать (n-1) 2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1) 2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.

Пусть нужно отсортировать массив 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

После того, как были поменяны местами элемента 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[j] < a) { tmp = a[j]; a[j] = 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[j] < a) { tmp = a[j]; a[j] = 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[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

В этом случае сложность также порядка n 2 , но в случае отсортированного массива будет всего один проход.

Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа 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[i]); } _getch(); }

Сортировка многомерного массива

С ортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.

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[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #include #include #include 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[i][j] > a) { tmp = a[i][j]; a[i][j] = 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[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } 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[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } 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); } }

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

Метод пузырька

Сортировка простыми обменами , сортиро́вка пузырько́м (англ. bubble sort ) - простой алгоритм сортировки . Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n ²).

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками .

Алгоритм

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

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка .

Примеры реализации

Python

Def swap(arr, i, j) : arr[ i] , arr[ j] = arr[ j] , arr[ i] def bubble_sort(arr) : i = len (arr) while i > 1 : for j in xrange (i - 1 ) : if arr[ j] > arr[ j + 1 ] : swap(arr, j, j + 1 ) i -= 1

VBA

Sub Sort(Mus() As Long ) Dim n As Long , i As Long , tmp As Long i = 1 Do While (i < UBound (Mus) ) If Mus(i) > Mus(i + 1 ) Then tmp = Mus(i) Mus(i) = Mus(i + 1 ) Mus(i + 1 ) = tmp If i > 1 Then i = i - 1 Else i = i + 1 End If Else i = i + 1 End If Loop End Sub

Усовершенствованный алгоритм сортировки пузырьком в Pascal

P:=True ; {Перестановка есть} K:=1 ; {Номер просмотра} While P Do Begin P:=false ; For i:=1 To n-k Do If X[ i] > X[ i+1 ] Then Begin A:=X[ i] ; X[ i] :=X[ i+1 ] ; X[ i+1 ] :=A; P:=true ; End ; k:=k+1 ; End ;

PHP

$size = count ($arr ) -1 ; for ($i = $size ; $i >=0 ; $i --) { for ($j = 0 ; $j <=($i -1 ) ; $j ++) if ($arr [ $j ] >$arr [ $j +1 ] ) { $k = $arr [ $j ] ; $arr [ $j ] = $arr [ $j +1 ] ; $arr [ $j +1 ] = $k ; } }