Interchange 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 c/c++ sắp xếp các phần tử trong mảng một chiều bằng thuật toán Interchange Sort

Nhận xét: 

Nhiều thuật toán sắp xếp thường được thực hiện đổi chỗ hai phần tử kề liền nhau trên suốt chiều dài của dãy  a[] ban đầu để thu được 1 dãy có thứ tự cần thực hiện “khử nghịch thế”
"Khử nghịch thế" là làm mất các phần tử không đúng vị trí

Ý tưởng:

Một dãy tùy ý cho trước (đang lộn xộn) luôn tồn tại các nghịch thế, bao giờ cũng xuất phát từ phần từ dãy hiện hành rồi tìm tất cả các cặp nghịch thế chữa phần tử ấy. Và để sắp dãy có trật tự thì cần khử các nghịch thế đó bằng cách đổi chỗ cặp nghịch thế này.

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

• 1.Khởi tạo i=0;
• 2.cho j=i+1;
• 3. Trong khi i<=n thì làm:
• Nếu i<j mà (a[i]>a[j] thì gọi hàn swap(a[i],a[j]) để đổi chỗ 2 phần tử này
• j=j+1;
• 4.cho i=i+1;
• nếu i<n lặp lại bước 2
• ngược lại kết thúc.

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 interchangesort(int a[],int n) { for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) { if(a[i]<a[j]) swap(a[i],a[j]); } } int main() { int a[1000],n; nhap(a,n); interchangesort(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:

• 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:58 PM