Ý tưởng:
Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. Các bước tiến hành như sau :
Thuật toán:
* Bước 1 : i = 1;// bắt đầu từ đầu dãy
* Bước 2 : j = i+1;//tìm các phần tử a[j] < a[i], j>i
* Bước 3 :
Trong khi j < N thực hiện
Nếu a[j]<a[i]:a[i]=a[j]// hoán vị (a[i] a[j])
j = j+1;
* Bước 4 : i = i+1;
Nếu i < n: Lặp lại Bước 2.
Ngược lại: Dừng.
* Ví dụ: Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt:
Cài đặt thuật toán sắp xếp theo kiểu đổi chỗ trực tiếp thành hàm InterchangeSort:
void InterchangeSort(int a[], int N )
{
int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ
Hoanvi(a[i],a[j]);
}
0 nhận xét:
Đăng nhận xét