Selection Sort

grasping the bytes > Information Visualization > Sort Algorithms Visualizer > Selection Sort - (fr)

menu

Sort Algorithms Visualizer

About sorting

> Sort algorithms

Instructions

Exercises

About the applet (source code).

Probably the most natural sort of all. My take is that 70% of newcomers faced to sorting an array will come up with this solution. This sort is the worst algorithms in numbers of comparisons: n(n+1)/2 compares in all cases. Yet is the most efficient of all the currently known algorithms in terms of exchanges: at most n-1 exchanges.

class SelectSort extends AlgoTri {
 SelectSort (int t, VueTris v) { super("Selection Sort", t, v); }
 public void sort () {
  for (int i = 0; i < size; i++) {
   int curmin = i;
   for (int j = i+1; j < size; j++) {
    if (compare(j, curmin)<0)
     curmin=j;
   }
   if (curmin != i)
    exchange(curmin, i);
  }
 }
};

Exercise (advanced):

Design a more efficient algorithm in numbers of exchanges, without sorting the array in a buffer, then making only requested changes. Hint: use statistics on the data distribution.