Hỏi về quá trình phát triển của thuật toán Selection sort

#1

ai cso thể chỉ cho em biết QUÁ TRÌNH PHÁT TRIỂN của thuật toán SELECTION SORT

#2

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

#3

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:

Wiki:

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ỏ)

1 Like
#4

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.

1 Like
#5

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

#6

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ả :smile:

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?