Data structure and algorithm

em đang nói về lịch sử phát triển của thuật toán này ?

Lịch sử thì … chắc chả ai nhớ rồi.
Bạn có thể nhìn animation này để xem algorith: http://cse.iitkgp.ac.in/pds/notes/swf/selection.html

Animation của thuật toán selection sort:

toptal.com

Selection Sort - Sorting Algorithm Animations

Animation, code, analysis, and discussion of selection sort on 4 initial conditions.

Wiki:

Selection sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: the sublist of items already sort...

Thuật toán này có Oh(n^2) - worst case, Ohm(n^2) - best case và Theta(n^2) - average case (gọi là time complexity) nên khá chậm với các array lớn (và tạm chấp nhận được với các array nhỏ)

Như animation (link đầu tiên), bạn thấy thuật toán này khá đơn giản, nó sẽ tìm giá trị lớn nhất (hoặc nhỏ nhất) và move xuống cuối (hoặc đầu). Khi move, nó sẽ swap cái vị trí cuối đó.

Ví dụ như thế này:
Có mảng 15, 23, 12, 4 (mảng 4 giá trị)
Nó scan tìm giá trị lớn nhất, ở đây là 23 -> move xuống cuối
Giờ mảng chuyển thành 15, 4, 12, 23 (4 được swap với 23 vì 23 nó xuống cuối, chiếm vị trí của 4 rồi)
Giờ nó scan trong mảng con: 15, 4, 12, tìm giá trị lớn nhất, ra số 15, chuyển xuống dưới cùng của mảng con, tức là swap với số 12
Giờ mảng là 12, 4, 15, 23
Nó lại scan trong mảng con 12, 4 tìm giá trị lớn nhất là 12 và swap tiếp vowsi4
Giờ mảng là 4, 12, 15, 23. Mảng con có size = 1 thì k cần sort nữa.

dạ đúng rồi anh cái thuật toán này do ai sáng tạo ra

theo mình nghĩ thì selection sort nó được mô phỏng từ việc mà con người làm hàng ngày, như sắp xếp các lá bài, xếp hàng theo thứ tự trong trường học,… cho nên có thể nói là không có ai phát minh (sáng tạo) ra nó cả