Thuật toán sắp xếp chọn (Selection Sort)
2 posters
Trang 1 trong tổng số 1 trang
Thuật toán sắp xếp chọn (Selection Sort)
1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
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 1 phần tử.
Do 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.
3. Giải thuật
- Bước 1: i = 1;
- Bước 2: Tìm X[min] trong dãy X[i] ... X[n]
- Bước 3: Đỗi chổ X[i] cho X[min], nếu min trùng với i thì bỏ qua bước này.
- Bước 4:
* Nếu i <= n-1 thì tăng i lên 1 vị trí (i = i +1), quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đung vị trí.
4. Mã thực thi (tựa C)
5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu 7, 2, 5, 4, 1, 3, 8, 6
i=1, min=5, swap(X[min],X[i]) ta có 1, 2, 5, 4, 7, 3, 8, 6
i=2, min=2, không đổi chổ ta có 1, 2, 5, 4, 7, 3, 8, 6
i=3, min=5, swap(X[min],X[i]) ta có 1, 2, 3, 4, 7, 5, 8, 6
i=4, min=4, không đổi chổ ta có 1, 2, 3, 4, 7, 5, 8, 6
i=5, min=6, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 7, 8, 6
i=6, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 8, 7
i=7, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 7, 8 (dãy đã sắp xếp)
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
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 1 phần tử.
Do 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.
3. Giải thuật
- Bước 1: i = 1;
- Bước 2: Tìm X[min] trong dãy X[i] ... X[n]
- Bước 3: Đỗi chổ X[i] cho X[min], nếu min trùng với i thì bỏ qua bước này.
- Bước 4:
* Nếu i <= n-1 thì tăng i lên 1 vị trí (i = i +1), quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đung vị trí.
4. Mã thực thi (tựa C)
- Code:
void SelectionSort(int X[], int n)
{
int min;
for(int i=0;i<n-1;i++)
{
min=i;
for(int j=i+1;j<n;j++)
if(X[j]<X[min]) min=j; // Tìm được vị trí chứa giá trị nhỏ nhất
swap(a[min],a[i]); // Đổi chổ min cho i
}
}
void swap (int x, int y)
{
int temp;
if (x>y){
temp=x;
x=y;
y=temp;
}
}
5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu 7, 2, 5, 4, 1, 3, 8, 6
i=1, min=5, swap(X[min],X[i]) ta có 1, 2, 5, 4, 7, 3, 8, 6
i=2, min=2, không đổi chổ ta có 1, 2, 5, 4, 7, 3, 8, 6
i=3, min=5, swap(X[min],X[i]) ta có 1, 2, 3, 4, 7, 5, 8, 6
i=4, min=4, không đổi chổ ta có 1, 2, 3, 4, 7, 5, 8, 6
i=5, min=6, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 7, 8, 6
i=6, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 8, 7
i=7, min=8, swap(X[min],X[i]) ta có 1, 2, 3, 4, 5, 6, 7, 8 (dãy đã sắp xếp)
hosytan- Tổng số bài gửi : 29
Join date : 02/05/2013
Re: Thuật toán sắp xếp chọn (Selection Sort)
Được biểu diễn bằng C# với đoạn code sau:
- Code:
public int[] selectionsort(int[] a)
{
foreach (int i = 0; i < (a.Length-1); i++)
{
int min = i;
for (int j = i + 1; j < a.Length; j++)
if (a[j] < a[min])
min = j;
if (min != i)
{
int tmp= a;
a= a[min];
a[min] = a;
}
return a;
}
Nguồn:Thuật toán sắp xếp trộn
hbs315- Tổng số bài gửi : 8
Join date : 13/12/2013
Similar topics
» Thuật toán sắp xếp nổi bọt (Bubble Sort)
» Thuật toán sắp xếp chèn (Insertion Sort)
» Thuật toán sắp xếp trộn (Merge Sort)
» Thuật toán sắp xếp vun đống (Heap Sort)
» Thuật toán sắp xếp phân đoạn/sắp xếp nhanh (Quick Sort)
» Thuật toán sắp xếp chèn (Insertion Sort)
» Thuật toán sắp xếp trộn (Merge Sort)
» Thuật toán sắp xếp vun đống (Heap Sort)
» Thuật toán sắp xếp phân đoạn/sắp xếp nhanh (Quick Sort)
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|