Lựa chọn Sắp xếp là thuật toán tấn công hoạt động tạm biệt để tìm số nhỏ nhất từ mảng và sau đó đặt nó vào vị trí đầu tiên. mảng tiếp theo sẽ được duyệt qua sẽ bắt đầu từ chỉ mục bên cạnh vị trí đặt số nhỏ nhất.
Hãy lấy một ví dụ để làm rõ hơn khái niệm này.
Chúng ta có một mảng {6, 3, 8, 12, 9} trong mảng này phần tử nhỏ nhất là 3. Vì vậy, chúng ta sẽ đặt 3 ở vị trí đầu tiên, sau này mảng sẽ giống như {3, 6, 8, 12, 9}. Bây giờ chúng ta sẽ lại tìm số nhỏ nhất nhưng lần này chúng ta sẽ không xét đến 3 trong tìm kiếm của mình vì nó đã ở đúng vị trí của nó. Tìm phần tử nhỏ nhất tiếp theo là 6, tạo mảng có 6 ở vị trí thứ hai và sau đó tìm kiếm lại trong mảng cho đến khi mảng được sắp xếp.
Hoạt động của thuật toán sắp xếp lựa chọn−
các bước sau được thực hiện bởi thuật toán Sắp xếp lựa chọn
Hãy lấy một mảng {20, 12, 23, 55, 21}
-
Đặt phần tử đầu tiên của mảng là tối thiểu.
Tối thiểu =20
-
So sánh mức tối thiểu với phần tử tiếp theo, nếu nó nhỏ hơn mức tối thiểu, hãy chỉ định phần tử này là tối thiểu. Làm điều này cho đến cuối mảng.
So sánh với 12:20> 12, tối thiểu =12
So sánh với 23:12 <23, tối thiểu =12
So sánh với 55:12 <55, tối thiểu =12
So sánh với 21:12 <21, tối thiểu =12
-
Đặt giá trị tối thiểu ở vị trí đầu tiên (chỉ số 0) của mảng.
Mảng ={12, 20, 23, 55, 21}
-
cho lần lặp tiếp theo, hãy bắt đầu sắp xếp từ phần tử chưa được sắp xếp đầu tiên, tức là phần tử bên cạnh vị trí tối thiểu được đặt.
Mảng ={12, 20, 23, 55, 21}
Tìm kiếm bắt đầu từ 20, phần tử tiếp theo được đặt ở vị trí tối thiểu.
Lặp lại 2:
Tối thiểu =20
So sánh với 23:20 <23, tối thiểu =20
So sánh với 55:20 <55, tối thiểu =20
So sánh với 21:20 <21, tối thiểu =20
Tối thiểu tại chỗ không thay đổi,
Mảng ={12, 20, 23, 55, 21}
Lặp lại 3:
Tối thiểu =23.
So sánh với 55:23 <55, tối thiểu =23
So sánh với 21:23> 21, tối thiểu =21
Giá trị tối thiểu được chuyển đến chỉ mục =2
Mảng ={12, 20, 21, 55, 23}
Lặp lại 4:
Tối thiểu =55
So sánh với 23:23 <55, tối thiểu =23
Tối thiểu được chuyển đến chỉ mục 3Array ={12, 20, 21, 23, 55}
Ví dụ
#include <stdio.h>
int main() {
int arr[10]={6,12,0,18,11,99,55,45,34,2};
int n=10;
int i, j, position, swap;
for (i = 0; i < (n - 1); i++) {
position = i;
for (j = i + 1; j < n; j++) {
if (arr[position] > arr[j])
position = j;
}
if (position != i) {
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}
for (i = 0; i < n; i++)
printf("%d\t", arr[i]);
return 0;
} Đầu ra
0 2 6 11 12 18 34 45 55 99