Sorting: Selection Sort
13th January 2006 - By Paradochs
Information
- Order: O(n²)
- Best Case: O(n²)
- Average: O(n²)
- Memory Usage: O(1)
- Stable: No
- Comparison Based: Yes
Description (from wikipedia)
Selection sort is a sort algorithm, a comparison sort that works as follows:
- find the minimum value in the list
- swap it with the value in the first position
- sort the remainder of the list (excluding the first value)
It is probably the most intuitive sort algorithm to invent.
This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time. Among simple O(n2) algorithms, it is generally outperformed by insertion sort, but still tends to outperform contenders such as bubble sort and gnome sort.
Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), this algorithm is stable (but slower).
Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum.
A bidirectional variant of selection sort, called shaker sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. Note, however, that shaker sort more often refers to a bidirectional variant of bubble sort.
C++ Files and Code Listing
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:9 Feb 05
File: SelectionSort.h
*/
#include <time.h>
class SelectionSort {
public:
SelectionSort();
SelectionSort(int *, int);
~SelectionSort();
int * getArray();
int getN();
bool getSorted();
double getTime();
long int getIncrements();
void setArray(int *);
void sort();
private:
void setN(int);
void setSorted(bool);
void resetTime();
void resetIncrements();
int * A;
int n;
bool sorted;
double time;
long int increments;
};
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:16 Feb 05
File: SelectionSort.cpp
*/
#ifndef SELECTIONSORT_H
#define SELECTIONSORT_H
#include "SelectionSort.h"
#endif
SelectionSort::
SelectionSort() {
n = 1;
A = new int[n];
A[0] = 0;
sorted = true;
}
SelectionSort::
SelectionSort(int * newArray, int N) {
n = N;
A = new int[n];
for(int i=0; i<n; i++)
A[i] = newArray[i];
sorted = false;
resetIncrements();
}
SelectionSort::
~SelectionSort() {
delete(A);
}
int *
SelectionSort::
getArray() {
return A;
}
int
SelectionSort::
getN() {
return n;
}
bool
SelectionSort::
getSorted() {
return sorted;
}
double
SelectionSort::
getTime() {
return time;
}
long int
SelectionSort::
getIncrements() {
return increments;
}
void
SelectionSort::
setArray(int * newArray) {
delete(A);
n = sizeof(newArray);
A = new int[n];
sorted = false;
}
void
SelectionSort::
sort() {
time_t t1, t2;
t1 = clock();
for(int i=0; i<n-1; i++) {
int k=i;
int key=A[i];
for(int j=i+1; j<n; j++) {
if(increments++, A[j]<key) {
k=j;
key=A[j];
}
}
A[k]=A[i];
A[i]=key;
}
t2 = clock();
time = (double)((t2 - t1)/CLOCKS_PER_SEC);
}
void
SelectionSort::
setN(int newN) {
n = newN;
}
void
SelectionSort::
setSorted(bool newSorted) {
sorted = newSorted;
}
void
SelectionSort::
resetTime() {
time = 0.0;
}
void
SelectionSort::
resetIncrements() {
increments = 0;
}