Java, Practice

Java. Developing a class that implements the selection sorting algorithm




Java. Developing a class that implements the selection sorting algorithm

This topic describes the step-by-step process for creating a generic class that implements the selection sorting algorithm. The topic will be useful for beginners when learning sorting methods and the basics of object-oriented programming. The principle of operation of the selection sorting algorithm is described in detail in the topic:

Contents

Search other websites:

1. Task

Develop a generic SortSelection class that contains tools for implementing the selection sorting algorithm. Demonstrate the methods of the class.

  ⇑

2. Instruction
2.1. Project creating. Classes SortSelection and TestSortSelection

The first step is to create the TestSortSelection.java module, which declares two classes:

  • class SortSelection<T> – implements the selection sorting algorithm. The type parameter T in the class is limited to the type Number (T extends Number). This means that the class is designed to handle numeric data, for example, data of types Integer, Long, Short, Double, and others;
  • TestSortSelectin class – designed to test (use) the operation of the SortSelection class.

At the moment, the text of the TestSortSelection.java module is as follows.

// A generalized class that implements the selection sorting algorithm.
// Class handles numeric types (Integer, Double, ...) - limited to Number type
class SortSelection<T extends Number> {

}

public class TestSortSelection {
  // In the main() method, the operation of the SortSelection class is tested
  public static void main(String[] args) {
  }
}

  ⇑

2.2. Entering the internal class variables

In the SotrSelection<T> class, in the private section, an internal variable A is introduced – an array of numbers to process.

// A generalized class that implements the selection sorting algorithm.
// Class handles numeric types (Integer, Double, ...) - limited to Number type
class SortSelection<T extends Number> {
  private T[] A; // sortable array
}

...

  ⇑

2.3. Class constructors

Constructors perform initialization of class data. The SortSelection class implements three constructors:

  • constructor without parameters – sets a value of null for the reference A;
  • a constructor that receives an external array of type T[] as an input parameter. The clone() method in the constructor creates a copy of the external array;
  • a constructor that receives as an input parameter another instance of the SortSelection<T> class.

 

// Class constructors
// Constructor without parameters
SortSelection() {
  A = null;
}

// A constructor that receives as a parameter an array _A of type T[]
SortSelection(T[] _A) {
  A = _A.clone(); // Make a copy from _A
}

// A constructor that takes as parameter another instance of the SortSelection<T> class
SortSelection(SortSelection<T> obj) {
  A = obj.A.clone();
}

  ⇑

2.4. Methods Get(), Set(). Access to the internal array

To access the internal array A, the Get(), Set() methods are used which have the following implementation

// Methods for accessing internal data in a class
// Get a copy of internal array A
T[] Get() {
  return A.clone();
}

// Set new value in array A
void Set(T[] _A) {
  A = _A.clone(); // make a copy from _A
}

  ⇑

2.5. Method Sort(). Sorting the entire array

The main class method that implements sorting in array A is the Sort() method.

// A method that implements the selection sorting algorithm.
// The order parameter sets the sort order:
// - if order = true, then sort in ascending order;
// - if order = false, then sort in descending order.
void Sort(boolean order) {
  int i, j, k;
  T t;

  for (i=0; i<A.length; i++) // i - step number
  {
    k = i;
    t = A[i];

    // Loop to find the smallest (largest) element
    for (j=i+1; j<A.length; j++)
      if (order) {
        // Finding the smallest element
        if (A[j].doubleValue()<t.doubleValue())
        {
          k = j;
          t = A[j];
        }
    }
    else {
      // Finding the largest element
      if (A[j].doubleValue()>t.doubleValue())
      {
        k = j;
        t = A[j];
      }
    }

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

  ⇑

2.6. Method SortRange(). Sorting an array within specified limits

There are times when you need to sort items in a given range. For this, the SortRange() method is implemented in the class. The method takes three parameters: the sort order (ascending or descending), the lower and upper bounds of the range.

// Method that implements the selection sorting algorithm in a given range [pos1, pos2-1]
// Parameters:
// - order - sorting order (true-ascending, false-descending);
// - pos1 - the lower bound of the index in the array inclusive;
// - pos2 - index upper bound - exclusively.
// If the sorting was successful, the function returns true, otherwise - false.
boolean SortRange(boolean order, int pos1, int pos2) {
  // Checking pos1 and pos2 values for adequacy
  if (pos1>=pos2) return false;
  if ((pos1<0) || (pos1>=A.length)) return false;
  if ((pos2<0) || (pos2>A.length)) return false;

  // If everything is in order, then sort the array
  int i, j, k;
  T t;

  for (i=pos1; i<pos2; i++) // i - step number
  {
    k = i;
    t = A[i];

    // Loop to find the smallest (largest) element
    for (j=i+1; j<pos2; j++)
      if (order) {
        // Finding the smallest element
        if (A[j].doubleValue()<t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }
      else {
        // Finding the largest element
        if (A[j].doubleValue()>t.doubleValue())
        {
          k = j;
          t = A[j];
        }
      }
    A[k] = A[i];
    A[i] = t;
  }

  return true;
}

  ⇑

2.7. Method Print(). Print the array

 

// Method that outputs the contents of array A - used when testing the class
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. Development of the TestSortSelection class, the main() method. Testing the SortSelection class

The TestSortSelection class implements the main() method, which demonstrates the use of the methods of the SortSelection class.

public class TestSortSelection {
  // In the main() method, the operation of the SortSelection class is tested
  public static void main(String[] args) {
    // 1. Using class instance for Integer type
    Integer[] AI = { 2, 3, 8, 1, 4, 7, 9, 5, 2 };
    SortSelection<Integer> objInt1 = new SortSelection<Integer>(AI);
    objInt1.Print("Before sorting - objInt1:"); // print the array before sorting

    // 1.1. Sort an array in descending order of elements
    objInt1.Sort(false);
    objInt1.Print("After sorting - objInt1:");

    // 1.2. Test of method Get()
    Integer[] AI2;
    AI2 = (Integer[])objInt1.Get(); // copy array of instance objInt1

    // 1.3. Print the array AI2
    System.out.println("Array AI2: ");
    for (int i=0; i<AI2.length; i++)
      System.out.print(AI2[i]+" ");
    System.out.println();

    // 1.4. Sort the elements of the objInt1 array within the specified limits [2, 5]
    //     SortRange() method test
    int pos1 = 2;
    int pos2 = 6;
    objInt1.SortRange(true, pos1, pos2); // in ascending order
    objInt1.Print("objInt1.Range(true, 2, 6)");

    // 2. Using a class instance for the Float type
    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. Sort elements in ascending order
    objFloat1.Sort(true);
    objFloat1.Print("Array objFloat1 after sorting");

    // 2.2. Test of method Set()
    Float[] AF2 = { 0.1f, 0.5f, -0.2F, -1.3F, -100.77F };
    objFloat1.Set(AF2); // install a new array in an instance objFloat1
    objFloat1.Print("Array objFloat1 after changing:");
  }
}

  ⇑

4. The structure of the entire program (TestSortSelection.java module). Abridged version
// A generalized class that implements the selection sorting algorithm.
// Class handles numeric types (Integer, Double, ...) - limited to Number type
class SortSelection<T extends Number> {
  private T[] A; // sortable array

  // Class constructors
  // Constructor without parameters
  SortSelection() {
    ...
  }

  // A constructor that receives an _A array of type T[] as a parameter
  SortSelection(T[] _A) {
    ...
  }

  // Methods for accessing internal data in a class
  // Get a copy of internal array A
  T[] Get() {
    ...
  }

  // Set a new value in array A
  void Set(T[] _A) {
    ...
  }

  // Method implementing the selection sorting algorithm.
  // The order parameter sets the sort order:
  // - if order = true, then sort in ascending order;
  // - if order = false, then sort in descending order.
  void Sort(boolean order) {
    ...
  }

  // A method that implements a selection sorting algorithm in a specified range [pos1, pos2-1]
  boolean SortRange(boolean order, int pos1, int pos2) {
    ...
  }

  // Method that outputs the contents of array A - used when testing the class
  void Print(String comment) {
    ...
  }
}

public class TestSortSelection {
  ...
}

  ⇑

5. The result of the program
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

  ⇑

Related topics

  ⇑