Введение в Bubble Sort в Java

Bubble sort - один из наиболее часто используемых алгоритмов сортировки данных в Java. Сортировка здесь выполняется путем рекурсивного сравнения соседних чисел и смещения их в порядке возрастания или убывания по мере необходимости. Это смещение элементов выполняется до тех пор, пока все цифры не будут полностью отсортированы в требуемом порядке.

Название «Bubble sort» этого алгоритма объясняется тем, что элементы массива пузыриваются к его началу. Давайте разберемся с алгоритмом сортировки пузырьков на примере.

Пример: рассмотрим массив чисел (6 1 8 5 3), которые необходимо расположить в порядке возрастания.

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

Итерации

Ниже приведены итерации, выполняемые в Bubble Sort на Java, которые выглядят следующим образом:

Первая итерация

(6 1 8 5 3) - Он начинается со сравнения первых двух чисел и сдвигает меньшее число из двух вправо. Следовательно, среди 6 и 1, 1 - меньшее число, смещенное влево, а 6 - вправо.

(1 6 8 5 3) - Затем он сравнивает два соседних числа, сдвигая одну позицию вправо. Здесь число 6 меньше 8 и, следовательно, сохраняется тот же порядок.

(1 6 8 5 3) - Снова при смещении на одну позицию вправо происходит сравнение между 8 и 5. Число 5 смещается влево, так как оно меньше 8.

(1 6 5 8 3) - Здесь проводится сравнение между номерами 8 и 3. Число 3 смещено влево, поскольку оно меньше 8.

(1 6 5 3 8) - это окончательный результат заказа после 1-й итерации.

Вторая итерация

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

(1 6 5 3 8) - Здесь сравнение снова начинается с первых двух цифр результата первой итерации. Он сравнивает числа 1 и 6 и сохраняет тот же порядок, поскольку 1 меньше 6.

(1 6 5 3 8) - Здесь сравниваются цифры 5 и 6. Тот же порядок сохраняется, поскольку он уже находится в требуемом порядке возрастания.

(1 5 6 3 8) - Здесь сравнение проводится между номерами 6 и 3. Число 3 смещено влево, так как оно меньше 6.

(1 5 3 6 8) - Следующие числа 6 и 8 сравниваются друг с другом. Сохраняется тот же порядок, что и в ожидаемом порядке.

(1 5 3 6 8) - это окончательный результат после второй итерации. Тем не менее, мы можем заметить, что цифры не полностью расположены в порядке их возрастания. Тем не менее нам нужно обменять номера 5 и 3, чтобы получить окончательный результат. Следовательно, программа идет на третью итерацию.

Третья итерация

(1 5 3 6 8) - Третья итерация начинается со сравнения первых двух цифр 1 и 5. Поскольку порядок соответствует ожидаемому, он сохраняется прежним.

(1 5 3 6 8) - Далее сравниваются соседние числа 3 и 5. Поскольку 5 больше 3, оно смещено вправо.

(1 3 5 6 8) - итерация продолжается для сравнения чисел 5 и 6, 6 и 8. Поскольку она находится в требуемом порядке, она сохраняет порядок.

(1 3 5 6 8) - Наконец, итерация останавливается, когда программа пересекает сравнение каждого смежного элемента и обнаруживает, что все цифры расположены в порядке возрастания.

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

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

Ниже приведен код Java, который является реализацией алгоритма сортировки Bubble. (Обратите внимание, что первая позиция массива в Java начинается с 0 и продолжается с шагом 1, то есть массив (0), массив (1), массив (2) и продолжается).

Код:

import java.util.Scanner;
public class BubbleSort (
static void bubbleSort(int() arraytest) (
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++)( // first for loop performs multiple iterations
for(int j=1; j < (ni); j++)(
if(arraytest(j-1) > arraytest(j))( // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest(j-1); // assigns the greater number to temp variable
arraytest(j-1) = arraytest(j); // shifts the lesser number to the previous position
arraytest(j) = temp; // bigger number is then assigned to the right hand side
)
)
)
)
public static void main(String() args) (
int arraytest() =(23, 16, 3, 42, 75, 536, 61); // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)( // for loop used to print the values of array
System.out.print(arraytest(i) + " ");
)
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)(
System.out.print(arraytest(i) + " "); // for loop to print output values from array
)
)
)

Выход:

Преимущества и недостатки Bubble Sort в Java

Ниже приведены различные преимущества и недостатки пузырьковой сортировки в Java:

преимущества

  1. Код очень легко написать и понять. Обычно это занимает всего несколько минут.
  2. Реализация также очень проста.
  3. Пузырьковая сортировка сортирует числа и сохраняет их в памяти, следовательно, экономит много памяти.

Недостатки

  1. Этот алгоритм не подходит для больших наборов данных, так как сравнение занимает много времени. Время, необходимое для сортировки входных чисел, увеличивается в геометрической прогрессии.
  2. O (n 2) - средняя сложность Bubble sort, а O (n) - наилучшая сложность (лучший случай, когда элементы сортируются в первую очередь), где n - количество элементов.

Приложения в реальном времени

Поскольку Bubble sort способен обнаруживать мелкие ошибки при сортировке, он используется в компьютерной графике. Он также используется в алгоритме заполнения многоугольника, где необходимо отсортировать выравнивание вершин многоугольника.

Вывод

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

Рекомендуемые статьи

Это руководство по Bubble Sort на Java. Здесь мы обсуждаем несколько итераций для выполнения пузырьковой сортировки в Java и ее реализации кода, а также преимущества и недостатки. Вы также можете посмотреть следующие статьи, чтобы узнать больше -

  1. Пузырьковая сортировка в JavaScript
  2. Сортировка в R
  3. 3D-массивы в Java
  4. Массивы в C #
  5. Bubble Sort in Python

Категория:

Разработка программного обеспечения