C#. Development of a generic class that implements the selection sorting algorithm in C#





Development of a generic class that implements the selection sorting algorithm in C#

This topic describes the implementation of a generic class in C#, which contains tools that implement the selection sorting algorithm.

Before using this topic, it is recommended that you familiarize yourself with the theoretical features of the algorithm in the following topic:


Contents


Search other websites:

Task

Develop a generic SortSelection<T> class that implements the selection sorting algorithm. Demonstrate how class methods work.

 

Instructions

1. Create a project. Classes SortSelection<T> and Program. The IComparable<T> interface

The development of the class is performed in the Microsoft Visual Studio – 2019 system using the C# application template – Console Application. The text of two classes is pre-formed:

  • generic class SortSelection<T>, which is the solution of this problem;
  • the Program class, in which the SortSelection<T> class will be tested.

The initial program code is as follows

// Developing a class that implements the selection sorting algorithm
using System;
using static System.Console;

namespace ConsoleApp10
{
  // The generalized class SortSelection<T> - Implements the selection sorting algorithm.
  // To compare values, you need to implement the IComparable<T> interface.
  class SortSelection<T> where T:IComparable<T>
  {

  }

  // Class Program - tests the work of the SortSelection<T> class
  class Program
  {
    static void Main(string[] args)
    {

    }
  }
}

As you can see from the code, the SortSelection<T> class implements the generic IComparable<T> interface

...

class SortSelection<T> where T:IComparable<T>
{

}

...

The interface provides so-called type safety when comparing values of some generic type T. The interface declares the CompareTo() method

int CompareTo()

which is used in our program in the Sort() and SortRange() methods (see sections 2.5, 2.6) to compare two values of some type T.

If you do not implement the IComparable<T> interface implementation in the SortSelection<T> class and write the class declaration as follows

...

class SortSelection<T>
{

}

...

then it will be impossible to compare the value of the generic type T, and the sorting methods will fail to be implemented. In this case, the usual comparison operations <, >, == do not provide type safety.

 

2. Development of the SortSelection<T> class
2.1. Entering the internal class variables

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

...

// Generalized class SortSelection<T> - implements the selection sorting algorithm
class SortSelection<T>
{
  // One-dimensional array with data to be sorted
  private T[] A;
}

...

 

2.2. Class constructors

At this stage, three constructors are introduced into the text of the SortSelection<T> class, initializing the internal data of the class (array A).

// Constructors.
// Constructor without parameters
public SortSelection()
{
  A = null;
}

// A constructor that receives an external array of type T[]
public SortSelection(T[] A)
{
  // Make a copy using the Clone() method
  this.A = (T[])A.Clone();
}

// Constructor that receives as input an instance of the SortSelection<T> class
public SortSelection(SortSelection<T> obj)
{
  A = (T[])obj.A.Clone();
}

 

2.3. Access methods Get(), Set()

To access the internal array A, you must implement the corresponding Get(), Set() accessor methods. Note that the accessors use array copying using the Clone() method. The Clone() method has the following features:

  • the method implements a copy of the array, allocating memory in a different area. Thus, the instance array A and the outer array are located in different memory locations. If instead of using the Clone() (A = _A.Clone()) method, you use simple reference assignment (for example, A = _A), then the outer and inner arrays will point to the same memory location. This can lead to invisible errors if changes in the external array affect the internal one (and vice versa), which is undesirable;
  • the method is declared in the System.Array class, which is the base for all arrays declared in the program. Therefore, this method is available in the program.
// Access methods.
// Get a copy of array A
public T[] Get()
{
  return (T[])A.Clone();
}

// Set a new value
public void Set(T[] _A)
{
  A = (T[])_A.Clone();
}

 

2.4. Method Sort(). Sort the entire array. Method CompareTo()

The main method of the class is the Sort() method, in which the entire array is sorted. The peculiarity of this method is that the CompareTo() method, which is declared in the IComparable<T> interface, is used to compare two values of the generic type T.

The CompareTo() method has the following declaration:

int CompareTo(T other);

here other is an instance (object) of generic type T.

The method compares the current instance with another object of the same type and returns an integer. This number determines whether the current instance comes before, after, or at that very position in the sort order, compared to other. If the method returns a number <0, then the value of the current instance comes before the value of the other (less than) object. If the method returns a number == 0, then the values are equivalent in terms of sort order. If the method returns a number >0, then the value of the current instance follows the value of the object other (greater than).

// Sorting methods
// A method that sorts the entire array.
// The order parameter sets the sort order,
// - if order=true, then sort in ascending order;
// - if order=false, then sort in descending order.
public void Sort(bool 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].CompareTo(t)<0)
        {
          k = j;
          t = A[j];
        }
      }
      else
      {
        // Finding the largest element
        if (A[j].CompareTo(t) > 0)
        {
          k = j;
          t = A[j];
        }
      }

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

 

2.5. Method SortRange(). Sorting an array in a given range

A modification of the Sort() method is the SortRange() method, which allows you to sort not the entire array, but part of it in the specified range.

// Method that implements the selection sorting algorithm in the specified range [pos1, pos2-1]
// Parameters:
// - order - sort order (true-ascending, false-descending);
// - pos1 - the lower bound of the index in the array, inclusive;
// - pos2 - the upper bound of the index is exclusive.
// If the sorting was successful, the function returns true, otherwise - false.
public bool SortRange(bool order, int pos1, int pos2)
{
  // Checking if the values pos1, pos2 are adequate
  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].CompareTo(t) < 0)
        {
          k = j;
          t = A[j];
        }
      }
      else
      {
        // Finding the largest element
        if (A[j].CompareTo(t) > 0)
        {
          k = j;
          t = A[j];
        }
      }

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

  return true;
}

 

2.6. Method Print(). Display the array

The Print() method prints the contents of the internal array A to the screen. The method is used for testing purposes.

// Displaying the internal array to the screen
public void Print(string comment)
{
  WriteLine(comment);
  for (int i = 0; i < A.Length; i++)
    Write("{0} ", A[i]);
  WriteLine();
}

 

3. Developing the Program class

The Program class contains a static main() function that demonstrates the use of the methods of the SortSelection<T> class.

// Program class - tests the operation of the SortSelection<T> class
class Program
{
  static void Main(string[] args)
  {
    // 1. Working with an array of int type
    // 1.1. Declare an array of integers
    int[] AI = { 3, 5, -1, 2, -4 };

    // 1.2. Create instance based on AI array
    SortSelection<int> objInt1 = new SortSelection<int>(AI);
    objInt1.Print("objInt1 before sorting");

    // 1.3. Sort array objInt1
    objInt1.Sort(true);
    objInt1.Print("objInt1 after sorting");

    // 1.4. Sort in the specified range [1, 2]
    objInt1.SortRange(false, 1, 3);
    objInt1.Print("objInt1.SortRange(false, 1, 3):");

    // 2. Working with an array of type string
    string[] AS =
    {
      "abcd",
      "fghi",
      "jklmn",
      "jprst",
      "Hello",
      "bestprog"
    };
    SortSelection<string> objString = new SortSelection<string>(AS);
    objString.Print("Before sorting: objString");

    objString.Sort(true); // sort strings ascending
    objString.Print("After sorting: objString");

    SortSelection<string> objString2 = new SortSelection<string>();
    objString2.Set(objString.Get());
    objString2.Print("objString2:");
  }
}

 

4. The text of the entire program (abridged version)

After processing all the previous points, a program is obtained, the abbreviated text of which is as follows.

// Developing a class that implements the selection sorting algorithm
using System;
using static System.Console;

namespace ConsoleApp10
{
  // The generalized class SortSelection<T> - implements the selection sorting algorithm.
  // To compare values, you need to implement the IComparable<T> interface.
  class SortSelection<T> where T:IComparable<T>
  {
    // One-dimensional array with data to be sorted
    private T[] A;

    // Constructors.
    // Constructor without parameters
    public SortSelection()
    {
      ...
    }

    // Constructor that receives an external array of type T[]
    public SortSelection(T[] A)
    {
      ...
    }

    // Constructor that receives an input instance of the SortSelection<T> class
    public SortSelection(SortSelection<T> obj)
    {
      ...
    }

    // Access methods.
    // Get a copy of array A
    public T[] Get()
    {
      ...
    }

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

    // Sort methods.
    // A method that sorts the entire array.
    public void Sort(bool order)
    {
      ...
    }

    // Method that implements the selection sorting algorithm in the specified range [pos1, pos2-1]
    public bool SortRange(bool order, int pos1, int pos2)
    {
      ...
    }

    // Displaying the internal array to the screen
    public void Print(string comment)
    {
      ...
    }
  }

  // Class Program - tests the operation of the SortSelection<T> class
  class Program
  {
    static void Main(string[] args)
    {
      ...
    }
  }
}

 

5. The result of the program
objInt1 before sorting
3 5 -1 2 -4
objInt1 after sorting
-4 -1 2 3 5
objInt1.SortRange(false, 1, 3):
-4 2 -1 3 5
Before sorting: objString
abcd fghi jklmn jprst Hello bestprog
After sorting: objString
abcd bestprog fghi Hello jklmn jprst

 


Related topics