I.                   Giải thuật Selection sort(Chọn): Lần lượt chọn phần tử nhỏ nhất trong dãy chỉ số k1,k2,..kn với i= 0,1,…n;ki<k(i+1)<…,kn và đổi chỗ cho phần tử thứ ki. Như vậy, sau j = n-1 lần chọn, chúng ta sẽ có dãy khóa được sắp xếp theo thứ tự tăng dần

1.Ý tưởng:

v     Bước 1: Tìm phần tử nhỏ nhất trong dãy và đưa nó về vị trí đầu tiên của dãy.

v     Bước 2: Tìm phần tử nhỏ thứ hai và đưa nó về vị trí thứ 2 trong dãy.

v     Bước tiếp: Lặp lại quá trình trên cho đến khi tất các phần tử đã sắp đúng thứ tự.

2.Giải mã:

Void SelectionSort(int a[], int n)

{

   int min;

   for(int i=0;i<n-1;i++)

   {

      min=i;

      for(int j=i+1;j<n;j++)

         if(a[j]<a[min]) min=j;

      HoanVi(a[min],a[i]);

   }

}

II.                 Giải thuật Insertionsort(Chèn):  là một thuật toán  bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

1.Ý tưởng:

v                 Sử dụng biến để chia tập thành 2 vùng: vùng đẵ sắp và vùng chưa sắp.

v                 Vùng đã sắp bắt đầu từ phần tử đầu tiên của dãy.

v                 Lấy phần tử đầu tiên của vùng chưa sắp và chèn vào vùng đã sắp.

v                 Như vậy, vùng đã sắp sẽ có thêm một phần tử.

v                 Thực hiện tương tư cho đến khi vùng chưa sắp không còn phần tử nào

2. Giải mã:

void insertionsort(int *list, int n)

{

   int pos,i,x;

   for(i=1;i<n;i++)

   {

                  x=list[i];

                  pos=i-1;

                  while((pos>=0) && (list[pos]>x))

                  {

                              list[pos+1]=list[pos];

                              pos--;

                  }

                  list[pos+1]=x;}}

III.               Giải thuật buble sort(Nổi bọt):là một thuật tóan đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh

1.Ý tưởng:

v     Với các cặp liền kề, thứ i và thứ i+1, đổi chỗ các phần tử này nếu chúng không đúng trật tự sắp xếp. Sau mỗi lần thực hiện việc đổi chỗ, ta thu được 1 phần tử đã ở đúng vị trí;

v     Thực hiện lặp lại quá trình trên cho n-1 phần tử còn lại;

v     Thuật toán dừng khi không còn cặp nào sai vị trí.

2.Giả mã:

void bubblesort(int list[], int n)

{

   int i,j;

   for(i=0;i<(n-1);i++)

      for(j=n-1;j>i;j--)

                    if(list[j]<list[j-1])

                                swap(&list[j],&list[j-1]);

}

IV.             Giả thuật Quicksort(Nhanh): là một phương pháp sắp xếp theo kiểu phân đoạn được cải tiến từ thuật toán Selection Sort do C.A.R Hoare (Sir Charles Antony Richard Hoare – 1960) đưa ra.

1.Ý tưởng:

        Giải thuật QuickSort sắp xếp dãy a[0], a[1],..., a[n-1] dựa trên việc phân hoạch dãy ban đầu thành 2 phần:

v     Phần 1: Gồm các phần tử  có giá trị không lớn hơn x

v     Phần 2: Gồm các phần tử  có giá trị không bé hơn x

    với x là giá trị của một phần tử  tùy ý trong dãy ban đầu.

        Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 2 đoạn:

1.      a[k]  <= x , với k = 1 .. i-1

2.      a[k ] > x , với k =  i..n-1

        Nếu các đoạn 1 và 2 chỉ có 1 phần tử  thì chúng cũng đã có thứ tự, khi đó dãy con ban đầu đã được sắp.

        Ngược lại, nếu các đoạn 1 và 2  có nhiều hơn 1 phần tử  thì dãy con ban đầu chỉ có thứ tự khi các đoạn 1, 2 được sắp.

        Để sắp xếp các đoạn 1 và 2, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …

2.Giả mã:

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

{   

      int       i, j, x;

      if (left ³ right)           return;

      x = a[(left+right)/2]; // chọn phần tử giữa làm                                                    giá trị mốc

      i = left; j = right;

       do{

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

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

     if(i <= j) {

                              Swap(a[i], a[j]);

                  i++ ; j--;

                  }

      } while(i < j) ;

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

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

}

V.                Tìm kiếm tuần tự:

1.Ý tưởng:

v     Sử dụng vòng lặp để có thể duyệt cả danh sách, xuất phát từ phần tử đầu tiên trong danh sách.

v     Tại mỗi bước lặp, so sánh phần tử trong danh sách với giá trị cần tìm ( theo khóa nào đó ). Quá trình sẽ dừng nếu tìm thấy đối tượng cần tìm hoặc đã đi hết danh sách.

2.Giả mã:

int linearSearch (int x, int *a, int n){

      for (int i = 0; i<n; i++)

                  if (a[i] == x) return i;

      return -1;

}

Hoặc:

int linearSearch2(int x, int *a, int n){

      int i = 0,x;

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

      if (a[i] == x) return i;

      return -1;

}

VI.             Tìm kiếm nhị phân

1.Ý tưởng:

Ø     Lấy khóa cần tìm kiếm X so sánh với khóa của phần tử ở giữa, vị trí của phần tử ở giữa là mid=(min+max)/2, trong đó min = 0, max = n-1

Ø     Vì dãy đã được sắp xếp nên giá trị khóa tại vị trí giữa lớn hơn X thì phần tử cần tìm thuộc khoảng [min,mid-1], và ngược lại. Nếu giá trị của X = giá trị của khóa tại vị trí giữa thì đó là phần tử cần tìm

Ø     ở bước tiếp theo, nếu giá trị của khóa tại vị trí giữa nhỏ hơn X thì ta dich chuyển cận dưới lên vị trí mid+1 và ngược lại. Quá trình lặp lại cho tới khi khóa có nội dung trùng với X hoặc cận dưới vượt quá cận trên(X không thuộc dãy).

2.Mã giả:

Int Binary_search(int *A, int x, int n)

{

int min=0, max=n-1,mid;

   while (min <= max)

      {

       mid = (min+max)/2;

       if (x > A[mid])

           min = mid + 1;

       else if(x<A[mid])

           max = mid -1;

      else return(mid);

      }

  return (-1)