Selection sort

From TheBestLinks.com

Selection sort is a sort algorithm that works as follows:

find the minimum value in the list
swap it with the value in the first position
find the minimum value amongst the remaining values
swap it with the value in the second position
repeat until the list is sorted

If you had to invent a sort algorithm on your own, you'd probably write an algorithm similar to selection sort because it is probably the more intuitive and immediate to invent.

An evolution of selection sort remembers the index of the minimum element that it finds in each pass. At the end of each pass it makes one exchange. This is more efficient because it reduces the total number of swaps, which cannot be bigger than the number n of elements to sort.

The na�ve algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n²), assuming that comparisons can be done in constant time. Thus it is outperformed on almost-sorted lists by insertion sort.

Heapsort greatly improves the basic algorithm by using a heap data structure to speed up finding and removing the lowest datum.

Implementations of the basic Selection Sort

Implementation in C:

for(i=0 ; i<n-1 ; i++)
{
   for(j=i+1 ; j<n ; j++)
   {
      if(x[i] > x[j])
      {
         temp=x[j];
         x[j]=x[i];
         x[i]=temp;
      }
   }
}

Implementation in Basic:

For i = 1 To n - 1
   For j = i + 1 To n
      If x(i) > x(j) Then
         temp = x(i)
         x(i) = x(j)
         x(j) = temp
      End If
   Next j
Next i

Implementations of the evoluted Selection Sort

Implementation in C:

int find_min_index (float [], int, int);
void swap (float [], int, int);
 
/* selection sort on array v of n floats */
 
void selection_sort (float v[], int n) {
  int  i;
 
  /* for i from 0 to n-1, swap v[i] with the minimum
   * of the i'th to the n'th array elements
   */
  for (i=0; i<n; i++) 
    swap (v, i, find_min_index (v, i, n));
} 
 
/* find the index of the minimum element of float array v from
 * indices start to end
 */
int find_min_index (float v[], int start, int end) {
  int  i, mini;
 

  mini = start;
  for (i=start+1; i<end; i++) 
    if (v[i] < v[mini]) mini = i;
  return mini;
}
 
/* swap i'th with j'th elements of float array v */
void swap (float v[], int i, int j) {
  float	t;
 
  t = v[i];
  v[i] = v[j];
  v[j] = t;
}

Implementation in Java:

   public static void selectionSort (int[] numbers)
   {
      int min, temp;

      for (int index = 0; index < numbers.length-1; index++)
      {
         min = index;
         for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
               min = scan;

         // Swap the values
         temp = numbers[min];
         numbers[min] = numbers[index];
         numbers[index] = temp;
      }
   }

de:SelectionSort fr:Tri par s�lection ja:選択ソート

Discussion

Last posted 0 of 0 messages

[no messages posted yet]

>> post message >>

Watch

You can add this article to your own "watchlist" and receive e-mail notification about all changes in this page.

Retrieved from "http://www.thebestlinks.com/Selection_sort.html"

Categories: Sort algorithms