Algorithm Implementation/Sorting/Selection sort

This article describes implementations of the selection sort sorting algorithm in a variety of real-world programming languages.

BASIC

Fori=1Ton-1min=iForj=i+1TonIfx(min)>x(j)Thenmin=jEndIfNextjtemp=x(i)x(i)=x(min)x(min)=tempNext

C/C++

voidselection(int*array,intlength){intmax,i,temp;while(length>0){max=0;for(i=1;i<length;i++)if(array[i]>array[max])max=i;temp=array[length-1];array[length-1]=array[max];array[max]=temp;length--;}}

C

This is an implementation of the unstable variant:

intselectionSort(intdata[],intcount){inti,j;inttmp;intminimum;for(i=0;i<count-1;i++){minimum=i;/* current minimum *//* find the global minimum */for(j=i+1;j<count;j++)if(data[minimum]>data[j])minimum=j;/* new minimum *//* swap data[i] and data[minimum] */tmp=data[i];data[i]=data[minimum];data[minimum]=tmp;}return0;}

This is an implementation of the stable variant:

voidselectionSort(intdata[],intcount){inti,j,m,mi;for(i=0;i<count-1;i++){/* find the minimum */mi=i;for(j=i+1;j<count;j++)if(data[j]<data[mi])mi=j;m=data[mi];/* move elements to the right */for(j=mi;j>i;j--)data[j]=data[j-1];data[i]=m;}}

C++

#include<algorithm> // for: std::iter_swap, std::min_elementtemplate<typenameIterator>voidselection_sort(Iteratorbegin,Iteratorend){Iteratormin;while(begin!=end){min=std::min_element(begin,end);std::iter_swap(begin,min);++begin;}}

C#

publicvoidsortArray(int[]intArray){intmin,temp;for(inti=0;i<intArray.Length-1;i++){min=i;for(intj=i+1;j<intArray.Length;j++)if(intArray[j]<intArray[min])min=j;// swap the valuestemp=intArray[i];intArray[i]=intArray[min];intArray[min]=temp;}}

Java

An iterative implementation:

publicstaticint[]selectionsort(int[]numbers){for(inti=0;i<numbers.length-1;i++){intindex=i;for(intj=i+1;j<numbers.length;j++)if(numbers[j]<numbers[index])//Finds smallest numberindex=j;intsmallerNumber=numbers[index];//Swapnumbers[index]=numbers[i];numbers[i]=smallerNumber;}returnnumbers;}

A recursive implementation:

publicstaticintfindMin(int[]array,intindex){intmin=index-1;if(index<array.length-1)min=findMin(array,index+1);if(array[index]<array[min])min=index;returnmin;}publicstaticvoidselectionSort(int[]array){selectionSort(array,0);}publicstaticvoidselectionSort(int[]array,intleft){if(left<array.length-1){swap(array,left,findMin(array,left));selectionSort(array,left+1);}}publicstaticvoidswap(int[]array,intindex1,intindex2){inttemp=array[index1];array[index1]=array[index2];array[index2]=temp;}

JavaScript

functionselectionSort(sortMe){vari,j,tmp,tmp2;for(i=0;i<sortMe.length-1;i++){tmp=i;for(j=i+1;j<sortMe.length;j++){if(sortMe[j]<sortMe[tmp]){tmp=j;}}if(tmp!=i){tmp2=sortMe[tmp];sortMe[tmp]=sortMe[i];sortMe[i]=tmp2;}}}

ML

(* Selection sort is modified slightly for use on linked lists (which are the only inbuilt array-like structures in ML) in a functional programming language *)funselection_sort[]=[]|selection_sort(first::lst)=letfunselect_rsmall([],output)=small::(selection_sortoutput)|select_rsmall(x::xs,output)=if(x<small)thenselect_rx(xs,small::output)elseselect_rsmall(xs,x::output)inselect_rfirst(lst,[])end;

Ocaml

(* Gets the minimum element of the list *)letrecminlst=matchlstwithx::[]->x|(x::tl)->letmintl=mintlinifx<mintlthenxelsemintl;;(* Removes a given element from the list *)letrecremove(x,lst)=matchlstwith[]->[]|(y::tl)->ifx=ythentlelsey::(remove(x,tl));;(* Sorts a list by repeatedly extracting the minimum *)letrecselectionSort(lst)=matchlstwith[]->[]|_->letm=minlstinm::(selectionSort(remove(m,lst)));;

Phix

functionselection_sort(sequences)integerm fori=1tolength(s)dom=i forj=i+1tolength(s)doifs[j]<s[m]thenm=j endifendfor{s[i],s[m]}={s[m],s[i]}endforreturns endfunction

PHP

functionselectionSort(&$a){$n=count($a);for($i=0;$i<$n-1;$i++){$min=$i;for($j=$i+1;$j<$n;$j++)if($a[$j]<$a[$min])$min=$j;list($a[$i],$a[$min])=array($a[$min],$a[$i]);}}

Python

newList=[6,7,4,5,1]forouterinrange(len(newList)):minimum=min(newList[outer:])#find minimum elementminIndex=newList[outer:].index(minimum)#find index of minimum elementnewList[outer+minIndex]=newList[outer]#replace element at minIndex with first elementnewList[outer]=minimum#replace first element with min elementprintnewList

Ruby

defsort!(keys)foriin0..keys.size-2min=iforjini+1..keys.size-1min=jifkeys[j]<keys[min]endkeys[i],keys[min]=keys[min],keys[i]endkeysend