Last active
June 1, 2021 18:22
-
-
Save msmoiz/4a81b2375288948f9ff6582897d5c117 to your computer and use it in GitHub Desktop.
Selection Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template<typename T> | |
void exchange(Vector<T>& list, int i, int j) | |
{ | |
T temp = list[i]; | |
list[i] = list[j]; | |
list[j] = temp; | |
} | |
/** | |
* In a typical selection sort (a simple, but inefficient | |
* sort method), the sort is conducted in place by | |
* iterating over each item in the list. | |
* At each item, assume it is the minimum until proven wrong. | |
* Find the minimum of remaining items, and swap it into the | |
* current slot. By the end, all items will be in place. | |
* This sort exhibits quadratic time complexity (O(n2)) | |
* because it has two inner loops. | |
*/ | |
template<typename T> | |
void selection_sort(vector<T>& list) | |
{ | |
for (int i = 0; i < list.size(); ++i) // Iterate each item | |
{ | |
int min = i; | |
for (int j = i + 1; j < list.size(); ++j) // At each step, find the minimum remaining item | |
{ | |
if (list[j] < list[min]) | |
{ | |
min = j; | |
} | |
} | |
exchange(list, i, min); // Place it at the ith lowest position of the list | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment