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

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

Введение

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

Сортировка глазами машины и глазами человека

Давайте представим, что вам нужно отсортировать по возрастанию 5 столбиков разной высоты. Под этими столбиками может пониматься какая угодно информация (цены на акции, пропускная способность канала связи и пр.), можете представить какой-то свой вариант этой задачи, чтобы было более наглядно. Ну а мы, в качестве примера, будем сортировать мстителей по росту: Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:

Done!

И на этом сортировка будет успешно завершена. Однако, вычислительная машина в отличие от вас несколько туповата не видит всю структуру данных целиком. Ее программа управления может сравнивать лишь два значения в один промежуток времени. Для решения этой задачи ей придется поместить в свою память два числа и выполнить над ними операцию сравнения, после чего перейти к другой паре чисел, а так до тех пор, пока не будут проанализированы все данные. Поэтому любой алгоритм сортировки очень упрощенно можно представить виде трех шагов:

• Сравнить два элемента;
• Поменять местами или скопировать один из них;
• Перейти к следующему элементу;

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

Алгоритм пузырьковой сортировки

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

• Вы перемещаетесь к нулевому элементу нашего массива (Черная Вдова);
• Сравниваете нулевой элемент (Черную Вдову) с первым (Халком);
• Если элемент на нулевой позиции оказался выше, вы меняете их местами;
• Иначе, если элемент на нулевой позиции меньше, вы оставляете их на своих местах;
• Производите переход на позицию правее и повторяете сравнение (сравниваете Халка с Капитаном)

После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка: Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево: Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк): Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки: Визуализация работы пузырьковой сортировки

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

Для демонстрации работы сортировки на Java, приведем программный код, который:

• создает массив на 5 элементов;
• загружает в него рост мстителей;
• выводит на экран содержимое массива;
• реализует пузырьковую сортировку;
• осуществляет повторный вывод на экран отсортированного массива.

С кодом можно ознакомиться ниже, и даже загрузить его в свою любимую IntelliJ IDE. Его разбор будет производиться ниже:

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();            //снова выводим отсортированный йсписок
    }
}

Не смотря на подробные комментарии в коде, приведем описание некоторых методов, представленных в программе. Ключевые методы, осуществляющую основную работу в программе написаны в классе ArrayBubble. Класс содержит конструктор и несколько методов:

• 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);             //вызвать метод, меняющий местами
              }
          }
      }
  

Здесь следует обратить внимание на два счетчика: внешний out, и внутренний in. Внешний счетчик out начинает перебор значений с конца массива и постепенно уменьшается с каждым новым проходом на единицу. Переменная out с каждым новым проходом смещается все левее, чтобы не затрагивать значения, уже отсортированные в правую часть массива. Внутренний счетчик in начинает перебор значений с начала массива и постепенно увеличивается на единицу на каждом новом проходе. Увеличение in происходит до тех пока, пока он не достигнет out (последнего анализируемого элемента в текущем проходе). Внутренний цикл in производит сравнение двух соседних ячеек in и in+1. Если в in хранится большее число, чем в in+1, то вызывается метод toSwap, который меняет местами эти два числа.

Заключение

Алгоритм пузырьковой сортировки является одним из самых медленных. Если массив состоит из 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!