Monday, September 30, 2013

Sorting algorithm refreshers......Selection Sort!

So post two of sorting algorithm refreshers. This time it's Selection Sort with the same crappy O(n^2) growth rate but with possibly less swaps.

  1. Start an outer loop from the start of the array counting till the end of the array
  2. Start an inner loop starting from the outer loops counter and going till the end of the array
  3. Using the inner loop keep track of the smallest/largest value
  4. After inner loop is complete swap the smallest value you found with the contents that is pointed to from the index of the outer loop
#include

int main(void) {
    
    int list[] = { 3, 4, 1, 10, 23, 40, 2, 9};
    
    int arr_length = sizeof(list)/sizeof(list[0]);
    
    for(int i = 0; i < arr_length; ++i){        
        
        
        int min = i;
        for( int j = i+1; j < arr_length; ++j) {
            
            if( list[j] < list[min]) {
                min = j;
            }
        }
        
        if ( min != i) {
            
            int temp = list[i];
            list[i] = list[min];
            list[min] = temp;
        }
       
        
    }
    
    for( int i = 0; i < arr_length; ++i) {
        printf("%d ", list[i]);
    }
    
    printf("\n");
    
}

No comments:

Post a Comment