Главная · Интернет · Метод пузырьковой сортировки. Реализация пузырьковой сортировки на Java. Реализация пузырьковой сортировки на языке Java

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

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

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

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

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

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

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

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

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

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

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

Процедура 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 .

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

Введение

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

Сортировка глазами машины и глазами человека

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

Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:

Done!

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

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

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

После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:

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

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

Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки: Визуализация работы пузырьковой сортировки

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

Для демонстрации работы сортировки на Java, приведем программный код, который:
  • создает массив на 5 элементов;
  • загружает в него рост мстителей;
  • выводит на экран содержимое массива;
  • реализует пузырьковую сортировку;
  • осуществляет повторный вывод на экран отсортированного массива.
С кодом можно ознакомиться ниже, и даже загрузить его в свою любимую IntelliJ IDE. Его разбор будет производиться ниже: class ArrayBubble { private long a; //ссылка на массив private int elems; //количество элементов в массиве public ArrayBubble (int max) { //конструктор класса a = new long [ max] ; //создание массива размером max elems = 0 ; //при создании массив содержит 0 элементов } public void into (long value) { //метод вставки элемента в массив a[ elems] = value; //вставка value в массив a elems++ ; //размер массива увеличивается } public void printer () { //метод вывода массива в консоль for (int i = 0 ; i elems; i++ ) { //для каждого элемента в массиве System. out. print (a[ i] + " " ) ; //вывести в консоль System. out. println ("" ) ; //с новой строки } System. out. println ("----Окончание вывода массива----" ) ; } private void toSwap (int first, int second) { //метод меняет местами пару чисел массива long dummy = a[ first] ; //во временную переменную помещаем первый элемент a[ first] = a[ second] ; //на место первого ставим второй элемент a[ second] = dummy; //вместо второго элемента пишем первый из временной памяти } public void bubbleSorter () { for (int out = elems - 1 ; out >; in++ ) { //Внутренний цикл if (a[ in] > a[ in + 1 ] ) toSwap (in, in + 1 ) ; } } } } public class Main { public static void main (String args) { ArrayBubble array = new ArrayBubble (5 ) ; //Создаем массив array на 5 элементов array. into (163 ) ; //заполняем массив array. into (300 ) ; array. into (184 ) ; array. into (191 ) ; array. into (174 ) ; array. printer () ; //выводим элементы до сортировки array. bubbleSorter () ; //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ array. printer () ; //снова выводим отсортированный йсписок } } Не смотря на подробные комментарии в коде, приведем описание некоторых методов, представленных в программе. Ключевые методы, осуществляющую основную работу в программе написаны в классе ArrayBubble. Класс содержит конструктор и несколько методов:
  • into – метод вставки элементов в массив;
  • printer – выводит содержимое массива построчно;

    • toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов;

    и, наконец, главный метод:

  • bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно:

    public void bubbleSorter () { //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ for (int out = elems - 1 ; out >= 1 ; out-- ) { //Внешний цикл for (int in = 0 ; in out; in++ ) { //Внутренний цикл if (a[ in] > a[ in + 1 ] ) //Если порядок элементов нарушен toSwap (in, in + 1 ) ; //вызвать метод, меняющий местами } } }
Здесь следует обратить внимание на два счетчика: внешний out , и внутренний in . Внешний счетчик out начинает перебор значений с конца массива и постепенно уменьшается с каждым новым проходом на единицу. Переменная out с каждым новым проходом смещается все левее, чтобы не затрагивать значения, уже отсортированные в правую часть массива. Внутренний счетчик in начинает перебор значений с начала массива и постепенно увеличивается на единицу на каждом новом проходе. Увеличение in происходит до тех пока, пока он не достигнет out (последнего анализируемого элемента в текущем проходе). Внутренний цикл in производит сравнение двух соседних ячеек in и in+1 . Если в in хранится большее число, чем в in+1 , то вызывается метод toSwap , который меняет местами эти два числа.

Заключение

Алгоритм пузырьковой сортировки является одним из самых медленных. Если массив состоит из N элементов, то на первом проходе будет выполнено N-1 сравнений, на втором N-2, далее N-3 и т.д. То есть всего будет произведено проходов: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Таким образом, при сортировке алгоритм выполняет около 0.5х(N^2) сравнений. Для N = 5 , количество сравнений будет примерно 10, для N = 10 количество сравнений вырастит до 45. Таким образом, с увеличением количества элементов сложность сортировки значительно увеличивается:

На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке. Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов. Jgd!



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

Сортировка простыми обменами , сортиро́вка пузырько́м (англ. 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 ; } }

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

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

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

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

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