Пузырьковая сортировка массива. Реализация пузырьковой сортировки на Java. Реализация пузырьковой сортировки на языке Java

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

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

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

Отсортируем массив {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); } }

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

Всем привет!

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

Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:

Плюсы:

• Простота реализации алгоритма
• Красивое название

Минусы:

• Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2)
• Почти не применяется в реальной жизни (используется в основном в учебных целях)

Пусть есть у нас некий массив: 3 1 4 2

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

Вернемся к нашему массиву:3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два - значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился - он всё равно, после прохождения циклом всего массива, будет последним. Аналогия - как пузырёк воздуха всплывает в воде - так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.

Сравниваем "1" и "3" - ничего не меняем.
Сравниваем "3" и "2" - Три больше двух, значит меняем местами. Получается:1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла - значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй - видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.

Теперь осталось запрограммировать данный алгоритм на языке Pascal. const n = 4; {Заводим константу, это будет длина массива} var i, j, k:integer; {Две переменные для вложенного цикла, одна для того чтобы элементы менять местами } m:array of integer; {Заводим массив} begin {Будем запрашивать массив с клавиатуры:} Writeln("Введите массив:"); for i:=1 to n do begin Writeln(i, " элемент:"); Readln(m[i]); end; {Внешний цикл отвечает за то, что мы должны повторить внутренний цикл столько раз, сколько у нас элементов массива минус 1.} for i:=1 to n-1 do begin {Внутренний цикл уже перебирает элементы и сравнивает между собой.} for j:=1 to n-i do begin {Если элемент, больше следующего, то меняем местами.} if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; end; end; end; {Выводи результат:} for i:=1 to n do Write(m[i], " "); end.
Вот результат:

А вот видеоурок

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

Откуда взялось такое необычное название?

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

Описание алгоритма

Сортировка пузырьком выполняется следующим образом:

• первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
• следовательно, попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
• поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений - минус один;
• у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
• подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.

Еще короче алгоритм будущей программы можно записать так:

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

Псевдокод на основе описанного алгоритма

Самая простая реализация выполняется так:

Процедура Sortirovka_Puzirkom ;

Начало

цикл для j от nachalnii_index до konechii_index ;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv

(меняем значения местами);

Конец

Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету).

Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:

Процедура Sortirovka_Puzirkom ;

Начало

sortirovka = истина;

цикл пока sortirovka = истина;

sortirovka = ложь;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv (первый элемент больше второго), то:

(меняем элементы местами);

sortirovka = истина; (обозначили, что обмен был произведен).

Конец.

Недостатки метода

Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком?

Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален.

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

Кроме того, эффективен метод сортировки простыми обменами, как его еще называют, только для массивов небольшого размера. Большие объемы данных с его помощью обработать не получится: результатом станут либо ошибки, либо сбой работы программы.

Достоинства

Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Сортировка пузырьком идеально подходит для начинающих.

По причине недостатков алгоритм не применяют во внеучебных целях.

Наглядный принцип сортировки

Изначальный вид массива 8 22 4 74 44 37 1 7

Шаг 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Шаг 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Шаг 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Шаг 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Шаг 7 1 4 7 8 22 37 44 74

Пример сортировки пузырьком на языке Pascal

Пример:

const kol_mas=10;

var massiv:array of integer;

a, b, k: integer;

writeln ("input", kol_mas, "elements of array");

for a:=1 to kol_mas do readln(massiv[a]);

for a:=1 to kol_mas-1 do begin

for b:=a+1 to kol_mas do begin

if massiv[a]>massiv[b] then begin

k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;

end;

writeln ("after sort");

for a:=1 to kol_mas do writeln(massiv[a]);

Пример сортировки пузырьком на языке С (Си)

#include

#include

int main(int argc, char* argv)

int massiv = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;

for (; ;){

ff = 0;

for (i = 7; i>0; i--){

if (massiv[i] < massiv) {

swap (massiv[i],massiv);

if (ff == 0) break;

getch(); // задержка экрана

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

Решение

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

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

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

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 .