Tìm kiếm nhị phân

Ý tưởng

*Áp dụng đối với những dãy số đã có thứ tự(đã được sắp xếp tăng dần hoặc giảm dần).

*Giải thuật tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành.

Giải thuật

Bước 1: left = 1;  right = N;   // tìm kiếm  trên tất cả các phần tử

Bước 2:

mid = (left+right)/2;         // lấy mốc so sá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:   //tìm tiếp x trong dãy con aleft .. amid -1

  right =mid - 1;

¢a[mid] < x:   //tìm tiếp x trong dãy con amid +1 .. aright

  left = mid + 1;

Bước 3:

  Nếu left <= right   //còn phần tử chưa xét tìm tiếp.

  Lặp lại Bước 2.

  Ngược lại: Dừng  //Ðã xét hết tất cả các phần tử.

Cài đặt 

int BinarySearch(int a[],int N,int x )
{  int left =0; right = N-1;
  int mid;
  do{
  mid = (left + right)/2;
  if (x == a[mid]) 

  return mid;//Thấy x tại mid

  else if (x < a[mid])  

  right = mid -1;
          else

  left = mid +1;
  }while (left <= right);
  return -1; // Tìm hết dãy mà không có x

}  
Kết quả trả về là vị trí của x trong mảng. Nếu trả về -1 là không có x trong mảng

Tìm kiếm tuyến tính

*Ý tưởng

  Tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x.

*Giải thuật  

Bước 1:

   i = 1;          // bắt đầu từ phần tử đầu tiên của dãy

Bước 2: So sánh a[i] với x, có  2 khả năng :

*a[i] = x : Tìm thấy. Dừng

*a[i] != x :  Sang Bước 3.

Bước 3:

* i = i+1;      // xét tiếp phần tử kế trong mảng

* Nếu i >N: Hết mảng, không tìm thấy. Dừng

   Ngược lại: Lặp lại Bước 2.

Cài đặt

Cách 1

int LinearSearch(int a[], int N, int x)

{ 

  int i=0;

  while ((i<N) && (a[i]!=x ))   

  i++;

  if(i==N) 

  return -1;// tìm hết mảng nhưng không có x

  else 

  return i;// a[i] là phần tử có khoá x

} 

Cách 2:Cải tiến (dùng lính canh) giúp giảm bớt một phép so sánh(tối ưu hơn cách 1)

  int LinearSearch2(int a[],int N,int x)

{  int i=0;  // mảng gồm N phần tử từ a[0]..a[N-1]

   a[N] = x; // thêm phần tử thứ N+1

  while (a[i]!=x ) 

  i++;

  if (i==N)

   return -1;   // tìm hết mảng nhưng không có x

  else

  return i;   // tìm thấy x tại vị trí i

}

Lưu ý: Kết quả trả về của 2 hàm này là vị trí tìm thấy của x trong mảng. Nếu kết quả trả về là -1 là mảng không có phần tử x

Thuật Toán InsertionSort Theo Phương Pháp Đệ Quy

Thuật toán InsertionSort Theo Phương Pháp Đệ Quy

void Insert(int a[], int N, int x)
{
   if (N < 1 || a[N - 1] <= x) {
       a[N] = x;
       return;
   }
   a[N] = a[N - 1];
   Insert(a, N - 1, x);
}

void InsertionSort(int a[], int N)
{
   if (N <= 1)
       return;
   InsertionSort(a, N - 1);
   Insert(a, N - 1, a[N - 1]);
}

Thuật toán InsertionSort không đệ quy Tại đây

Thuật toán QUICKSORT

Ý tưởng

*Chia dãy cần sắp thành 2 phần

*Cách “chia”: ½ dãy bên trái chứa các giá trị nhỏ hơn ½ dãy bên phải

*Thực hiện việc sắp xếp trên từng dãy con (đệ qui)

Giải thuật

Cho dãy aL, aL+1, … aR

Bước 1:

  Phân hoạch dãy aL … aR thành các dãy con:

*Dãy con 1: aL … aj< x

*Dãy con 2: aj+1 … ai-1 =x

*Dãy con 3: ai … aR > x

Bước 2:

*Nếu (L<j) Phân hoạch dãy aL … aj

*Nếu (i<R) Phân hoạch dãy ai … aR

  Giải thuật phân hoạch dãy aL, aL+1, … aR thành 2 dãy con

    Bước 1:

            Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, L≤k≤R

  x=a[k], i=L, j=R

  Bước 2:

  Phát hiện và hiệu chỉnh cặp a[i] và a[j] nằm sai chỗ:

  Bước 2a: Trong khi (a[i]<x) i++

  Bước 2b: Trong khi (a[j]>x) j--

  Bước 2c: Nếu (i<j) Hoán vị a[i] và a[j]

  Bước 3:

  Nếu i<j: Lặp lại bước 2

  Ngược lại: Dừng phân hoạch

Cài đặt

void QuickSort(int a[], int left, int right)

{  int i, j, x;  x=a[(left+right)/2];  i=left, j=right;

  do{  while(a[i]<x)  i++;

  while(a[j]>x) j--;

  if(i<=j) 

  {

  HoanVi(a[i], a[j]);  i++;  j--;

  }

  } while(i<j);

  if(left<j)  QuickSort(a, left, j);

  if(i<right)  QuickSort(a, i, right); 

}

Thuật toán BubbleSort

*Ý 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.

Giải thuật

Bước 1:

  i = 1; 

Bước 2:

  j = N; 

  Trong khi (j > i) thực hiện:

  Nếu a[j]<a[j-1]: Hoán vị a[j] và a[j-1]

  j = j-1; 

Bước 3:

  i = i+1; 

  Nếu  i >N-1: Hết dãy. Dừng 

  Ngược lại: Lặp lại Bước 2.

Cài đặt

void BubleSort(int a[], int N )

{ 

  int  i, j;
for (i = 0 ; i<N-1 ; i++)
  for (j =N-1; j >i ; j --)

    {
  if(a[j]< a[j-1])
  Hoanvi(a[j],a[j-1]);

    }

}

Thuật toán InsertionSort

Ý tưởng

Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử  a1 đã được sắp, sau đó thêm a2  vào đoạn a1 sẽ có đoạn  a1 a2 được sắp; tiếp tục thêm a3  vào đoạn a1 a2 để có đoạn  a1 a2  a3 được sắp; tiếp tục cho đến khi thêm xong aN  vào đoạn a1 a2 ...aN-1  sẽ có dãy a1 a2 .... aN được sắp. 

Thuật toán

Bước 1:  i = 2;  // giả sử có đoạn a[1]đã được sắp
Bước 2: x = a[i];
              Tìm vị trí posthích hợp trong đoạn a[1] đến a[i-1] để
              chèn a[i] vàoBước 3: Dời chỗ các phần tử  từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i]
Bước 4: a[pos] = x;  // có đoạn a[1]..a[i]  đã được sắp
Bước 5:  i = i+1;
          Nếu  i ≤N : Lặp lại Bước 2.
               Ngược lại  : Dừng. 

Cài đặt

void InsertionSort(int a[], int N )

{ 

  int pos;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
  x = a[i]; pos = i-1;
  // tìm vị trí chèn x

  while((pos >= 0)&&(a[pos] > x))
  {// kết hợp dời chỗ các phần tử

      a[pos+1] = a[pos];
      pos--;
  }
  a[pos+1] = x;// chèn x vào dãy
}

}

Thuật toán InsertionSort theo phương pháp đệ quy Tại đây