Data Structure: How to implement Straight Selection Sort in C++?

In selection sort,

  • In each pass smallest/largest element is selected and placed in a sorted list.
  • Th entire array is divided into two parts: sorted and unsorted
  • In each pass, in the unsorted subarray, the smallest element is selected and exchanged with the first element.

Algorithm

1. Declare and initialize necessary variables such as array[], i, j, large, n etc.
2. for ( i = n – 1; i > 0; i–), repeat following steps
large = x[0];
index = 0;
2.1 for(j = i ; j <= i; j++)
if x[j] > large
large = x[i]
index = j
2.2 x[index] =x[i]
x[i] = large
3. Display the sorted array

 

Source Code:

Output:

How many elements? 6
Insert array of element to sort: 78 56 110 12 56 26
The sorted list is 12 26 56 56 78 110

Efficiency of Straight selection sort

 

 

In this first pass, it makes (n – 1) comparisons, in second pass it makes (n – 2) comparisons and so on, So total number of comparisons is n(n-1)/2 which is O(n^2)

SHARE Data Structure: How to implement Straight Selection Sort in C++?

You may also like...

1 Response

Leave a Reply

Your email address will not be published. Required fields are marked *

Share