Yêu cầu: Với dữ liệu sinh viên gồm các thông tin

if (k>i) {tg = X[k]; X[k]= X[i]; X[i] = tg;}

}

• 
  Thuật toán có độ phức tạp O(n²), trong đó có (n-1)(n+2) phép so sánh và nhiều nhất là 3(n-1) phép hoán đổi vị trí các phần tử.
  

5.2.2. Sắp xếp nổi bọt

• 
  Tại mỗi bước lớn của thuật toán sắp xếp nổi bọt một phần tử được đưa về đúng vị trí của nó. Như vậy, thuật toán sắp xếp nổi bọt cũng chỉ có n-1 bước lớn. Đây là điểm giống với thuật toán sắp xếp chọn.
  
• 
  Điểm khác biệt là ở chỗ trong mỗi bước lặp của thuật toán sắp xếp chọn chỉ thông qua các phép toán so sánh để xác định vị trí hiện thời của phần tử thích hợp với vị trí đang được xét đến tại bước lặp, sau đó có thể thực hiện phép đổi chỗ để đưa phần tử về vị trí thích hợp; trong khi đó, với thuật toán sắp xếp nổi bọt, sẽ phải thực hiện liên tiếp một số phép toán so sánh và đổi chỗ để đưa được phần tử thích hợp về vị trí đang xét đến trong bước lặp của thuật toán. Chẳng hạn, xét bước thứ i, 1  i  n:
  

1. 
   Các phần tử ở vị trí trước i đều đã được chọn thích hợp;
   
2. 
   Xét lần lượt các cặp (X[j-1], X[j]), j = n, ..., i+1, nếu X[j-1] > X[j] thì đổi chỗ X[j-1] và X[j].
   

13

22

3

14

14

15

21

14

15

19

j = 10

13

22

3

14

14

15

21

14

15

19

j = 9

13

22

3

14

14

15

21

14

15

19

13

22

3

14

14

15

21

14

15

19

13

22

3

14

14

15

14

21

15

19

j = 7

13

22

3

14

14

15

14

21

15

19

13

22

3

14

14

14

15

21

15

19

13

22

3

14

14

14

15

21

15

19

j = 5

13

22

3

14

14

14

12

21

15

19

j = 4

13

22

3

14

14

14

12

21

15

19

13

22

3

14

14

14

12

21

15

19

13

3

22

14

14

14

12

21

15

19

13

3

22

14

14

14

12

21

15

19

3

13

22

14

14

14

12

21

15

19

• 
  Trong ví dụ trên, sau khi kiểm tra từ chỉ số j = 10 đến j = 2 để đổi chỗ các cặp “nghịch biến", X[j-1] > X[j], thuật toán đã chuyển được phần tử nhỏ nhất vào vị trí i=1. Không khó để chứng minh rằng phép toán b) ở bước thứ i nêu trên chuyển được phần tử nhỏ nhất trong số các phần tử {X[i], ..., X[n]} về vị trí thứ i.
  

for (i=1; i

{

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

{tg = X[j-1]; X[j-1]= X[j]; X[j] = tg;}

}

• 
  Thuật toán có độ phức tạp O(n²), trong đó phải thực hiện (n-1)(n+1) phép so sánh và nhiều nhất là 3n(n-1)/2 phép hoán đổi vị trí các phần tử.
  

5.2.3. Sắp xếp chèn

• 
  Giả sử có phần đầu của mảng là B(i) = { X[1],...,X[i] } đã được sắp xếp không giảm:
  

• 
  xét phần tử thứ i+1. Đưa (chèn) X[i+1] vào vị trí thích hợp trong dãy (5.1). Đặt tg = X[i+1]. Có ba khả năng xảy ra:
  

1. 
   X[i] ≤ X[i+1]: Giữ nguyên X[i+1] ở vị trí thứ i+1.
   
2. 
   Tồn tại chỉ số j, 1< j i, sao cho X[j-1] ≤ tg < X[j]: Kéo toàn bộ các phần tử từ X[j],..., X[i] về phía sau. Chèn giá trị X[i+1] vào vị trí thứ j.
   
3. 
   X[i+1] < X[1]. Kéo toàn bộ các phần tử từ X[1],..., X[i] về phía sau. Chèn giá trị X[i+1] vào vị trí thứ 1.
   

j = i+1;

while (X[j-1] > tg)

{ X[j] = X[j-1];

j = j-1;

X[j] = tg;

• 
  Trong đoạn mã trên, khi chỉ số j nhận giá trị 1 tương ứng với trường hợp c). Vì vậy, trường hợp b) và c) có thể được mô tả:
  

tg = X[i+1];

while ((j>1) && (X[j-1] > tg))

{ X[j] = X[j-1];

j = j-1;

}

X[j] = tg;

• 
  Để ý rằng nếu X[i]  X[i+1], tức là X[j-1]  tg ngay khi j = i+1 thì rõ ràng là vòng lặp không được thực hiện bước nào, chỉ số j không thay đổi, nghĩa là phép gán X[j] = tg thực ra là gán X[i+1] cho chính nó, không làm thay đổi giá trị phần tử nào.
  
• 
  Trong mọi trường hợp, luôn có thể coi B(1) = { X[1] } đã được sắp xếp không giảm. Như vậy, thuật toán sắp xếp chèn có thể được mô tả như sau:
  

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

{ j = i+1;

tg = X[i+1];

while ((j>1) && (X[j-1] > tg))

{ X[j] = X[j-1];

j = j-1;

}

X[j] = tg;

X

13

22

30

14

5

21

21

12

15

19

Đặt tg = 14, j= 4.

X	13	22	30	14	5	21	21	12	15	19
j				4

X	13	22	30	30	5	21	21	12	15	19
j			3

X	13	22	22	30	5	21	21	12	15	19
j		2

X	13	14	22	30	5	21	21	12	15	19
j		2

• 
  Thuật toán sắp xếp chèn có độ phức tạp O(n²), trong đó, trong trường hợp xấu nhấtphải thực hiện (n-1)(n+1) phép so sánh và n(n+1)/2 phép đổi chỗ.