Selection sort program in C++
In this post, you will learn to write a selection sort program using the C++ programming language.
In selection sort, elements are arranged in two parts- sorted one and unsorted one.
Selection sort is a simple sorting algorithm. In computer science, selection sort is an in-place comparison sorting algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty, and the unsorted part is the entire list. It has an O(n²) time complexity where, n is the total number of items in the list, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort.
In selection sort elements are arranged in two parts - sorted one and unsorted one.
At first, the sorted part is empty, and the unsorted part contains all the elements. At every step, the algorithm finds the minimal element from an unsorted part and placed it at the end of the sorted part. In the last part of the process, the unsorted part becomes empty and the sorted part contains all the elements in sorted order.
Selection Sort Example
These are the selection sorting techniques.
Search for the element that is less than the first element. A[2] < A[0] so interchange them.
Next, search for the next element that is less than the second element. A[2] < A[1] so interchange them.
Next, search for the next element that is less than the third element. A[4] < A[2] so interchange them.
Next, search for the next element that is less than the fourth element. A[5] < A[4] so interchange them.
Next, search for the next element that is less than the fifth element. A[5] < A[4] so interchange them.
Selection Sorting Algorithm
for i <- 1 to n-1 do
min <- i;
for j <- i+1 to n do
if A[j] < A[i] then
min <- j
if min!= i then
temp <- A[i]
A[i] <- A[min]
A[min] <- temp
Program1: Selection sort in C++ using user inputs
#include<iostream>
using namespace std;
int main()
{
int i,j,n,loc,temp,min,arr[10];
cout<<"Enter the number of elements: ";
cin>>n;
cout<<"\nEnter the elements: \n";
for(i=0;i>>arr[i];
}
for(i=0;iarr[j])
{
min=arr[j];
loc=j;
}
}
temp=arr[i];
arr[i]=arr[loc];
arr[loc]=temp;
}
cout<<"\nSelection Sorted List: \n";
for(i=0;i<<arr[i]<<" ";
}
return 0;
}
Output of the above code:
Enter the number of elements: 6
Enter the elements:
78 33 53 32 89 63
Selection Sorted List:
32 33 53 63 78 89
Program2: Selection sort in C++ using functions
#include <iostream>
using namespace std;
// Swap two variables
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// function to print an array
void printArray(int arr[], int size) {
for (int x = 0; x < size; x++) {
cout << arr[x] << " ";
}
cout << endl;
}
void selectionSort(int arr[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
if (arr[i] < arr[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&arr[min_idx], &arr[step]);
}
}
// driver code
int main() {
int data[] = {67, 32, 44, 90, 43, 49};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
cout << "Sorted Array:\n";
printArray(data, size);
}
Output of the above code:
Sorted Array:
32 43 44 49 67 90
Related Articles
Queue implementation in c++Queue using linked list c++
Swapping of two numbers in C++
Generate random numbers in C++
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to find greatest of three numbers
C program for addition of two numbers
C program to calculate compound interest
C program to find the ASCII value of a character
C program to convert Decimal to Octal
C program to convert decimal to binary
Write a C program to calculate Simple Interest
C program to check whether a number is even or odd
C program to reverse a number
C program to check palindrome number
C program to check whether an alphabet is a vowel or consonant
Program to find square root of a number in C
C program to check whether a number is positive or negative