Selection Sort Dynamic Array in C++

Introduction

In this lab, you will learn to perform selection sort to sort an unsorted dynamic array in C++ using the selection sort algorithm.

Create a new C++ file

First, create a new C++ file named main.cpp in the ~/project directory.

touch ~/project/main.cpp

Implement the Selection Sort Algorithm

The selection sort algorithm works by selecting the minimum element and placing it at the beginning of the array, then selecting the next minimum element from the rest of the array and placing it at index 1, and so on until the array is fully sorted. Here's how to implement the selection sort algorithm in C++:

#include <iostream>
using namespace std;

// function to swap the position of two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// function to perform the selection sort algorithm
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}

In this code block, we define a function swap() to swap the position of two elements in the array, and a function selectionSort() to perform the selection sort algorithm on the array.

Input the Array

In this step, you will input the dynamic array that needs to be sorted. You can do this by prompting the user to enter the elements of the array one by one:

// driver code
int main() {
  int size;
  cout<<"Enter the size of the array: ";
  cin>>size; //input the size of array
  int* data = new int[size]; //Dynamically declare array

  // Input the elements of the array one by one
  for(int i = 0; i < size; i++) {
    cout<<"Enter element "<<i+1<<" : ";
    cin>>data[i];
  }

Perform Selection Sort

Now that we have the unsorted array, we can perform the selection sort algorithm on it using the selectionSort() function we defined earlier. Here's how to do it:

  // Perform selection sort
  selectionSort(data, size);

Output the Sorted Array

Finally, we will output the sorted array to the console using a loop in a function called printArray(). Here's how to do it:

  // Output the sorted array
  cout << "\nSorted array: ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // Free memory used by the dynamic array
  delete[] data;
  return 0;
}

Compile and Run the Code

To compile and run the code, open the terminal and navigate to the folder where your main.cpp file is stored. Then execute the following commands:

g++ main.cpp -o main
./main

The sorted array should be displayed in the console.

Summary

In this lab, you have learned how to use the selection sort algorithm to sort an unsorted dynamic array in C++. To do so, you had to input the array, implement the selection sort algorithm, perform the sort, output the sorted array, and then compile and run the code in the terminal. With these skills, you will be able to sort arrays of any size using selection sort.