Select sort

Summary

This chapter introduces the selective sorting in the sorting algorithm .

Catalog
1.  Introduction to selection sorting
2.  Select Sorting text description
3.  Time complexity and stability of selective sorting
4.  Choose Sort implementation
4.1  Selection sort C Realization
4.2  Selection sort C++ Realization
4.3  Selection sort Java Realization

Reprint please indicate the source ： Selection sort - If the sky doesn't die - Blog Garden

---

More ： Data structure and algorithm series Catalog

Introduction to selection sorting

Selection sort (Selection sort) It is a simple and intuitive sorting algorithm .
The basic idea is this ： First, find the smallest... In the unordered sequence (or Maximum ) Elements , Then store it at the beginning of the sequence ; next , Then continue to find the smallest element from the remaining unordered elements (or Maximum ) Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted .

Select Sorting text description

Select sort code

/*
 *  Selection sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void select_sort(int a[], int n)
{
    int i;        //  The end of the ordered area 
    int j;        //  The starting position of the disorder area 
    int min;    //  The position of the smallest element in the disordered region 

    for(i=0; i<n; i++)
    {
        min=i;

        //  find "a[i+1] ... a[n]" The smallest element between , And assign it to min.
        for(j=i+1; j<n; j++)
        {
            if(a[j] < a[min])
                min=j;
        }

        //  if min!=i, The exchange  a[i]  and  a[min].
        //  After the exchange , To ensure the a[0] ... a[i]  The elements between are ordered .
        if(min != i)
            swap(a[i], a[min]);
    }
}

The following is a sequence of numbers {20,40,30,10,60,50} For example , Demonstrate its selection sorting process ( Here's the picture ).

Sorting process

The first 1 Trip to ：i=0. find a[1...5] Minimum of a[3]=10, And then a[0] and a[3] swap . Sequence change ：20,40,30,10,60,50 -- > 10,40,30,20,60,50
The first 2 Trip to ：i=1. find a[2...5] Minimum of a[3]=20, And then a[1] and a[3] swap . Sequence change ：10,40,30,20,60,50 -- > 10,20,30,40,60,50
The first 3 Trip to ：i=2. find a[3...5] Minimum of , Because the minimum value is greater than a[2], This trip doesn't do anything .
The first 4 Trip to ：i=3. find a[4...5] Minimum of , Because the minimum value is greater than a[3], This trip doesn't do anything .
The first 5 Trip to ：i=4. In exchange for a[4] and a[5] The data of . Sequence change ：10,20,30,40,60,50 -- > 10,20,30,40,50,60

Time complexity and stability of selective sorting

Select sorting time complexity
The time complexity of sorting is O(N2).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ？N-1！ therefore , The time complexity of sorting is O(N2).

Select sort stability
Selective sorting is a stable algorithm , It satisfies the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Choose Sort implementation

Selection sort C Realization
Implementation code (select_sort.c)

/**
 *  Selection sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <stdio.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
#define swap(a,b) (a^=b,b^=a,a^=b)

/*
 *  Selection sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void select_sort(int a[], int n)
{
    int i;        //  The end of the ordered area 
    int j;        //  The starting position of the disorder area 
    int min;    //  The position of the smallest element in the disordered region 

    for(i=0; i<n; i++)
    {
        min=i;

        //  find "a[i+1] ... a[n]" The smallest element between , And assign it to min.
        for(j=i+1; j<n; j++)
        {
            if(a[j] < a[min])
                min=j;
        }

        //  if min!=i, The exchange  a[i]  and  a[min].
        //  After the exchange , To ensure the a[0] ... a[i]  The elements between are ordered .
        if(min != i)
            swap(a[i], a[min]);
    }
}

void main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    select_sort(a, ilen);

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Selection sort C++ Realization
Implementation code (SelectSort.cpp)

/**
 *  Selection sort ：C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 *  Selection sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void selectSort(int* a, int n)
{
    int i;        //  The end of the ordered area 
    int j;        //  The starting position of the disorder area 
    int min;    //  The position of the smallest element in the disordered region 

    for(i=0; i<n; i++)
    {
        min=i;

        //  find "a[i+1] ... a[n]" The smallest element between , And assign it to min.
        for(j=i+1; j<n; j++)
        {
            if(a[j] < a[min])
                min=j;
        }

        //  if min!=i, The exchange  a[i]  and  a[min].
        //  After the exchange , To ensure the a[0] ... a[i]  The elements between are ordered .
        if(min != i)
        {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

int main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    selectSort(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Selection sort Java Realization
Implementation code (SelectSort.java)

/**
 *  Selection sort ：Java
 *
 * @author skywang
 * @date 2014/03/11
 */

public class SelectSort {

    /*
     *  Selection sort 
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void selectSort(int[] a, int n) {
        int i;        //  The end of the ordered area 
        int j;        //  The starting position of the disorder area 
        int min;    //  The position of the smallest element in the disordered region 

        for(i=0; i<n; i++) {
            min=i;

            //  find "a[i+1] ... a[n]" The smallest element between , And assign it to min.
            for(j=i+1; j<n; j++) {
                if(a[j] < a[min])
                    min=j;
            }

            //  if min!=i, The exchange  a[i]  and  a[min].
            //  After the exchange , To ensure the a[0] ... a[i]  The elements between are ordered .
            if(min != i) {
                int tmp = a[i];
                a[i] = a[min];
                a[min] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20,40,30,10,60,50};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        selectSort(a, a.length);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The principle and output of the two implementations are the same . Here is their output ：

before sort:20 40 30 10 60 50 
after  sort:10 20 30 40 50 60