Bubble sorting in java program

Bubble Sort Algorithm in Java: Array Sorting Program & Example

Bubble sort is a simple algorithm that compares the first element of the array to the next one. If the current element of the array is numerically greater than the next one, the elements are swapped. Likewise, the algorithm will traverse the entire element of the array.

In this tutorial, we will create a JAVA program to implement Bubble Sort. Check the output of the code that will help you understand the program logic.

Java Program to Check Armstrong Number

package com.guru99; public class BubbleSort < public static void main(String[] args) < int arr[] =; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr);//sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); > static void bubbleSort(int[] array) < int n = array.length; int temp = 0; for(int i=0; i < n; i++) // Looping through the array length < System.out.println("Sort Pass Number "+(i+1)); for(int j=1; j < (n-i); j++) < System.out.println("Comparing "+ array[j-1]+ " and " + array[j]); if(array[j-1] >array[j]) < //swap elements temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j-1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); >> > > static void printArray(int[] array) < for(int i=0; i < array.length; i++) < System.out.print(array[i] + " "); >System.out.println(); > >

Output:

860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860

Источник

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

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

Введение

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

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

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

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

Done!

• Сравнить два элемента;
• Поменять местами или скопировать один из них;
• Перейти к следующему элементу;

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

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

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

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

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

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

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

• создает массив на 5 элементов;
• загружает в него рост мстителей;
• выводит на экран содержимое массива;
• реализует пузырьковую сортировку;
• осуществляет повторный вывод на экран отсортированного массива.

 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 >= 1; out--) < //Внешний цикл for (int in = 0; in < 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(); //снова выводим отсортированный йсписок >> 

• 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); //вызвать метод, меняющий местами > > > 

Заключение

Алгоритм пузырьковой сортировки является одним из самых медленных. Если массив состоит из 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!

Источник