Selection Sort

A Selection sorting technique uses a general algorithm which uses an ascending or descending priority queue. The idea would be to pre-process input array X[i] into the descending or ascending priority queues by the functions dpqinsert(dpq, x) or apqinsert(apq, x) respectively. Now, the next and final step would be to select data in appropriate order from the priority queue and store in appropriate order from the priority queue and store in X[i]. Thus the algorithm for an ascending order selection sorting is as follows –

/* empty the ascending pq, apq */

/* insert each element of X[i] to apq */

for (i = 0; i<n; i++){

apqinsert(apq, X[i])

}

/* select smallest from apq and store in X[i] */

for (i = 0; i<n; i++){

X[i] =  apqmindelete(apq);

}

Any data structure may be used to implement the priority queue. The order of selection sorting is O(n²).