#include <stdio.h> void p( int a[], int len ) { for( int i = 0; i < len - 1; i++ ) printf( "%d, ", a[i] ) ; printf( "%d\n", a[ len - 1 ] ) ; } int main() { int a[] = { 3, 6, 2, 11, 59, 5782, 2 } ; int len = sizeof(a) / sizeof(int) ; p(a, len) ; // selection sort // Imagine you have 6 pieces of pasta, all // of different lengths. // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // Now you want to put them in order of increasing height. // Here's what you do with selection sort. // You start at the very left side. // You pass through all sticks, // in the rest of the collection // LOOKING FOR THE SMALLEST ONE. // You identify the smallest one // as index 2. // | // | | // | | | | // | ||| | | // 0 1 2 3 4 5 // Swap with the item at index 0. // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // Now you are on index 1. You need to // pass through array elements 2-5 and // find the smallest one in THAT set // of the collection. // You identify the smallest as index 3. // swap. // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // Keep going. // 2 swaps with 3 // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // 3 swaps with 4 // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // 4 swaps with 5 // | // | | // | | | | // | | | | | | // 0 1 2 3 4 5 // and we're done ////////// // The algorithm. // We will walk through the array ONE TIME // from the first element to the SECOND LAST // element. We don't need to "sort" the very // last element. Think about it. for( int i = 0 ; i < len - 1 ; i ++ ) { // Now, at each element, we want to // find the SMALLEST ELEMENT TO THE // RIGHT OF IT, so we can swap the // current element (at i) with the // smallest element in the rest of the list. // set the mini = minimum index to be // ASSUMED to be the one immediately // to the right of the element we are // currently sorting. int mini = i + 1 ; // now, walk through the rest // of the list .. everything to the right // of the current element we are sorting // must be examined... NOTHING to the left // will be examined because that part // HAS ALREADY BEEN SORTED. // Once we reach the 3rd element, for example, // you should realize that THE FIRST 2 SLOTS // WILL ALREADY CONTAIN THE TWO SMALLEST // ELEMENTS IN THE WHOLE ARRAY. Take a // look at what this next loop does to understand // why. for( int j = i + 1 ; j < len ; j++ ) if( a[ j ] < a [ mini ] ) // if this jth element is smaller than the smallest we found so far mini = j ; // then set the smallest to being j // swap a[ i ] with the SMALLEST ELEMENT // we could find int tmp = a[ i ] ; a[ i ] = a[ mini ] ; a[ mini ] = tmp ; } p(a, len) ; }

Advertisements