Пузырьковая сортировка — Bubble Sort. Алгоритмы сортировок.

Алгоритмы сортировок, Bubble Sort — введение в Java 027 #

массив требующий сортировки

массив требующий сортировки

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

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

Пузырьковая сортировка #

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

Названа сортировка так потому, что цифры “всплывают” меняясь местами.

Пузырьковая сортировка или Bubble sort

Пузырьковая сортировка или Bubble sort

Bubble Sort и рекурсия #

import java.util.Arrays;

public class BubbleSort {
	static void bubbleSort(int[] arrUnsort) {
		int count = 0;
		for (int i = 0; i < arrUnsort.length - 1; i++)
			if (arrUnsort[i] > arrUnsort[i + 1]) {
				int temp = arrUnsort[i];
				arrUnsort[i] = arrUnsort[i + 1];
				arrUnsort[i + 1] = temp;
				count++;
			}
		if (count > 0) {
			bubbleSort(arrUnsort);
		}
	}

	public static void main(String[] args) {
		int[] myArr = {104, 64, 34, 25, 12, 22, 11, 90};
		bubbleSort(myArr);
		System.out.println(Arrays.toString(myArr));
	}
}

Bubble Sort без рекурсии #

public static void bubbleSort(int[] array) {
    boolean unsorted = true;
    int temp;
    while (unsorted) {
        unsorted = false;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                unsorted = true;
            }
        }
    }
}

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

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String name = "Andrej";
        String[] array = name.split("");
        System.out.println(Arrays.toString(bubbleSort(array)));
    }

    public static String[] bubbleSort(String[] array) {
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1].toLowerCase().compareTo(array[i].toLowerCase()) < 0) {
                String tempStr = array[i];
                array[i] = array[i + 1];
                array[i + 1] = tempStr;
                count++;
            }
        }
        if (count > 0) {
            bubbleSort(array);
        }
        return array;
    }
}

Рекурсия #

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

Рекурсия - определение метода через саму себя.

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

  1. Рекурсия, 17-yj урок
  2. Домашнее задание и закрепление материала - рекурсия. Занимательные задачки
  3. Как работает рекурсия – объяснение в блок-схемах и видео
  4. Просто для ознакомления - рекурсивное программирование

Дополнительные материалы к пузырьковой сортировке #

  1. Пузырьковая сортировка и все-все-все
  2. Очень важный материал для самостоятельного изучения - двоичное дерево поиска
  3. Сортировка пузырьком
  4. https://www.baeldung.com/java-bubble-sort

Дополнительные материалы для ознакомления и расширения кругозора #

  1. Алгоритм сортировки
  2. Блочная сортировка