[ DS with Java ] Section 4.1 : Selection Sort

Preface : 
Array-based sorting algorithm deal with a sequence of elements in a list and use some rearrangement strategy to order the elements. We begin with a very simple example, called the selection sort, that proceeds through the list position by position. Let use illustrate these ideas with a discussion of the selection sort algorithm. A sample problem has us arranging an array of four animals in ascending order of their size : 
 

Ps. Selection sort passes through the list and exchanges the smallest element with the first element. I then passes through the remaining elements and exchanges the second smallest element with the second element and so forth.

Selection Sort Algorithm : 
We develop the selection sort algorithm for an array of n elements. The resulting list is in ascending order with : 
arr[0] <= arr[1] <= arr[2] ... <= arr[n-2] <= arr[n-1] 

The algorithm starts at index 0 and determines the position of the smallest element in the list. An exchange swaps the element at the position with arr[0] and leaves the rest of the list in unsorted order. Take some procedure on the rest of the list until the index reaches the end of the list. 
Let's assume arr is an integer array with n=5 elements having values {50, 20, 40, 75, 35}. Below figure displays how we sort the list with selection sort algorithm : 
 

The SelectionSort Method : 
The static method selectionSort() in the class Arrays implements the algorithm for an integer array. Its signature includes the array arr as the parameter. The implementation of the method consists of nested for-loops. The outer loop establishes the n-1 passes over the array where n is the length of the array. The control variable, called pass, ranges from 0 to n-2, For each iteration, an inner loop scans the unordered sub-list arr[pass] to arr[n-1] and assigns to the variable smallIndex the position of the smallest element. An exchange between arr[pass] and arr[smallIndex] complete the iteration and places element arr[smallIndex] to its correct position in the final sorted list. 

- Arrays.java 代碼 :

view plaincopy to clipboardprint?

1. public class Arrays {  
2.     public static void selectionSort(int[] arr) {  
3.         int smallIndex, tmp;  
4.         int pass, n = arr.length;  
5.         // pass has the range 0 to n-2  
6.         for(pass=0; pass<=n-2; pass++) {  
7.             smallIndex = pass;  
8.             for(int i=pass; i<=n-1; i++) {  
9.                 if(arr[i]
10.                     smallIndex = i;  
11.                 }  
12.             }  
13.             if(smallIndex!=pass){  
14.                 tmp = arr[pass];  
15.                 arr[pass] = arr[smallIndex];  
16.                 arr[smallIndex] = tmp;  
17.             }  
18.         }  
19.     }  
20.       
21.     public static void main(String args[]) {  
22.         // declare an integer array  
23.         int[] arr = {66, 20, 33, 55, 53, 57, 69, 11, 67, 70};  
24.         Arrays.selectionSort(arr);  
25.         System.out.print("Sorted: ");  
26.         for(int i=0; i
27.             System.out.print(arr[i]+" ");  
28.     }  
29. }  

Output :
Sorted: 11 20 33 53 55 57 66 67 69 70

Supplement : 
* [ 資料結構 小學堂 ] 排序 : 選擇排序法