Всем привет! Это сообщение в блоге “Концепции как код” является первым в серии, в которой я попытаюсь объяснить концепции в области компьютерных наук самыми простыми способами, которые я могу.
Как человек, у которого не было формализованного образования в области компьютерных наук, я всегда чувствовал, что упустил возможность изучить внутреннюю работу структур данных и алгоритмов, которые должен знать каждый инженер-программист (я никогда не тестировался на них во время собеседования! Может быть, это и хорошо?).
Поэтому одна из моих будущих амбиций в блоге состоит в том, чтобы делать короткие и приятные посты о конкретных концепциях, которые я изучаю и которым могу научить других.
Я буду кодировать эти концепции на Java, так как это язык, который мне наиболее удобен и которым я пользуюсь чаще всего. Я могу время от времени переключать его и использовать Python, но посмотрим, как мы поступим.
С этим покончено, давайте начнем с простого алгоритма сортировки, называемого пузырьковой сортировкой.
Представляем сортировку пузырьков
Это не те пузыри, которые мы ищем
Из всех алгоритмов сортировки Пузырьковая сортировка является самой простой.
По сути, у нас есть входной массив, по которому сортировка пузырьков будет выполняться несколько раз. Во время каждого прохода алгоритм сравнивает два элемента рядом друг с другом и меняет их местами, если они не отсортированы. Это называется пузырьковой сортировкой, потому что сортировка “всплывает” из нижнего конца списка.
Давайте разберем это еще глубже. Сортировка пузырьков выполняет три простые задачи:
- Многократно просматривая список для сортировки.
- Сравнение соседних элементов (элементов рядом друг с другом) в списке и их сортировка.
- Меняем их местами, если первый элемент больше второго элемента.
Давайте взглянем на некоторый псевдокод, чтобы лучше визуализировать этот процесс:
bubbleSort(inputArray)
n = length(inputArray)
for (k = 1 until n)
for (j = 0 until -1)
if(array[j] > array[j + 1])
swap(array, j, j + 1)
В этом коде psuedo n – длина нашего массива. Чтобы убедиться, что весь наш список отсортирован, нам нужно выполнить n — 1 переходов в нашем списке. Если бы у нас был список из 10 элементов, нам нужно было бы сравнить второй элемент нашего списка (в позиции 1 в массиве) и продолжать просматривать его 9 раз, пока мы не отсортируем весь список. В конце списка создается отсортированный пузырь, поэтому нам нужно сделать n — 1 проходов в нашем списке.
В ваших операторах if мы сравниваем число в нашем массиве в позиции j с числом в позиции j + 1 (соседнее число в нашем списке).
Реализация пузырьковой сортировки в Java
Давайте превратим наш псевдокод в какой-нибудь реальный Java-код. Наш метод сортировки пузырьков должен выглядеть следующим образом.
public void sortV1(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
}
Как и в нашем псевдокоде, нам нужно пройти через наш список n — 1 раз. Если число в позиции j больше, чем число в позиции j + 1, мы используем временную переменную для обмена позициями чисел.
Давайте посмотрим на это в действии. Мы создадим список чисел, которые мы сможем отсортировать в нашем основном методе.
// Program entry
public static void main(String[] args) {
// Instantiate a new instance of our BubbleSort class
BubbleSort sort = new BubbleSort();
// Define the input array that we wish to sort
int[] inputArray = new int[]{6,4,3,6,4,7,9,2,4,3,1};
// Call our sortV1 method and pass in our inputArray
sort.sortV1(inputArray);
// Print out the results to the console
System._out_.println(Arrays._toString_(inputArray));
}
По сути, мы создаем новый экземпляр нашего класса BubbleSort и применяем метод сортировки в нашем списке. Затем мы выводим наш отсортированный список на консоль и должны получить следующий результат.
[1, 2, 3, 3, 4, 4, 4, 6, 6, 7, 9] Process finished with exit code 0
Теперь, как вы можете видеть, сортировка пузырьков действительно довольно проста в реализации. Однако это также один из самых медленных методов сортировки. Я расскажу о сложности и времени выполнения в следующем сообщении в блоге, но сейчас давайте сосредоточимся на том, как мы можем улучшить время выполнения нашей сортировки пузырьков.
Сортировка пузырьков происходит довольно медленно, но, вероятно, не так медленно…
Улучшение нашей среды выполнения сортировки пузырьков
Прежде чем мы начнем улучшать вашу сортировку пузырьков, важно отметить, что эти улучшения все равно приведут к снижению сложности выполнения в худшем случае. По-прежнему важно знать, как вы можете повысить производительность, поэтому я расскажу об одном способе сделать это здесь.
Во-первых, давайте создадим частный метод обмена, который выполняет обмен за нас.
// swap helper method
private void swap(int[] numbers, int a, int b) {
int temp = numbers[a];
numbers[a] = numbers[b];
numbers[b] = temp;
}
Мы также можем сократить количество проходов, которые мы делаем в нашем списке. В настоящее время, если бы мы предоставили нашему методу сортировки список, который уже был отсортирован, мы бы все равно сделали несколько проходов по нему.
Чтобы этого не произошло, мы можем удалить внешний цикл, когда список будет полностью отсортирован. В нашем внутреннем цикле вместо того, чтобы проходить через список n — 1 раз, мы пройдем через список n-i раз. Это остановит алгоритм сортировки пузырьков непосредственно перед отсортированным пузырьком.
В нашем новом внешнем цикле мы проверяем, отсортирован ли массив, проверяя, были ли выполнены какие-либо замены в последнем проходе. Таким образом, если наш список уже отсортирован, мы просто делаем один проход по списку и оставляем его в покое.
Наш новый метод должен выглядеть так:
// Bubble Sort improvement
public void sortV2(int[] numbers) {
int i = 0;
boolean hasSwappedOccured = true;
while (hasSwappedOccured) {
hasSwappedOccured = false;
i++;
for (int j = 0; j < numbers.length - i; j++) {
if (numbers[j] < numbers[j + 1]) {
swap(numbers, j, j + 1);
hasSwappedOccured = true;
}
}
}
}
Теперь мы можем внедрить наш новый метод сортировки в наш основной метод следующим образом:
// Program entry
public static void main(String[] args) {
// Instantiate a new instance of our BubbleSort class
BubbleSort sort = new BubbleSort();
// Define the input array that we wish to sort
int[] inputArray = new int[]{6,4,3,6,4,7,9,2,4,3,1};
// Call our sortV2 method and pass in our inputArray
sort.sortV2(inputArray);
// Print out the results to the console
System._out_.println(Arrays._toString_(inputArray));
}
И, как вы можете видеть, мы получаем тот же результат:
[1, 2, 3, 3, 4, 4, 4, 6, 6, 7, 9] Process finished with exit code 0
Вывод
В этом посте мы рассмотрели сортировку пузырьков. Это один из самых простых алгоритмов сортировки, которые вы можете использовать, но он также является одним из наихудших. В будущих постах мы рассмотрим методы сортировки, которые работают намного лучше, чем пузырьковая сортировка.
Не этот тип сортировки, хотя ….
Если вы хотите поближе ознакомиться с кодом в этом посте, ознакомьтесь с моим репозиторием на GitHub здесь .
Оригинал: “https://dev.to/willvelida/concepts-as-code-bubble-sort-53l3”