The main idea of the algorithm is quite simple as follows. The input data array is divided to two imaginary parts, sorted and unsorted. Initially the sorted part is empty. The algorithm searches for the smallest element of the unsorted part and adds it to the end of the sorted part. When the unsorted part becomes empty algorithm stops. However Selection sort is inefficient in sorting large sets.
Worst case performance - O(n^2)
Source - Quazoo |
C++
void selection_sort(int array[], int length)
{
for (int j = 0; j < length - 1; j++)
{
int min = j;
for (int i = j + 1; i < length; i++)
{
if (array[i] < array[min])
{
min = i;
}
}
if (min != j)
{
int temp = array[j];
array[j] = array[min];
array[min] = temp;
}
}
}
Java
Matlabpublic int[] selection_sort(int[] array) {
for (int j = 0; j < array.length - 1; j++) {
int min = j;
for (int i = j + 1; i < array.length; i++) {
if (array[i] < array[min]) {
min = i;
}
}
if (min != j) {
int temp = array[j];
array[j] = array[min];
array[min] = temp;
}
}
return array;
}
function array = selection_sort(array)Python
length = numel(array);
for i = (1:length-1)
min = i;
for j = (i+1:length)
if array(j) <= array(min)
min = j;
end
end
if i ~= min
array([min i]) = array([i min]);
end
end
end
def selection_sort(array):
for j in range(len(array)-1):
min = j
for i in range(j+1,len(array)):
if array[i] < array[min]:
min = i
if min != j:
temp = array[j]
array[j] = array[min]
array[min] = temp
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.