Algorithm Implementation/Sorting/Selection sort

Selection sort This article describes implementations of the selection sort sorting algorithm in a variety of real-world programming languages. 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 C/C++ void selection(int *array, int length) { int max, 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: int selectionSort(int data[], int count) { int i, j; int tmp; int minimum; 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; } return 0; } This is an implementation of the stable variant: void selectionSort(int data[], int count) { int i, 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_element template <typename Iterator> void selection_sort(Iterator begin, Iterator end) { Iterator min; while (begin != end) { min = std::min_element(begin, end); std::iter_swap(begin, min); ++begin; } } C# public void sortArray(int[] intArray) { int min, temp; for (int i = 0; i < intArray.Length - 1; i++) { min = i; for (int j = i + 1; j < intArray.Length; j++) if (intArray[j] < intArray[min]) min = j; // swap the values temp = intArray[i]; intArray[i] = intArray[min]; intArray[min] = temp; } } Java An iterative implementation: public static int[] selectionsort(int[] numbers) { for (int i = 0; i < numbers.length - 1; i++) { int index = i; for (int j = i + 1; j < numbers.length; j++) if (numbers[j] < numbers[index]) //Finds smallest number index = j; int smallerNumber = numbers[index]; //Swap numbers[index] = numbers[i]; numbers[i] = smallerNumber; } return numbers; } A recursive implementation: 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) { selectionSort(array, 0); } public static void selectionSort(int[] array, int left) { if (left < array.length - 1) { swap(array, left, findMin(array, left)); selectionSort(array, left+1); } } public static void swap(int[] array, int index1, int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } JavaScript function selectionSort (sortMe) { var i, 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 *) fun selection_sort [] = [] | selection_sort (first::lst) = let fun select_r small ([], output) = small::(selection_sort output) | select_r small (x::xs, output) = if (x< small) then select_r x (xs, small::output) else select_r small (xs, x::output) in select_r first (lst, []) end ; Ocaml (* Gets the minimum element of the list *) let rec min lst = match lst with x::[] -> x | (x::tl) -> let mintl = min tl in if x < mintl then x else mintl;; (* Removes a given element from the list *) let rec remove(x,lst) = match lst with [] -> [] | (y::tl) -> if x=y then tl else y::(remove(x,tl));; (* Sorts a list by repeatedly extracting the minimum *) let rec selectionSort(lst) = match lst with [] -> [] | _ -> let m = min lst in m::(selectionSort(remove(m,lst)));; Phix function selection_sort(sequence s) integer m for i=1 to length(s) do m = i for j=i+1 to length(s) do if s[j]<s[m] then m = j end if end for {s[i],s[m]} = {s[m],s[i]} end for return s end function PHP function selectionSort(&$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] for outer in range(len(newList)): minimum = min(newList[outer:]) #find minimum element minIndex = newList[outer:].index(minimum) #find index of minimum element newList[outer + minIndex] = newList[outer] #replace element at minIndex with first element newList[outer] = minimum #replace first element with min element print newList Ruby def sort!(keys) for i in 0..keys.size-2 min = i for j in i+1..keys.size-1 min = j if keys[j] < keys[min] end keys[i], keys[min] = keys[min], keys[i] end keys end it:Implementazioni di algoritmi/Selection sort