Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

selection sort
c++

How to implement selection sort in C++

Educative Answers Team

The Selection Sort algorithm is an in-place comparison-based algorithm. The idea behind it is to divide an array into two segments:

  • The sorted part at the left end.
  • The remaining unsorted part at the right end.

First, the algorithm finds either the minimum or the maximum element in our input array. Then, the algorithm moves this element to its correct position in the array.


How does the algorithm work?

To sort an array using Selection Sort, we must select the smallest element in the array.
1 of 7

Implementation

The algorithm is implemented in C++ in the following code snippet:

#include<stdio.h>
#include <iostream>
using namespace std;

int main ( )
{
	int data [] = { 6, 3, 5, 10, 2};
	int size = 5;

	cout<<"Unsorted Array: ";
	for( int i = 0; i < 5; i++)
		cout << data[i] << " "; 
	cout << endl;

	for (int i = 0; i < size -1; i++)
	{
		int minimum = i;
		for (int j = i+1; j < size; j++)
		{
			if (data[j] < data[minimum])
			{
				minimum = j;
			}
		}
		int temp = data[i];
		data[i] = data[minimum];
		data[minimum] = temp;
	}

	cout<<"Sorted Array: ";
	for( int i = 0; i < 5; i++)
		cout << data[i] << " "; 
	cout << endl;
	return 0;
}

Understanding the code

  • Lines 15-28: The first for loop traverses the whole of the array. Initially, it sets the minimum to be the index of the first element in the unsorted array.

  • Lines 18-24: The inner for loop traverses the remaining portion of the array to find its minimum value. Once complete, it swaps the minimum value, in the unsorted portion, with the first value of the same portion.

  • The algorithm repeats the procedure by moving to the next value in the list, and considering it to be the new minimum.


RELATED TAGS

selection sort
c++
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring