1.2 Selection Sort

❮ Python Dynamic Var Java Inner Class Summary ❯

1.2 Selection Sort

Category Algorithm

Selection sort is a simple and intuitive sorting algorithm that has a time complexity of O(n²) regardless of the data inputted. Therefore, it is best used when the data set is as small as possible. The only advantage might be that it does not occupy additional memory space.

1. Algorithm Steps

First, find the minimum (maximum) element in the unsorted sequence and place it at the beginning of the sorted sequence.

Then, continue to find the minimum (maximum) element from the remaining unsorted elements and place it at the end of the sorted sequence.

Repeat the second step until all elements are sorted.

2. Animation Demonstration

Code Implementation

JavaScript Code Implementation

Example

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) { // Find the smallest number
                minIndex = j; // Save the index of the smallest number
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

Python Code Implementation

Example

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # Record the index of the smallest number
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # If i is not the smallest number, swap i and the smallest number
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

Go Code Implementation

Example

func selectionSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length-1; i++ {
        min := i
        for j := i + 1; j < length; j++ {
            if arr[min] > arr[j] {
                min = j
            }
        }
        arr[i], arr[min] = arr[min], arr[i]
    }
    return arr
}

Java Code Implementation

Example

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // A total of N-1 rounds of comparison are needed
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // Each round requires N-i comparisons
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // Record the index of the currently found minimum value element
                    min = j;
                }
            }

            // Swap the found minimum value with the value at position i
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

PHP Code Implementation

Example

function selectionSort($arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

C Language

Example

void swap(int *a, int *b) // Swap two variables
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i, j;

    for (i = 0; i < len - 1; i++)
    {
        int min = i;
        for (j = i + 1;
if (i != min){
    array.swap(i, min);
}
return array;
}

** SNK2345

** 239***[email protected]

-

** kezhuoquan

** kez***[email protected]

The Rust implementation is as follows:

fn selection_sort<T:Ord + Debug>(array: &mut [T]) { for i in 0..array.len() { let mut temp = i; for j in i..array.len() { if array[j] < array[temp] { temp = j; } } array.swap(i, temp); } }

```

** kezhuoquan

* kez**[email protected]

** Click to share notes

Cancel

-1.0 Top 10 Classic Sorting Algorithms

-1.1 Bubble Sort

1.2 Selection Sort

WeChat Follow

❮ Python Dynamic Var Java Inner Class Summary ❯