C++ Coding Test Course, Selection Sort

Problem Description

Write a function to sort a given integer array in ascending order. The sorting algorithm to be used is Selection Sort.

Input

The first line contains an integer N. (1 ≤ N ≤ 1000)
The second line contains N integers. (Integer A[i] is -10000 ≤ A[i] ≤ 10000)

Output

Output the sorted array in ascending order in a single line, separated by spaces.

Concept Review of Selection Sort

The selection sort is one of the simplest sorting algorithms. It works by finding the smallest value in the given list and swapping it with the value at the front. This process is repeated until the list is sorted.

Process of Selection Sort

Find the smallest value in the current list.
Swap that value with the value at the current position.
Repeat steps 1 and 2 to sort the list.

Problem-Solving Process

1. Understanding for Problem Solving

To solve the problem, we start by finding the smallest value in the array and placing it at the front, then we find the next smallest value and place it in the second position. This process is repeated for the length of the array, and we need to search the remainder of the array to find the smallest value at each step.

2. Implementation of Selection Sort Algorithm

Now let’s implement the selection sort algorithm in C++. First, we will take the input for the array, then apply the selection sort algorithm to sort it, and finally print the result.


#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Set the current position as the index of the minimum value
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // If a minimum value is found
            }
        }
        // Swap the current position with the minimum value's position
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    selectionSort(arr, n);

    for(int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

3. Code Explanation

Let me explain each part of the code.

void selectionSort(int arr[], int n): This function performs selection sort. It takes an array and its size as parameters.
for (int i = 0; i < n - 1; i++): Iterates through the array to perform sorting.
int minIndex = i;: Initializes the index of the minimum value at the current index.
if (arr[j] < arr[minIndex]): Updates the new minimum value’s index if the current value is smaller than the minimum value.
int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;: Swaps the value at the current index with the value at the minimum value’s index.

4. Example Execution

Below is an example execution of the selection sort algorithm. First, we input N and the array values.


Input:
5
64 25 12 22 11

Output:
11 12 22 25 64

Time Complexity

The time complexity of selection sort is O(N²). It requires two nested loops since we need to traverse all the elements to find the minimum value. Thus, performance can degrade with a large amount of data.

Conclusion

In this post, we implemented selection sort using C++ and learned the basic concepts of sorting algorithms. Although selection sort is simple, it is not very efficient, so we should consider other sorting algorithms for larger datasets.

Additional Resources

Many sorting algorithms exist beyond selection sort. It is recommended to learn the following algorithms:

Bubble Sort
Insertion Sort
Merge Sort
Quick Sort

If you want to learn more about algorithms and data structures, please refer to the following resources: