Selection Sort Algorithm

Selection Sort's philosophy most closely matches human intuition: It finds the largest element and puts it in its place. Then it finds the next largest and places it and so on until the array is sorted. To put an element in its place, it trades positions with the element in that location (this is called a swap). As a result, the array will have a section that is sorted growing from the end of the array and the rest of the array will remain unsorted.

for (i=n down to 1)
    max = a[1];
    max_pos = 1;
    for (j=1 to i-1)
	if (a[j] > max)
	    max = a[j];
	    max_pos = j;
    if (i != max_pos)
	swap(i,max_pos);

The inner loop of this algorithm is finding the position of the maximum element in the unsorted portion of the array. The variable max contains the value of the maximum element seen by the loop so far and max_pos contains the position that max element was seen at. When that loop finishes looking at the unsorted portion of the array, max and max_pos will refer to the true max in that portion of the array. The outer loop is keeping track of the next place the max should be swapped into.

The i, j, and max_pos variables are colored to match their colors in the animation. You will see the values these variables take on near the top of the animation.