Урок J-11. Сортировка массива в Java.

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

Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.

Сортировка выбором (Selection sort) в Java.

Реализация алгоритма Сортировка выбором на Java:

public static void selectionSort(int[] arr){
    /*По очереди будем просматривать все подмножества
      элементов массива (0 - последний, 1-последний, 
      2-последний,...)*/
    for (int i = 0; i < arr.length; i++) {
        /*Предполагаем, что первый элемент (в каждом
           подмножестве элементов) является минимальным */
        int min = arr[i];
        int min_i = i; 
        /*В оставшейся части подмножества ищем элемент,
           который меньше предположенного минимума*/
        for (int j = i+1; j < arr.length; j++) {
            //Если находим, запоминаем его индекс
            if (arr[j] < min) {
                min = arr[j];
                min_i = j;
            }
        }
        /*Если нашелся элемент, меньший, чем на текущей позиции,
          меняем их местами*/
        if (i != min_i) {
            int tmp = arr[i];
            arr[i] = arr[min_i];
            arr[min_i] = tmp;
        }
     }
}

Еще одним достаточно простым и известным способом сортировки является Сортировка пузырьком.

Сортировка пузырьком (Bubble sort) в Java.

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

Реализация алгоритма Сортировка пузырьком на Java (по возрастанию):

public static void bubbleSort(int[] arr){
    /*Внешний цикл каждый раз сокращает фрагмент массива, 
      так как внутренний цикл каждый раз ставит в конец
      фрагмента максимальный элемент*/   
    for(int i = arr.length-1 ; i > 0 ; i--){
        for(int j = 0 ; j < i ; j++){
            /*Сравниваем элементы попарно, 
              если они имеют неправильный порядок, 
              то меняем местами
            if( arr[j] > arr[j+1] ){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

Следующие 2 видео наглядно демонстрируют работу алгоритмов сортировки пузырьком и выбором.

Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:

int arr[] ={62, 84, 32, 5, 0, 14, 52, 82, 58, 71};

Или мы можем создать массив случайных чисел

int arr[] = new int[10];
for(int i = 0; i < arr.length; i++) {
    //элементу массива присваивается случайное число от 0 до 99
    arr[i] = (int)(Math.random() * 100);
    System.out.print(arr[i] + "  ");
}

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

System.out.print("\n");
bubbleSort(arr);
for(int i = 0; i <  arr.length; i++) {
        System.out.print(arr[i] + "  ");
}       

или

System.out.print("\n");
selectionSort(arr);
for(int i = 0; i <  arr.length; i++) {
        System.out.print(arr[i] + "  ");
}       

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

В наше время нет необходимости самостоятельно реализовывать алгоритмы для сортировки, поскольку все что нам нужно, уже имеется в стандартных библиотеках Java.

 

Сортировка массива при помощи метода sort() из класса Arrays.

Метод sort() из класса Arrays использует усовершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку.

Arrays.sort(arr);// где arr это имя массива

Примечание: в начале файла предварительно нужно подключить библиотеку  java.util.

import java.util.*;

Сортировка массива целых чисел по возрастанию:

//Создаем массив случайных чисел
int arr[] = new int[10];
for(int i = 0; i <  arr.length; i++) {
        arr[i] =  (int)(Math.random() * 100);
        System.out.print(arr[i] + "  ");
}
System.out.print("\nSorted: \n");
//Сортируем массив
Arrays.sort(arr);
//Выводим отсортированный массив на консоль.
for(int i = 0; i <  arr.length; i++) {
        System.out.print(arr[i] + "  ");
}

Сортировка массива целых чисел по убыванию:

//Создаем массив случайных чисел
Integer arr[] = new Integer[10];
for(int i = 0; i <  arr.length; i++) {
        arr[i] =  (int)(Math.random() * 100);
        System.out.print(arr[i] + "  ");
}
System.out.print("\nSorted: \n");
//Сортируем массив
Arrays.sort(arr, Collections.reverseOrder());
//Выводим отсортированный массив на консоль.
for(int i = 0; i <  arr.length; i++) {
        System.out.print(arr[i] + "  ");
}

Обратите внимание, что при сортировке массива в обратном порядке (по убыванию) нужно использовать тип Integer[] вместо примитивного типа int[].

Сортировка массива строк в Java:

String[] names = new String[] {"Roman","Anna", "Petr", "Maria"}; 

Arrays.sort(names);
for(int i = 0; i <  names.length; i++) {
        System.out.print(names[i] + "  ");
}

В этом примере массив имен сортируется в порядке от А до Я. Для того чтобы отсортировать массив в обратном порядке, необходимо в методе sort() указать Collections.reverseOrder().

Arrays.sort(names, Collections.reverseOrder());

К сожалению, по умолчанию метод sort() сортирует только примитивные типы данных и строки. Как сортировать массив из собственно созданных объектов, будет рассмотрено в следующих уроках, поскольку это требует более углубленных знаний.

Упражнения на тему сортировка массивов в Java:

  1. Создайте массив из 20 случайных чисел (числа должны быть в диапазоне от 0 до 1000) и отсортируйте массив по убыванию при помощи сортировки пузырьком.
  2. Создайте массив содержащий марки автомобилей, отсортируйте его сначала по возрастанию, потом по убыванию.

Комментарии и пинги к записи запрещены.

Комментариев к записи: 53

  1. simsim:

    1,2 упражнение http://pastebin.com/ADcGm1F6

сюда
Все материалы сайта study-java.ru являются результатом труда его авторов. Копирование материалов в некоммерческих целях без указания источника в виде прямой ссылки на сайт study-java.ru запрещено. Использование материалов в коммерческих целях разрешено только с письменного согласия автора. Нарушение авторских прав преследуется по закону.