Selection sort algorithm (Selection Sort)

What is Selection Sort?

Selection Sort is a simple algorithm. This sorting algorithm is an algorithm based on in-place comparison, in which the list is divided into two parts, sorted (list) on the left and unsorted (unsorted list) in the right. Initially, the sorted part is blank and the unordered part is the original list.

The smallest element selected from the array has not been sorted and is swapped with the most left part and that element becomes the element of the sorted array. This process continues until all of the unmatched array elements are moved to the sorted array.

This algorithm is not suitable for large data sets where the worst case complexity and the average case for O (n2) with n are the number of elements.

You learn the in-place concept in chapter: Some basic concepts about sorting algorithms.

Selection sort works (Selection Sort) works

Below are illustrations of how the algorithm works. Suppose we have an array as follows:

Selection sort algorithm (Selection Sort) Picture 1

From the first position in the list has been sorted, the entire list is approved continuously. The first position has a value of 14, we find the entire list and find that 10 is the smallest value.

Selection sort algorithm (Selection Sort) Picture 2

Therefore, we replace 14 with 10. After a loop, value 10 replaces the value 14 at the first position in the sorted list. We swap these two values.

Selection sort algorithm (Selection Sort) Picture 3

In second place, value 33, we continue to scan the rest of the list in order of each element.

Selection sort algorithm (Selection Sort) Picture 4

We see that 14 is the second smallest value in the list and it should appear in the second position. We swap these two values.

Selection sort algorithm (Selection Sort) Picture 5

After two loops, the two smallest values ​​have been placed at the beginning of the sorted list.

Selection sort algorithm (Selection Sort) Picture 6

The same process will apply to the rest of the list. The figures below illustrate these processes.

Selection sort algorithm (Selection Sort) Picture 7

Next we will monitor some other aspects of the selection algorithm.

Selection sort algorithm (Selection Sort)

 Bước 1 : Thiết lập MIN về vị trí 0 Bước 2 : Tìm kiếm phần tử nhỏ nhất trong danh sách Bước 3 : Tráo đổi với giá trị tại vị trí MIN Bước 4 : Tăng MIN để trỏ tới phần tử tiếp theo Bước 5 : Lặp lại cho tới khi toàn bộ danh sách đã được sắp xếp

Sample algorithm for sort selection

 B ắ t đầ u gi ả i thu ậ t s ắ p x ế p ch ọ n ( Selection Sort ) list : m ả ng c á c ph ầ n t ử n : k í ch c ỡ m ả ng for i = 1 t ớ i n - 1 /* thiết lập phần tử hiện tại là min*/ min = i /* kiểm tra phần tử có là nhỏ nhất không */ for j = i + 1 t ớ i n if list [ j ] < list [ min ] th ì min = j ; k ế t th ú c if k ế t th ú c for /* tráo đổi phần tử nhỏ nhất với phần tử hiện tại*/ if indexMin != i then tr á o đổ i list [ min ] v à list [ i ] k ế t th ú c if k ế t th ú c for K ế t th ú c gi ả i thu ậ t 

According to Tutorialspoint

Previous lesson: Insert algorithm (Insertion Sort)

Next lesson: Mixing algorithm (Merge Sort)