Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Saturday, January 24, 2015

/*thuật toán sắp xếp shaker sort
Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau:
Lượt đi: đẩy phần tử nhỏ về đầu mảng.
Lượt về: đẩy phần tử lớn về cuối mảng.
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Bước 1: l=0; r=n-1; //Đoạn l->r là đoạn cần được sắp xếp
k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sơ thu hẹp đoạn l->r
Bước 2:
Bước 2a:
j=r; //đẩy phần tử nhỏ về đầu mảng
Trong khi j>l
nếu a[j]<a[j-1] thì {Doicho(a[j],a[j-1]): k=j;}
j--;
l=k; //loại phần tử đã có thứ tự ở đầu dãy
Bước 2b: j=l
Trong khi j<r
nếu a[j]>a[j+1] thì {Doicho(a[j],a[j+1]); k=j;}
j++;
r=k; //loại phần tử đã có thứ tự ở cuối dãy
Bước 3: Nếu l<r lặp lại bước 2
Ngược lại: dừng

*/
#include<iostream>
using namespace std;
inline void doi(int &a, int &b)
{
int t = a; a = b; b = t;
}
void xep(int a[], int n)
{
int left = 0, right = n - 1, k,i,j;
while (left < right)
{
for (i = left; i < right; i++) if (a[i]>a[i + 1]) { doi(a[i], a[i + 1]); k = i; };
right = k;
for (j = right; j>left; j--) if (a[j] < a[j - 1]){ doi(a[j], a[j - 1]); k = j; }
left = k;
}
}
void main()
{
int a[10] = { 2, 8, 9, 5, 6, 3, 4, 7, 1, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

0 comments:

Post a Comment

Popular Posts