Java, Практика

Java. Разработка класса, который реализует алгоритм сортировки выбором




Java. Разработка класса, который реализует алгоритм сортировки выбором

В данной теме описывается пошаговый процесс создания обобщенного класса, который реализует алгоритм сортировки выбором. Тема будет полезна начинающим при изучении методов сортировки а также основ объектно-ориентированного программирования. Принцип работы алгоритма сортировки выбором подробно описывается в теме:

Содержание

Поиск на других ресурсах:

1. Условие задачи

Разработать обобщенный класс SortSelection, содержащий средства реализующие алгоритм сортировки выбором. Продемонстрировать работу методов класса.

  ⇑

2. Выполнение
2.1. Создание проекта. Классы SortSelection и TestSortSelection

Первым шагом создается модуль TestSortSelection.java, в котором объявляется два класса:

  • класс SortSelection<T> – реализует алгоритм сортировки выбором. Параметр T типа в классе ограничен типом Number (T extends Number). Это означает, что класс предназначен для обработки числовых данных, например, данных типов Integer, Long, Short, Double и других;
  • класс TestSortSelection – предназначен для тестирования (использования) работы класса SortSelection.

На данный момент, текст модуля TestSortSelection.java следующий.

// Обобщенный класс, который реализует алгоритм сортировки выбором.
// Класс обрабатывает числовые типы (Integer, Double, ...) - ограничен типом Number
class SortSelection<T extends Number> {

}

public class TestSortSelection {
  // В методе main() тестируется работа класса SortSelection
  public static void main(String[] args) {

  }
}

  ⇑

2.2. Ввод внутренних переменных класса

В классе SotrSelection<T> в разделе private вводится внутренняя переменная A – массив обрабатываемых чисел.

// Обобщенный класс, который реализует алгоритм сортировки выбором.
// Класс обрабатывает числовые типы (Integer, Double, ...) - ограничен типом Number
class SortSelection<T extends Number> {
  private T[] A; // сортируемый массив
}

...

  ⇑

2.3. Конструкторы класса

Инициализацию данных класса выполняют конструкторы. В классе SortSelection реализованы три конструктора:

  • конструктор без параметров – устанавливает значение null для ссылки A;
  • конструктор, который получает входящим параметром внешний массив типа T[]. С помощью метода clone() в конструкторе формируется копия внешнего массива;
  • конструктор, который получает входным параметром другой экземпляр класса SortSelection<T>.

 

// Конструкторы класса
// Конструктор без параметров
SortSelection() {
  A = null;
}

// Конструктор, который получает параметром массив _A типа T[]
SortSelection(T[] _A) {
  A = _A.clone(); // Сделать копию из _A
}

// Конструктор, который получает параметром другой экземпляр класса SortSelection<T>
SortSelection(SortSelection<T> obj) {
  A = obj.A.clone();
}

  ⇑

2.4. Методы Get(), Set(). Доступ к внутреннему массиву

Для доступа к внутреннему массиву A используются методы Get(), Set() которые имеют следующую реализацию

// Методы доступа к внутренним данным в классе
// Получить копию внутреннего массива A
T[] Get() {
  return A.clone();
}

// Установить новое значение в массиве A
void Set(T[] _A) {
  A = _A.clone(); // сделать глубокую копию из _A
}

  ⇑

2.5. Метод Sort(). Сортировка всего массива

Главный метод класса, реализующий сортировку в массиве A, есть метод Sort().

// Метод, который реализует алгоритм сортировки выбором.
// Параметр order задает порядок сортировки:
// - если order=true, то отсортировать в порядке возрастания;
// - если order=false, то отсортировать в порядке убывания.
void Sort(boolean order) {
  int i, j, k;
  T t;

  for (i=0; i<A.length; i++) // i - номер шага
  {
    k = i;
    t = A[i];

    // Цикл поиска наименьшего (наибольшего) элемента
    for (j=i+1; j<A.length; j++)
      if (order) {
        // Поиск наименьшего элемента
        if (A[j].doubleValue()<t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }
      else {
        // Поиск наибольшего элемента
        if (A[j].doubleValue()>t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }

    A[k] = A[i];
    A[i] = t;
  }
}

  ⇑

2.6. Метод SortRange(). Сортировка массива в заданных пределах

Бывают случаи, когда нужно отсортировать элементы в заданном диапазоне. Для этого в классе реализован метод SortRange(). Метод получает три параметра: порядок сортировки (по возрастанию или убыванию), нижнюю и верхнюю границы диапазона.

// Метод, который реализует алгоритм сортировки выбором в заданном диапазоне [pos1, pos2-1]
// Параметры:
// - order - порядок сортировки (true-по возрастанию, false-по убыванию);
// - pos1 - нижняя граница индекса в массиве включительно;
// - pos2 - верхняя граница индекса - исключительно.
// Если сортировка состоялась успешно, функция возвращает true, иначе - false.
boolean SortRange(boolean order, int pos1, int pos2) {

  // Проверка значений pos1 и pos2 на адекватность
  if (pos1>=pos2) return false;
  if ((pos1<0) || (pos1>=A.length)) return false;
  if ((pos2<0) || (pos2>A.length)) return false;

  // Если все в порядке, то отсортировать массив
  int i, j, k;
  T t;

  for (i=pos1; i<pos2; i++) // i - номер шага
  {
    k = i;
    t = A[i];

    // Цикл поиска наименьшего (наибольшего) элемента
    for (j=i+1; j<pos2; j++)
      if (order) {
        // Поиск наименьшего элемента
        if (A[j].doubleValue()<t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }
      else {
        // Поиск наибольшего элемента
        if (A[j].doubleValue()>t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }

    A[k] = A[i];
    A[i] = t;
  }

  return true;
}

  ⇑

2.7. Метод Print(). Вывод массива

 

// Метод, который выводит содержимое массива A - используется при тестировании класса
void Print(String comment) {
  System.out.println(comment);
  for (int i=0; i<A.length; i++)
    System.out.print(A[i]+" ");
  System.out.println();
}

  ⇑

3. Разработка класса TestSortSelection, метод main(). Тестирование работы класса SortSelection

В классе TestSortSelection реализован метод main(), в котором продемонстрировано использование методов класса SortSelection.

public class TestSortSelection {

  // В методе main() тестируется работа класса SortSelection
  public static void main(String[] args) {

    // 1. Использование экземпляра класса для типа Integer
    Integer[] AI = { 2, 3, 8, 1, 4, 7, 9, 5, 2 };
    SortSelection<Integer> objInt1 = new SortSelection<Integer>(AI);
    objInt1.Print("Before sorting - objInt1:"); // вывести массив перед сортировкой

    // 1.1. Отсортировать массив в порядке убывания элементов
    objInt1.Sort(false);
    objInt1.Print("After sorting - objInt1:");

    // 1.2. Тест метода Get()
    Integer[] AI2;
    AI2 = (Integer[])objInt1.Get(); // скопировать массив экземпляра objInt1

    // 1.3. Вывести массив AI2
    System.out.println("Array AI2: ");
    for (int i=0; i<AI2.length; i++)
      System.out.print(AI2[i]+" ");
    System.out.println();

    // 1.4. Отсортировать элементы массива objInt1 в указанных пределах [2, 5]
    // Тест метода SortRange()
    int pos1 = 2;
    int pos2 = 6;
    objInt1.SortRange(true, pos1, pos2); // в порядке возрастания
    objInt1.Print("objInt1.Range(true, 2, 6)");

    // 2. Использование экземпляра класса для типа Float
    Float[] AF = { 2.8f, 3.5f, 11.23f, 0.5f, 2.4f, 1.1f };
    SortSelection<Float> objFloat1 = new SortSelection<Float>(AF);
    objFloat1.Print("Array objFloat1 before sorting");

    // 2.1. Отсортировать элементы в порядке возрастания
    objFloat1.Sort(true);
    objFloat1.Print("Array objFloat1 after sorting");

    // 2.2. Тест метода Set()
    Float[] AF2 = { 0.1f, 0.5f, -0.2F, -1.3F, -100.77F };
    objFloat1.Set(AF2); // установить новый массив в экземпляре objFloat1
    objFloat1.Print("Array objFloat1 after changing:");
  }
}

  ⇑

4. Структура всей программы (модуля TestSortSelection.java). Сокращенный вариант

 

// Обобщенный класс, который реализует алгоритм сортировки выбором.
// Класс обрабатывает числовые типы (Integer, Double, ...) - ограничен типом Number
class SortSelection<T extends Number> {

  private T[] A; // сортируемый массив

  // Конструкторы класса
  // Конструктор без параметров
  SortSelection() {
    ...
  }

  // Конструктор, получающий параметром массив _A типа T[]
  SortSelection(T[] _A) {
    ...
  }

  // Методы доступа к внутренним данным в классе
  // Получить копию внутреннего массива A
  T[] Get() {
    ...
  }

  // Установить новое значение в массиве A
  void Set(T[] _A) {
    ...
  }

  // Метод, реализующий алгоритм сортировки выбором.
  // Параметр order задает порядок сортировки:
  // - если order=true, то отсортировать в порядке возрастания;
  // - если order=false, то отсортировать в порядке убывания.
  void Sort(boolean order) {
    ...
  }

  // Метод, реализующий алгоритм сортировки выбором в указанном диапазоне [pos1, pos2-1]
  boolean SortRange(boolean order, int pos1, int pos2) {
    ...
  }

  // Метод, который выводит содержимое массива A - используется при тестировании класса
  void Print(String comment) {
    ...
  }
}

public class TestSortSelection {
  ...
}

  ⇑

5. Результат выполнения программы
Before sorting - objInt1:
2 3 8 1 4 7 9 5 2
After sorting - objInt1:
9 8 7 5 4 3 2 2 1
Array AI2:
9 8 7 5 4 3 2 2 1
objInt1.Range(true, 2, 6)
9 8 3 4 5 7 2 2 1
Array objFloat1 before sorting
2.8 3.5 11.23 0.5 2.4 1.1
Array objFloat1 after sorting
0.5 1.1 2.4 2.8 3.5 11.23
Array objFloat1 after changing:
0.1 0.5 -0.2 -1.3 -100.77
objFloat2:
0.1 0.5 -0.2 -1.3 -100.77

  ⇑

Связанные темы

  ⇑