ПРИМЕР 3. Сортировка массива

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

Последовательность действий

1. Создайте новый файл Bubble.java.

2. В алгоритме пузырьковой сортировки соседние элементы массива сравниваются и меняются, если требуется, местами. При этом малые значения сдвигаются к одному краю массива, а большие значения — к другому. Этот процесс напоминает всплывание пузырьков воздуха на разные уровни в емкости с жидкостью, откуда и произошло название данного алгоритма. Пузырьковая сортировка предполагает обработку массива в несколько проходов. Элементы, взаимное расположение которых отличается от требуемого, меняются местами. Число проходов должно быть таким, чтобы все элементы непременно встали на свои места. Максимальное количество проходов должно быть на один меньше, чем число элементов в массиве. Ниже приведен исходный код, составляющий основу алгоритма пузырьковой сортировки. Сортируемый массив называется nums.

// Это пример реализации алгоритма пузырьковой сортировки.

for(a=l; а < size; а++)

for(b=size-l; b > = a; b--) {

if(nums[b-l] > nums[b]) { // если требуемый порядок следования

//не соблюдается, поменять элементы местами

t = nums[b-1];

nums[b-l] = nums[b];

nums[b] = t;

}

}

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

3. Ниже приведен весь исходный код программы из файла Bubble.java.

/*

Демонстрация алгоритма пузырьковой сортировки.

*/

class Bubble {

public static void main(String args[]) {

int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9, 287, 49 };

int a, b, t;

int size;

size = 10; // Количество элементов для сортировки

// отобразить исходный массив

System.out.print(" Original array is: ");

for(int i=0; i < size; i++)

System.out.print(" " + nums[i]);

System.out.println();

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

for(a=l; а < size; а++)

for(b=size-l; b > = a; b—) {

if(nums[b-l] > nums[b]) { // если требуемый

// порядок следования не соблюдается, поменять

// элементы местами

t = nums[b-l];

nums[b-l] = nums[b];

nums[b] = t;

}

}

// отобразить отсортированный массив

System.out.print (" Sorted array is: ");

for(int i=0; i < size; i++)

System.out.print(" " + nums[i]);

System.out.println();

}

}

Ниже приведен результат выполнения данной программы.

Original array is: 99 -10 100123 18 -978 5623 463 -9 287 49

Sorted array is: -978 -10 -9 18 49 99 287 463 5623 100123