Метод сортировки пузырьком java

Java Blog

Сортировка «пузырьком» (Bubble sort) — это самый простой алгоритм сортировки, он сравнивает первые два элемента, если первый больше второго, меняет их местами, продолжает выполнять (сравнивает и меняет местами) следующую пару смежных элементов. Затем он начинается снова с первых двух элементов, сравнивает, переставляет, пока не потребуется перестановка.

Вот пример реализации сортировки «пузырьком» на Java.

public static int[] sort(int[] data) < int dataLength = data.length; int swap; boolean sorted; for (int i = 0; i < dataLength; i++) < sorted = true; for (int a = 1; a < (dataLength - i); a++) < if (data[a - 1] >data[a]) < swap = data[a - 1]; data[a - 1] = data[a]; data[a] = swap; sorted = false; >> // если отсортировано - выходим, пропуская ненужный цикл. if (sorted) break; > return data; >

Опробуем его с тестовыми данными.

package Bubble; public class Main < public static void main (String[] args) < int[] data = ; String sorted = ""; for (int el : sort(data)) < sorted += String.valueOf(el)+" "; >System.out.println(sorted); > public static int[] sort(int[] data) < int dataLength = data.length; int swap; boolean sorted; for (int i = 0; i < dataLength; i++) < sorted = true; for (int a = 1; a < (dataLength - i); a++) < if (data[a - 1] >data[a]) < swap = data[a - 1]; data[a - 1] = data[a]; data[a] = swap; sorted = false; >> // если отсортировано, выходим, пропуская ненужный цикл. if (sorted) break; > return data; > >

• Получить ссылку
• Facebook
• Twitter
• Pinterest
• Электронная почта
• Другие приложения

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Методы класса Object в Java

Класс Object является корнем иерархии классов. У каждого класса есть Object как суперкласс. Все объекты, включая массивы, реализуют методы этого класса. Методы класса Object Метод getClass() public final Class getClass() Возвращает класс времени исполнения (runtime class) этого Object. Возвращенный объект Class — это объект, который заблокирован статическими синхронизированными методами представленного класса. Фактический тип результата — Class где |X| заменяется статическим типом выражения, для которого вызывается getClass. Например, в этом фрагменте кода не требуется приведение: Number n = 0; Class c = n.getClass(); Метод getClass() возвращает: Объект Class, представляющий класс времени исполнения (runtime class) этого объекта. Метод hashCode public int hashCode() Возвращает значение хэш-кода для объекта. Этот метод поддерживается для использования хэш-таблиц, таких как те, что предоставляются HashMap. Основной контракт метода hashCo

Как получить текущий timestamp в Java

Чтобы получить текущий timestamp в Java : package main; import java.sql.Timestamp; public class Main < public static void main(String[] args)< Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); >> Вывод: 2019-10-03 10:09:21.61 Вот еще два более подробных примера как получить текущий timestamp в Java: 1. java.sql.Timestamp Есть два метода получить текущий java.sql.Timestamp package main; import java.sql.Timestamp; import java.text.SimpleDateFormat; import java.util.Date; public class Main < private static final SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy.MM.dd.HH.mm.ss"); public static void main(String[] args) < // Метод 1 Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); // Метод 2 - через Date Date date = new Date(); System.out.println(new Timestamp(date.getTime()

Spring Boot стартеры

Стартеры — это набор удобных дескрипторов зависимостей, которые вы можете включить в свое приложение. Вы получаете универсальный набор для всех необходимых вам Spring и связанных с ними технологий без необходимости искать примеры кода и копировать и вставлять множество дескрипторов зависимостей. Например, если вы хотите начать использовать Spring и JPA для доступа к базе данных, включите в ваш проект зависимость spring-boot-starter-data-jpa. Стартеры содержат множество зависимостей, которые необходимы вам для быстрого запуска и запуска проекта с согласованным, поддерживаемым набором управляемых переходных зависимостей. Что указывается в имени стартера Все официальные стартеры следуют аналогичной схеме именования; spring-boot-starter-*, где * это конкретный тип приложения. Эта структура наименования предназначена, чтобы помочь, когда вам нужно найти стартер. Интеграция Maven во многие IDE позволяет вам искать зависимости по имени. Например, если установлен соответствующий плагин Ecl

Источник

Реализация пузырьковой сортировки на 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!

Источник