Tiêu đề Chuong 2 - Lecture note ✅

○ Nếu mảng đã sắp xếp, chỉ cần 1 lượt duyệt để kiểm tra, phát hiện không có swap ⇒ O(n). ○ Điều này phụ thuộc ta có cài đặt cờ “có swap” hay không. Ví dụ ● 5,3,8,6,2 ● Lần lặp đầu tiên (i = 0): ● So sánh và hoán đổi từng cặp phần tử: ● 5>3: Hoán đổi → 3,5,8,6,2 ● 5<8: Không hoán đổi → 3,5,8,6,2 ● 8>6: Hoán đổi → 3,5,6,8,2 ● 8>2: Hoán đổi → 3,5,6,2,8 ● Phần tử lớn nhất (8) đã được đưa về cuối. ● Lần lặp thứ hai (i = 1): ● So sánh và hoán đổi các phần tử còn lại: ● 3<5: Không hoán đổi → 3,5,6,2,8 ● 5<6: Không hoán đổi → 3,5,6,2,8 ● 6>2: Hoán đổi → 3,5,2,6,8 ● Phần tử lớn thứ hai (6) đã được đưa về đúng vị trí. ● Lần lặp thứ ba (i = 2): ● So sánh và hoán đổi: ● 3<5: Không hoán đổi → 3,5,2,6,8 ● 5>2: Hoán đổi → 3,2,5,6,8 ● Lần lặp thứ tư (i = 3): ● So sánh và hoán đổi: ● 3>2: Hoán đổi → 2,3,5,6,8
● Kết quả cuối cùng: 2,3,5,6,8 C++ #include #include using namespace std; void bubble(vector& mang) { int n = mang.size(); for (int i=0;imang[j+1]) { //int temp = mang[j]; //mang[j]=mang[j+1]; //mang[j+1] = temp; swap(mang[j],mang[j+1]); } } } } int main() { vector mang = {5,3,8,6,2}; bubble(mang); for (int x:mang) cout<mang[j+1]: mang[j], mang[j+1] = mang[j+1], mang[j]
mang = [5,3,8,6,2] bubble(mang) print("Danh sach sap xep",mang) 3.2. INSERTION SORT Ý tưởng ● Insertion Sort mô phỏng cách xếp bài trên tay: 1. Giả sử các phần tử bên trái (0..i-1) đã được sắp xếp. 2. Lấy phần tử thứ i (gọi là key), “chèn” nó vào vị trí thích hợp trong đoạn [0..i-1]. Phân tích độ phức tạp ● Trung bình và tệ nhất: Khi dữ liệu ngẫu nhiên hoặc giảm dần ⇒ O(n^2). ● Tốt nhất: Nếu mảng đã gần sắp xếp (tăng dần), chỉ cần so sánh ≈1 lần cho mỗi i ⇒ O(n). ● Trong thực tế, Insertion Sort nhanh khi n nhỏ hoặc mảng “gần” sắp xếp. Ví dụ ○ 5,3,8,6,2 -> Lần lặp đầu tiên (i = 1): ○ key = 3, j = 0 (phần tử trước key là 5). ○ So sánh: ○ 5>3: Di chuyển 5 sang phải → 5,5,8,6,2 ○ Chèn key vào vị trí j + 1 = 0 → 3,5,8,6,2 Lần lặp thứ hai (i = 2): ○ key = 8, j = 1 (phần tử trước key là 5). ○ So sánh: