Skip navigation

#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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: