Sắp xếp lựa chọn c ++
Thuật toán sắp xếp lựa chọn - Selection SortSắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con trong một mảng nhất định Diễn giải một cách đơn giản hơn thì thuật toán sắp chọn diễn ra như sau
Ví dụ sau giải thích các bước trên .arr [] = 64 25 12 22 11 // Tìm phần tử nhỏ nhất trong arr [0 .. 4] // và đặt nó ở đầu 11 25 12 22 64 // Tìm phần tử nhỏ nhất trong arr [1 .. 4] // và đặt nó ở đầu arr [1 .. 4] 11 12 25 22 64 // Tìm phần tử nhỏ nhất trong arr [2 .. 4] // và đặt nó ở đầu arr [2 .. 4] 11 12 22 25 64 // Tìm phần tử nhỏ nhất trong arr [3 .. 4] // và đặt nó ở đầu arr [3 .. 4] 11 12 22 25 64 Ví dụ sắp xếp lựa chọn trong C++ Hàm sắp xếp các lựa chọn sắp xếp void selectionSort ( int mảng[], < int n) { int i, j, min_index; // Di chuyển từng ranh giới của mảng con chưa sắp xếp cho (i = 0 ; i < n 1; i++) { // Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp min_index = i; cho (j = i+ 1 ; j < if (arr[j] < arr[min_index]) min_index = j; // Hoán đổi phần tử nhỏ nhất tìm được với phần tử đầu tiên hoán đổi (&arr[min_index], &arr[i]); } } Phân chia thuật toán- Trường hợp tốt nhất. 0 replacement (n-1 as in the code),  Như đã trình bày ở giải thuật Trao đổi Sắp xếp thì có rất nhiều giải thuật về bài toán sắp xếp nhưng giải thuật nào mang lại tính hiệu quả cao cho công việc cũng như dễ hiểu cho bạn đọc thì hôm nay chúng ta sẽ cùng tìm hiểu Ý tưởng Ý tưởng chính của thuật toán là xuất phát từ cuối dãy (hoặc đầu), đổi các cặp phần tử kế tiếp để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành . lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để kiểm tra thì dừng giải thuật Giải thuật Bước 1 tôi = 0 ; Bước 2 Tìm phần tử a[min] nhỏ nhất trong dãy hành động từ a[i] đến a[n] Bước 3 Use function swap to change a[i] and a[min] Bước 4 Nếu i < n – 1 thì tôi = tôi + 1; lặp lại bước 2; Ngược lại. dừng Ví dụ. Cho dãy A gồm 4 phần tử 10, 5, 14, 9. Vui lòng sử dụng thuật toán sắp xếp Sắp xếp lựa chọn để minh họa First i=0. a0 = 10. Gán cho 10 là giá trị nhỏ nhất Chạy từ a1 đến a3 xét thấy a1 là phần tử nhỏ nhất ( min) nên đổi vị trí giữa a0 và a1 new lines. 5, 10, 14, 9 Phần tử nhỏ nhất được tìm thấy của mảng được đưa ra đầu tiên nên sẽ tăng i lên 1 đơn vị i=i+1=1. a1= 10 Chạy từ a1 đến a3 xét thấy a3=9 là phần tử nhỏ nhất nên tiến hành chuyển đổi vị trí giữa a1 và a3 new lines. 5, 9, 14 , 10 Tương tự từ a1 đến a3 không còn phần từ nào nhỏ hơn 9 nên tôi sẽ tăng lên 1 đơn vị i=i+1=2. a2=14 Chạy từ a2 đến a3 xét thấy a3=10 là phần tử nhỏ nhất nên tiến hành chuyển đổi vị trí giữa a2 và a3 new lines. 5, 9, 10, 14 Sau đó tăng i lên 1 đơn vị i=i+1=3. Do not I 5, 9, 10, 14 Mã C/C++ Hàm sắp xếp theo thuật toán Lựa chọn Sắp xếp Hàm chuyển đổi vị trí 2 phần tử ( Hoán đổi ). Hàm chính Trước khi chạy hàm chính, bạn phải nhập hàm và xuất mảng 1 chiều. Các bạn có thể xem tại đây Kết quả SO PHAN TÚ 6 Phan tú thư 0. 7 phan tu thu 1. 11 phan tu thu 2. 1 phan tu thu 3. 4 phan tu thu 4. 6 phan tu thu 5. 0 Nội dung của mang la. 7 11 1 4 6 0 Mang sau khi sap xep la. 0 1 4 6 7 11 Trên đây là một trong các thuật toán sắp xếp sắp xếp của bài toán C/C++. Sắp xếp lựa chọn là một thuật toán giải quyết bài toán sắp xếp, còn rất nhiều thuật toán sắp xếp khác mà chúng tôi sẽ gửi cho các bạn ở các bài viết sau. Xem thêm Thuật toán sắp xếp nổi bọt (BubbleSort) |
