Saturday, January 24, 2015

Selection Sort

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)

selection sort
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
public 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;
}
Matlab
function array = selection_sort(array)
    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
Python
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.