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

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

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

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

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

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

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 void 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);
        }
    }
}

Рекурсия #

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

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

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

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

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

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