thuật toán tìm kiếm nhị phân

/*thuật toán tìm kiếm nhị phân
Được áp dụng trên mảng đã có thứ tự.
Ý tưởng: .
Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có
ai-1<ai<ai+1
Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]
Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0,   ai-1]
Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:
Bước 1: left=0; right=N-1;
Bước 2:
mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hành
So sánh a[mid] với x. Có 3 khả năng
a[mid]= x: tìm thấy. Dừng
a[mid]>x :  Right= mid-1;
a[mid]<x : Left= mid+1;
Bước 3: Nếu Left <=Right ; //  còn phần tử trong dãy hiện  hành
+ Lặp lại bước 2
Ngược lại : Dừng
Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0

*/
#include<iostream>
using namespace std;
int tim(int a[], int left,int right, int x)
{
do
{
if (x == a[(left + right) / 2]) return 1;
if (a[(left + right) / 2] > x) right = (left + right) / 2 - 1;
else left = (left + right) / 2 + 1;
} while (left <= right);
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << tim(a, 0, 9, 1);
}

thuật toán tìm kiếm tuyến tính

/*thuật toán tìm kiếm tuyến tính
Cho danh sách có n phần tử a0, a1, a2…, an-1.
Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.
Tìm phần tử có khoá bằng X trong mảng
Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
Giải thuật tìm kiếm nhị phân
Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C.
Ý tưởng : So sánh X lần lượt với phần tử thứ 1, thứ 2,…của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước tiến hành
Bước 1: Khởi gán i=0;
Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;
Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:
int LinearSearch(int a[],int n, int x)
{
int i=0;
while((i<n)&&(a[i]!=x))
i++;
if(i==n)
return 0; //Tìm không thấy x
else
return 1; //Tìm thấy
}Nhận xét: Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n.
Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối dãy.
int LinearSearch(int a[],int n, int x)
{ int i=0; a[n]=x;   // a[n] là phần tử “lính canh”
while(a[i]!=x) 
i++;
if(i==n)
return 0; // Tìm không thấy x
else
return 1; // Tìm thấy
}

*/
#include<iostream>
using namespace std;
int tim(int a[], int n,int x)
{
for (int i = 0; i < n;i++) if (x == a[i]) return i+1;
return 0;
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int x;
cout << "nhap gia tri muon tim: ";
cin >> x;
int vt = tim(a, 10, x);
if (vt !=0) cout << "tim thay tai vi tri: " << vt << "\n";
else cout << "khong tim thay\n";
}

thuật toán selection sort

/*thuật toán selection sort
Ý tưởng:
Chọn phần tử nhỏ nhất trong N phần tử trong dãy hiện hành ban đầu.
Đưa phần tử này về vị trí đầu dãy hiện hành
Xem dãy hiện hành chỉ còn N-1 phần tử của dãy hiện hành 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ử
Bước 1:   i = 0;
Bước 2:  Tìm phần tử a[min] nhỏ nhất trong    dãy hiện hành từ a[i] đến a[N]
Bước 3 :  Đổi chỗ a[min] và a[i]
Bước 4 :  Nếu  i < N-1 thì
i = i+1; Lặp lại Bước 2;                Ngược lại: Dừng.

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

thuật toán interchange sort

/*thuật toán interchange sort
Ý tưởng: Xuất phát từ đầu dãy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy.
Bước 1: i = 0;  // bắt đầu từ đầu dãy
Bước 2: j = i+1; //tìm các nghịch thế với a[i]
Bước 3:
Trong khi j < N thực hiện
Nếu a[j]<a[i] //xét cặp a[i], a[j]
Swap(a[i],a[j]);
j = j+1;
Bước 4: i = i+1;
Nếu  i < N-1: Lặp lại Bước 2.
Ngược lại:  Dừng.

*/
#include<iostream>
using namespace std;
void xep(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])
{
a[i] += a[j]; a[j] = a[i] - a[j]; a[i] = a[i] - a[j];
}
}
void main()
{
int a[10] = { 3, 7, 4, 1, 8, 9, 2, 5, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

thuật toán bubble sort

/*thuật toán bubble sort
Ý tưởng:
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i.
Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
Bước 1 : i = 0; // lần xử lý đầu tiên
Bước 2 : j = N-1;//Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j > i) thực hiện:
Nếu a[j]<a[j-1]
Doicho(a[j],a[j-1]);
j = j-1;
Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu  i =N: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2.

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

thuật toán sắp xếp shaker sort

/*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];
}

Đối số mảng truyền cho hàm - con trỏ

xuat(int a[10]) hoàn toàn tương đương với xuat(int *a), tức đối số là biến con trỏ, do đó khi printf phải thêm dấu * để chuyển thành giá trị để in.
vì a là mảng ( là 1 chuổi ô nhó liên tiếp nhau, mặt định a là ô nhớ đầu tiên == a[0]) khi truyền mảng vào hàm thức chất là truyền địa chỉ của ô nhớ đầu tiên trong mảng, còn n là biến thông thường, xuat(int n) hoàn toàn khác với xuat(int *n).
mảng a trong main là nơi ta khai báo, mặt định trong main() lúc này là biến giá trị thông thường, nếu ta khai báo trong hàm xuat() mảng a[10] này thì trong hàm xuất nó mặt định là biến giá trị, khi printf không thêm dấu * gì hết, mà dùng a[i], chứ không được phép dùng a++

Cho 1 mảng int a[10];
Thì a thôi, sẽ là con trỏ hằng trỏ vào vị trí a[0].
a++ sẽ hiểu là thay đổi con trỏ, trỏ vào vị trí khác a[0] (tùy theo số lần chạy qua bước ++ mà thành a[1], a[2],...)

Con trỏ hằng, nghĩa là không thay đổi mà trỏ sang chỗ khác được.
Do vậy, đoạn code trong hàm main bị lỗi.

Tuy nhiên, khi int a[10] để vào tham số của hàm, thì a là 1 biến con trỏ mới, hoàn toàn là con trỏ động (tương đương *a), trỏ vào cái vùng bộ nhớ gốc lúc gọi hàm.
Lúc này, con trỏ a không còn là con trỏ hằng nữa, nên có thể thay đổi vị trí trỏ được, nên a++ chạy tốt.

lấy ví dụ:
======================
void xuat(int a[10],int n)
{
for(int i=0;i<n;i++) printf("%d",*(a++));
}
void main()
{
int b[10];
xuat(b,10);// trong main gọi hàm xuất bên trên
}
===================