Selection Sort

Cấu trúc dữ liệu và giải thuật - Sắp xếp

Đề bài: Viết chương trình sắp xếp các phần tử trong mảng một chiều bằng thuật toán Selection Sort.

Selection Sort hay còn được gọi là sắp xếp chọn

Ý tưởng:

Tìm phần tử nhỏ nhất (min) trong dãy đã cho có độ dài n, rồi đặt nó lên đầu dãy. Sau đó “lờ” nó đi, xét dãy a[] có n-1 phần tử và tìm phần tử nhỏ nhất cảu dãy đó sau đó đặt nó lên đầu dãy.Lặp lại các thao tác trên với dãy a[] cho đến khi chỉ còn 1 phần tử đang xét.

Các bước thực hiện:

• Với i=0 trong khi i<=n làm:
• Vitrimin = i;
• j=i+1;
• nếu a[j]<a[vitrimin] thì vitrimin=j;
• Gọi hàm swap(a[j],a[vitrimin]) để đổi chỗ
• Nếu j<n-1 thì i=i+1; lặp lại bước b ngược lại thì dừng
• Nếu j<=i thì j=j+1; lặp lại bước i ngược lại thì dừng

Cài đặt:

#include<iostream> #include<math.h> using namespace std; void nhap(int a[],int &n) { cout<<"moi nhap so phan tu "; cin>>n; for (int i=0;i<n;i++) { cin>>a[i]; } } void xuat (int a[],int n) { for(int i=0;i<n;i++) { cout<<a[i]<<" "; } } void swap(int &a,int &b) { int tam=a;a=b;b=tam; } void selectsort(int a[],int n) { int vitrimin; for(int i=0;i<n-1;i++) { vitrimin=i; for(int j=i+1;j<n;j++) if(a[j]<a[vitrimin]) vitrimin=j; swap(a[i],a[vitrimin]); } } int main() { int a[1000],n; nhap(a,n); selectsort(a,n); cout<<"kq: "; xuat(a,n); }

Kết quả khi chạy chương trình:

Độ phức tạp của thuật toán là:

• Tốt nhất: O(n(n-1)/2)
• Xấu nhất: O(n(n-1)/2)

Được viết bởi Đinh Quang Trưởng

cấu trúc dữ liệu và giải thuật sắp xếp 3:26 PM