**Selection Sort**

The selection sort
is a

**combination of searching and sorting**.
During each pass,
the unsorted element with the smallest (or largest) value is moved to its
proper position in the array. The number of times the sort passes through the
array is one less than the number of items in the array.

**The algorithm divides the input list into two parts:**

1.Sublist of items
already sorted, which is built up from left to right at the front (left) of the
list, and

2. Sublist of items
remaining to be sorted that occupy the rest of the list.

**Steps:**

Initially,
the sorted sublist is empty and the unsorted sublist is the entire input list.

1. Find
the smallest/largest (depending on sorting order) element in the unsorted
sublist.

2.
Exchanging (swapping) it with the leftmost unsorted element (putting it in
sorted order).

3. Moving
the sorted sublist boundaries one element to the right.

4. Repeat
steps 3 and 4.

**Example:**

This is the
initial, starting state of the array

Where the initial
sorted left sublist is empty.

65 38 22 25 14

14 65 38 22 25 //
sorted sublist = {14}

14 22 65 38 25 //
sorted sublist = {14, 22}

14 22 25 65 38 //
sorted sublist = {14, 22, 25}

14 22 25 38 65 //
sorted sublist = {14, 22, 25, 38}

14 22 25 38 65 //
sorted sublist = {14, 22, 25, 38, 65}

**SelectionSort.java**

public class SelectionSort {

public static void main(String[] args) {

int[] array = {64, 25, 12, 22, 11};

SelectionSort.

*sort*(array);
SelectionSort.

*printArr*(array);
}

**private**

**static**

**void**

**sort(**

**int**

**array[]) {**

**int**

**n = array.**

**length**

**;**

**int**

**idx,idxSorted;**

**// idxSorted: List sorted till this index**

**int**

**iMin;**// Min element index.

**for**

**(idxSorted = 0; idxSorted < n-1; idxSorted++) {**

**/* find the min element in the unsorted array[j .. n-1] */**

**/**Min index is the first element of unsorted list(default)*/**

**iMin = idxSorted;**

**for**

**( idx = idxSorted+1; idx < n; idx++) {**

**/****

* Find
minimum element index in Unsorted List.

*
Update the Minimum element index.

*/

**if**

**(array[idx] < array[iMin]) {**

**iMin = idx;**

**}**

**}**

**if**

**(iMin != idxSorted) {**

**/** swap(array[j]<-->array[iMin]) */**

**int**

**temp = array[idxSorted];**

**array[idxSorted] = array[iMin];**

**array[iMin] = temp;**

**}**

**}**

**}**

private static void printArr(int[] array) {

StringBuffer
sb = new StringBuffer();

for (int i : array) {

sb.append(i).append(" ");

}

System.

*out*.println(sb.toString());
}

}

**Output:**

11 12 22 25 64

## No comments:

## Post a Comment