Sắp xếp bậc hai
Sắp xếp - là sắp xếp lại các phần tử của một mảng (danh sách) theo một thứ tự nhất định.
Phương pháp bong bóng (sắp xếp bong bóng) hoặc sắp xếp theo trao đổi đơn giản).
Một tác phẩm kinh điển bất hủ của thể loại này. Nguyên tắc hoạt động rất đơn giản: chúng ta đi xung quanh mảng từ đầu đến cuối, đồng thời hoán đổi các phần tử lân cận chưa được sắp xếp. Kết quả của lần vượt qua đầu tiên đến vị trí cuối cùng, "bật lên" phần tử cực đại. Bây giờ chúng ta lại bỏ qua phần chưa sắp xếp của mảng (từ phần tử đầu tiên đến phần tử áp chót) và thay đổi các hàng xóm chưa sắp xếp trên đường đi. Phần tử lớn thứ hai sẽ ở vị trí áp chót. Tiếp tục với tinh thần tương tự, chúng ta sẽ bỏ qua phần chưa được sắp xếp ngày càng giảm của mảng, đẩy giá trị lớn nhất tìm được về cuối.
Nguồn
Thuật toán thực hiện thuật toán này
LOOP CHO J=1 ĐẾN N-1 BƯỚC 1
f=0
LOOP FOR I=1 TO N-J-1 BƯỚC 1
NẾU A[I] > A[I+1] THÌ
TRAO ĐỔI A[I],A[I+1]
f=1
TIẾP THEO TÔI
NẾU F=0 THÌ THOÁT VÒNG VÒNG // nếu không có trao đổi nào trong quá trình vượt qua,
// có nghĩa là tất cả các phần tử
// sắp xếp theo thứ tự
TIẾP THEO J
Độ phức tạp của thuật toán này: \(\displaystyle O(n^{2})\).
Thông tin hữu ích khác: Bài viết trên Wikipedia.