Hướng dẫn và mô phỏng thuật toán sắp xếp Selection Sort
Bài viết được sự cho phép của tác giả Phạm Công Sơn
Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn một phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
Các bước thực hiện thuật toán
1. Chọn phần tử đầu tiên i = 0
2. Tìm phần tử a[min] nhỏ nhất trong mảng từ a[i] tới a[n]. Với n là độ dài của mảng
3. Hoán đổi vị trí a[i] với a[min]
4. Tiếp tục chọn phần tử i = i + 1 và quay về bước 1
Mã nguồn được thực hiện trên javascript
Tạo dãy số ngẫu nhiên để mô phỏng sắp xếp
- 93
- 93
- 10
- 40
- 28
- 30
- 12
- 16
- 71
- 26
- ?
- ?
- ?
Mã nguồn được thực hiện trên javascript
var SelectionSort = function () { $.extend(this, new SortX()); this.name = "SelectionSort"; this.onCreateScripts = function (array, scripts) { var $this = this; var addScript = function (a1, a2, action) { scripts.push($this.createScript0(a1, a2)); // Script lấy ra 2 số cần so sánh scripts.push($this.createScript1(a1, a2)); // Script để thực hiện so sánh giữa 2 số return action(); } var min; for (var i = 0; i < array.length - 1; i++) { min = i; scripts.push(this.createScriptOneItem(array[min])); for (var j = i + 1; j < array.length; j++) { if (addScript(array[j], array[min], () => array[j].number < array[min].number)) { min = j; scripts.push(this.createScriptOneItem(array[min])); } } var b1 = array[i]; var b2 = array[min]; array[min] = b1; array[i] = b2; scripts.push(this.createScript2(b1, b2)); // Script thực hiện hoán đổi giữa 2 số với nhau. } } } var pageSortX = new PageSortX(); pageSortX.sortX = new SelectionSort(); pageSortX.start();
Chúc các bạn cuối tuần vui vẻ
Sơn 20
Bài viết gốc được đăng tải tại sonpc20.com
Có thể bạn quan tâm:
Xem thêm Việc làm Developer hấp dẫn trên TopDev
- i iOS 17.5 Beta 1 vừa được phát hành, những thay đổi nào đáng chú ý?
- i iOS 18 khi nào ra mắt? iOS 18 sẽ không hỗ trợ máy nào?
- V Về Logging: Mắt thần của bạn trên hệ thống thực
- M Middlewares – Sự tùy biến trong ứng dụng phần mềm
- Đ Đón đầu 7 xu hướng công nghệ hàng đầu trong năm 2024
- T Thực hiện “Chuẩn Hóa CV” nhận ngay quà hấp dẫn
- M METRO.digital Vietnam culture and ways of working
- G GW2790QT – Màn hình 2K tốt nhất dành cho lập trình viên
- S So sánh AWS, Google Cloud và Azure năm 2024
- D Data Analyst là gì? Chuyện nghề của một Data Analyst