Методы сортировки

Санкт-Петербургский Государственный университет Телекоммуникаций им. проф. Бонч-Бруевича

Факультет Инфокоммуникационных Сетей и Систем

Кафедра Программной инженерии и вычислительной техники

Лабораторная работа

«Методы сортировки»

Группа:

Преподаватель:

Студент:

г. Санкт-Петербург

2020

1. Цель работы.

Ознакомление с алгоритмами сортировки линейных и нелинейных структур и методикой оценки эффективности алгоритмов.

1. Постановка задачи.

Для каждого из перечисленных методов сортировки провести анализ временных затрат для списков различной размерности. Вариант задания: сравнение временных затрат между сортировками Шелла и Пузырьком.

1. Описание алгоритма

[pic 1]

• Сортировка Пузырьком:

Перемещаемся к текущему (нулевому – назовем его N) элементу. Далее сравниваем его с N+1, если текущий элемент больше – то меняем их местами. Иначе – оставляем элементы на своих местах и сдвигаемся на позицию правее (N + 1).

• Сортировка Шелла:

[pic 2]

На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2 (Где N – общее число элементов); они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, вплоть до d = 1.

1. ЯП и IDE

1. OC – Windows 10, 64-bit (ОЗУ: 8гб, Процессор: Intel Core i5 8th gen 8250u))
2. ЯП – Java (JDK 11)
3. IDE – IntelliJ IDEA 2019.3.1 x64

Также в разработке импортировалась одна библиотека: java.util*

• класс Random (для заполнения массивов случайно-сгенерированными числами)
• класс Scanner (для ввода данных пользователем)
• статический метод Arrays.fill (для “очистки” массива)

1. Результаты работы

• Первый тест (Размер массива – 1000, количество сортировок - 300):

[pic 3]

• Второй тест (Размер массива – 1000, количество сортировок 700):[pic 4]

• Третий тест (Размер массива 2000, количество сортировок 1000):

[pic 5]

• Финальный тест (Размер массива 2500, количество сортировок 1300):

[pic 6]

Графики сортировок:

“y” – Время сортировки, “x” – Количество элементов массива.

[pic 7]

1. Выводы

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

1. Код программы

Класс ArraySort:

package LABS.LAB1;

import java.util.*;



public class ArraySort {
   private static int N,n;//Количество тестов // Количество элементов массива
   private static int[] array; // Массив целочисленных элементов
   private static Random randomNum;
   private static Scanner keyboard;
   private static long[] times;

   static{
       keyboard = new Scanner(System.in);
       randomNum = new Random();
       times = new long[2];
   }

   //Генерируем массив
   public void generateArray(){
       System.out.println("Введите размер массива: ");
       n = keyboard.nextInt();
       array = new int[n];
   }
   //Заполняем массива
   public void fillArray(){
       if(array == null){
           assert false;
           for (int i = 0; i < array.length; i++) {
               array[i] = randomNum.nextInt(1000) + 1;
           }
       }else {
           cleanArray();
           for (int i = 0; i < array.length; i++) {
               array[i] = randomNum.nextInt(1000) + 1;
           }
       }
   }

public void bubbleSort(){
   int change;
   for (int i = n - 1; i >= 1; i--) {
       for (int j = 0; j < i; j++) {
           if (array[j] > array[j + 1]) {
               change = array[j];
               array[j] = array[j + 1];
               array[j + 1] = change;
           }
       }
   }
}

public void shellSort(){
   for (int gap = array.length / 2; gap > 0; gap /= 2) {
       for (int i = gap; i < array.length; i++) {
           int key = array[i];
           int j = i;
           while (j >= gap && array[j - gap] > key) {
               array[j] = array[j - gap];
               j -= gap;
           }
           array[j] = key;
       }
   }
}

   //Сортировка Шелла
   public void sort() {
       long shellTime = 0, bubbleTime = 0; // Время сортировки
       if (array == null) {
           System.out.println("Массив пуст. Выйдете в меню и сгенерируйте его.");
       } else {
           System.out.println("Введите число сортировок: ");
           N = keyboard.nextInt();
           long firstTime = System.currentTimeMillis();
           //Сортировка шелла
           for (int test = 0; test < N; test++) {
               fillArray();
               shellSort();
               //Время теста сортировки
               shellTime += System.currentTimeMillis() - firstTime;
               // Добавили время
               fillArray();
               firstTime = System.currentTimeMillis();
               //Сортировка пузырьком
               bubbleSort();
               bubbleTime += System.currentTimeMillis() - firstTime;

               cleanArray();
           }
           System.out.println("Сортировки завершены ");
           times[0] = shellTime; //  Среднее время
           times[1] = bubbleTime;// Среднее время
           displayTime();
           destructClass();
       }
   }

   public void displayTime(){
       System.out.println("Конечное время сортировок: ");
       System.out.println("Сортировка пузырьком: " + times[0] * 0.001 + " cек");
       System.out.println("Сортировка Шелла: " + times[1] * 0.001 + " cек");
       System.out.println("Массив очищен. Нажмите \"G\" для генерации");


   }
   public void displayArray(){
       if(array != null){
           System.out.print("[");
           for (int value : array) {
               System.out.print(value + ", ");
           }
           System.out.print("]");
       }else{
           System.out.println("Массив пустой");
       }
       System.out.println("\n");
   }

   public void cleanArray(){
       Arrays.fill(array, 0);
   }


   public void destructClass(){
       n = 0;
       N = 0;
       cleanArray();
   }
}