C++. Development of a class that implements the selection sorting algorithm

Search other websites:

1. Selection sorting algorithm. Implementation features

The selection sort algorithm is used for a one-dimensional array. Selection sort allows you to get a sorted sequence by attaching to it one element after another in the desired order.

At the first step of the algorithm, all elements of the sequence are considered. First, it searches for the position of the element with the minimum (maximum) value. The item at the found position is exchanged with the item at the first (zero) position.

In the second step, all elements of the sequence are considered except the first one, since the first element has already been placed. The element with the minimum (maximum) value is searched again, after which this element is exchanged with the element at the second position.

The process is repeated until a new sequence is formed. At each next step, one less element is considered.

If the elements of the sequence are sorted in ascending order, then at each step the search for the minimum element is performed. If the elements of the sequence are sorted in descending order, then the search for the maximum element is performed.

If an array of n elements is considered, then the number of steps of the algorithm is n-1. The performance of the algorithm is O(n²).

The advantages of the algorithm:

ease of implementation;
the implementation of the algorithm does not require the use of an additional array.

Disadvantages of the algorithm:

low performance. This algorithm is suitable for sorting arrays of small sizes.

The operation of the selection sorting algorithm is shown in Figure 1. An array of 7 integers is considered. The algorithm can be applied to any sequence of numbers.

Figure 1. The algorithm of selection sort. An example of sorting an array of 7 numbers

⇑

2. Task

Develop a generic class containing tools that implement the selection sorting algorithm. Demonstrate how the class works in the main() function.

⇑

3. Class development

3.1. Create a SortSelection class. Initial view of the Console Application type program

The first step in developing a program is to create a templated SortSelection class.

#include <iostream>
using namespace std;

// A templated class that implements the selection sorting algorithm in a one-dimensional array
template <class T>
class SortSelection
{

}

void main(void)
{

}

⇑

3.2. Entering internal variables

At this stage, hidden internal variables are introduced into the class:

array of generic type T;
the number of elements in the array count.

After entering the variables, the class text is as follows:

...

// A templated class that implements the selection sorting algorithm in a one-dimensional array
template <class T>
class SortSelection
{
private:
  T* A; // internal one-dimensional array
  int count; // the number of elements in the array
}

...

⇑

3.3. Internal method Copy() of the class. Copying data to an internal array

The most common operation in class methods is copying data from an external array to an internal array. To implement this operation, the internal Copy() method is introduced into the private section of the class. This method is called from the class constructor and from the Set() method.

The method text is as follows

// Internal method to copy external array to internal array A
void Copy(T* _A, int _count)
{
  // 1. Check if _count is correct
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  try
  {
    // 2. Set the new number of elements
    count = _count;

    // 3. Allocate memory for internal array A
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 4. Copy items A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

⇑

3.4. Class constructors

The class contains 3 constructors, which are located in the public section:

constructor without parameters. Creates an instance of a class with an empty (nullptr) array;
constructor with two parameters. Fills the internal array A with the data of the external array;
copy constructor. Called when one instance is initialized by another and when a class instance is returned from a method with a return operation. The need to use the copy constructor in such classes is described in detail here.

// Class constructors
// Constructor without parameters
SortSelection()
{
  A = nullptr;
  count = 0;
}

// Constructor that initializes internal data with an external array
SortSelection(T* _A, int _count)
{
  Copy(_A, _count); // copy data to internal array
}

// Copy constructor - redirect to constructor with 2 parameters
SortSelection(const SortSelection& obj) :SortSelection(obj.A, obj.count)
{
}

⇑

3.5. Methods to access the internal array Get(), Set()

In the public section, two methods (accessors) have been added to access the internal array A:

method Get() – used when it becomes necessary to get a reference (pointer) to the internal array A and also to determine the number of elements of this array;
method Set() is needed to fill the array A with new data.

// Access methods to internal array of SortSelection class
// Get the number of elements of array A and a pointer to array A
T* Get(int* _count)
{
  *_count = count;
  return A;
}

// Set new array in class instance
void Set(T* _A, int _count)
{
  // Free the memory previously allocated for array A
  if (count > 0)
  {
    delete[] A;
    count = 0;
  }

  // Copy A = _A
  Copy(_A, _count);
}

⇑

3.6. Operator function operator=(). Overloading the assignment operator

The operator function operator=() is called in cases when the program assigns one instance of a class to another instance

objA = objB;

This assumes that both instances are of the same type. The operator function operator=() is located in the public section and has the following implementation

// Operator function operator=() - necessary for assigning arrays
SortSelection& operator=(SortSelection& obj)
{
  // Invoke methods Set() of the class
  Set(obj.A, obj.count);

  // Return the current instance
  return *this;
}

⇑

3.7. Method Sort(). Sorting data

The main method of the class is the public method Sort(), which implements direct sorting of data in the array. The method implements an insertion sorting algorithm. The method receives one parameter, order, which determines the sort order of the items. If order=true, then sorting occurs in ascending order of elements. If order=false, then sorting occurs in descending order of elements.

The method text is as follows

// Sorting method Sort()
// Methods receives parameter order,
// - if order=true - sort Ascending,
// - if order=false - sorting in decreasing order.
void Sort(bool order)
{
  int i, j, k;
  T x;

  for (i = 0; i < count; i++) // i - step number
  {
    k = i;
    x = A[i];

    for (j = i + 1; j < count; j++)
      if (order)
      {
        if (A[j] < x) // smallest element search
        {
          k = j; // k - position of the smallest element in array A
          x = A[j];
        }
      }
      else
      {
        if (A[j] > x) // search the largest element
        {
          k = j; // k - the position of the largest element in the array A
          x = A[j];
        }
      }

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

⇑

3.8. Method Print(). Display the array

The Print() method is used to display data in array A.

// Method that prints the internal array to the screen
void Print(string comment)
{
  cout << comment << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << " ";
  cout << endl;
}

⇑

4. Testing the class. The main() method text

The main() method tests the operation of the methods of the SortSelection class.

The function text is as follows

void main(void)
{
  // Testing of SortSelection() class
  // 1. For array of type int
  // 1.1. Declare a variables
  int AI[] = { 2, 5, 1, 8, 3, 5, 4, 3, 7 };
  SortSelection<int> objInt(AI, 9);
  objInt.Print("objInt:");

  // Sort the array in descending order
  objInt.Sort(false);
  objInt.Print("objInt after sorting:"); // print the array

  // 1.2. Test of copy constructor
  SortSelection<int> objInt2 = objInt;
  objInt2.Print("objInt2:");

  // 1.3. Test of operator function operator=()
  SortSelection<int> objInt3;
  objInt3 = objInt;
  objInt3.Print("objInt3:");

  // 1.4. Test the Set() method
  int AI2[] = { 0,5,2,3,3,4,5 };
  objInt2.Set(AI2, 7);
  objInt2.Print("objInt2:");

  // 1.5. Test the Get() method
  int* AI3;
  int count3;
  AI3 = objInt3.Get(&count3);
  cout << "Array AI3:" << endl;
  for (int i = 0; i < count3; i++)
    cout << AI3[i] << " ";
  cout << endl;

  // 2. Testing for array of type char
  char AC[] = { 'a', 'f', 'c', 'x', 'w', 'p' };
  SortSelection<char> objChar;
  objChar.Set(AC, 6); // method Set()
  objChar.Print("objChar before sorting:");

  // Sort the array objChar
  objChar.Sort(false);
  objChar.Print("objChar after sorting:");
}

⇑

5. General structure of the program. Abridged version

By processing the previous steps, you can get a full-fledged SortSelection class that implements the insertion sort algorithm. The text of the entire program, which contains the SortSelection class and the main() function, is abbreviated below

#include <iostream>
using namespace std;

// A templated class that implements the selection sorting algorithm in a one-dimensional array
template <class T>
class SortSelection
{
private:
  T* A; // internal one-dimensional array
  int count; // number of items in the array

  // Internal method to copy external array to internal array A
  void Copy(T* _A, int _count)
  {
    ...
  }

public:
  // Class constructor
  // Constructor without parameters
  SortSelection()
  {
    ...
  }

  // Constructor initializing internal data with an external array
  SortSelection(T* _A, int _count)
  {
    ...
  }

  // Copy constructor
  SortSelection(const SortSelection& obj) :SortSelection(obj.A, obj.count)
  {
  }

  // Methods for accessing the internal array of the SortSelection class
  // Get the number of elements of array A and a pointer to array A
  T* Get(int* _count)
  {
    ...
  }

  // Set a new array in the class instance
  void Set(T* _A, int _count)
  {
    ...
  }

  // Destructor
  ~SortSelection()
  {
    ...
  }

  // Operator function operator=()
  SortSelection& operator=(SortSelection& obj)
  {
    ...
  }

  // Method Sort() - sorting
  void Sort(bool order)
  {
    ...
  }

  // Method that displays the array
  void Print(string comment)
  {
    ...
  }
};

void main(void)
{
  ...
}

⇑

6. The result of the program

After running for execution, the program will give the following result

objInt:
2 5 1 8 3 5 4 3 7
objInt after sorting:
8 7 5 5 4 3 3 2 1
objInt2:
8 7 5 5 4 3 3 2 1
objInt3:
8 7 5 5 4 3 3 2 1
objInt2:
0 5 2 3 3 4 5
Array AI3:
8 7 5 5 4 3 3 2 1
objChar before sorting:
a f c x w p
objChar after sorting:
x w p f c a

BestProg

C++. Development of a class that implements the selection sorting algorithm