Page 222 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

Now let us see the step by step example: Notes

Example: Having the following list, let’s try to use selection sort to arrange the numbers
from lowest to greatest:
6, 3, 5, 4, 9, 2, 7.

First run:
2, 3, 5, 4, 9, 6, 7 (2 was the smallest number and 6 which was the first element were swapped)
Second run:
2, 3, 4, 5, 9, 6, 7 (4 and 5 were swapped, as 3 was already on the good position, with no other
element being smaller)
Third run:
2, 3, 4, 5, 6, 9, 7 (6 and 9 were swapped, 5 was already in the good position)
Forth run:

2, 3, 4, 5, 6, 7, 9 (7 and 9 were swapped)
Fifth run:
2, 3, 4, 5, 6, 7, 9 (no swap)

Sixth run:
2, 3, 4, 5, 6, 7, 9 (no swap)
Even though in the last two runs there were no swaps, the algorithm still makes passes, of a total
of n – 1 passes, where n is the number of elements.
2
The big-O notation for this algorithm is of O(n ), which is of the same order as the insertion sort.
!
Caution The condition of applying these sorting algorithms is dependent on speeds of
comparison associated with data moving.
The below is an implementation of the algorithm in C.
#include < iostream >
using namespace std;
int main()
{
long int n=100;
long int a[100];
cout << “Please insert the number of elements to be sorted:”;
cin >> n; // The total number of elements
for(int i=0;i < n;i++)
{
cout << “Input” << i << “ element:”;
cin >> a[i]; // Adding the elements to the array
}

LOVELY PROFESSIONAL UNIVERSITY 215