Selection sort

Selection sort is a sort algorithm that works as follows:

  1. find the minimum value in the list
  2. swap it with the value in the first position
  3. sort the remainder of the list (excluding the first value)

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 most intuitive and immediate to invent.

This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time. It is generally out performed by insertion sort.

Selection sort is not a stable sort.

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


Implementations of Selection Sort

Implementation in C:

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

Implementation in Basic:

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

Implementation in Java (iterative):

   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;
      }
   }

Implementation in Java (recursive):

	// Selection sort for an array of ints
        public static int findMin(int[] array, int index)
	{ 
		int min = index - 1;
		if(index < array.length - 1) min = findMin(array, index + 1);
		if(array[index] < array[min]) min = index;
		return min;
	}
	
	public static void selectionSort(int[] array)
	{ 
		for(int left = 0; left < array.length - 1; left++)
		{
			swap(array, left, findMin(array, left));
		}
	}

	public static void swap(int[] array, int index1, int index2)
	{//swap the two values
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
de:Selectionsort

fr:Tri par slection lt:Išrinkimo rūšiavimo algoritmas ja:選択ソート pl:Sortowanie przez wybieranie pt:Selection sort

Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools