Xét danh sách con gồm k phần tử đầu a1 … ak. Với k = 1, danh sách gồm một phần tử đã được sắp xếp thành dãy tăng dần. Giả sử trong danh sách k-1 phần tử đầu a1 … ak-1 đã được sắp xếp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1 … ak-1. Vị trí thích hợp cần tìm là vị trí đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.
Chọn phần tử nhỏ nhất đưa về vị trí đầu tiên của dãy hiện tại và không cần quan tâm đến nó nữa, khi đó dãy chỉ còn lại n-1 phần tử của dãy ban đầu, lúc đó dãy ta xét sẽ bắt đầu từ phần tử thứ 2 của mảng, chúng ta lập lại cho đến khi dãy hiện tại chỉ còn 1 phần tử.
- Ưu và nhược điểm
Số lần so sánh trong trường hợp tốt nhất là n(n-1)/2
Số lần so sánh trong trường hợp xấu nhất là 3n(n-1)/2
- Ưu điểm
Thuật toán đơn giản, dễ hiện thực.
Có số lần hoán đổi các vị trí ít.
- Nhược điểm
Chỉ được áp dụng trong các trường hợp có số lượng phần tử cần so sánh ít.
SORT
1. Insertion sort
Ý tưởng
Xét danh sách con gồm k phần tử đầu a1 … ak. Với k = 1, danh sách gồm một phần tử đã được sắp xếp thành dãy tăng dần. Giả sử trong danh sách k-1 phần tử đầu a1 … ak-1 đã được sắp xếp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1 … ak-1. Vị trí thích hợp cần tìm là vị trí đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.
2. Selection sort
- Ý tưởng
Chọn phần tử nhỏ nhất đưa về vị trí đầu tiên của dãy hiện tại và không cần quan tâm đến nó nữa, khi đó dãy chỉ còn lại n-1 phần tử của dãy ban đầu, lúc đó dãy ta xét sẽ bắt đầu từ phần tử thứ 2 của mảng, chúng ta lập lại cho đến khi dãy hiện tại chỉ còn 1 phần tử.
- Ưu và nhược điểm
Số lần so sánh trong trường hợp tốt nhất là n(n-1)/2 Số lần so sánh trong trường hợp xấu nhất là 3n(n-1)/2
- Ưu điểm
Thuật toán đơn giản, dễ hiện thực.
Có số lần hoán đổi các vị trí ít.
- Nhược điểm
Chỉ được áp dụng trong các trường hợp có số lượng phần tử cần so sánh ít.
Không nhận biết được mảng đã được sắp xếp.