Đề tài Công nghệ thông tin: Các thuật toán sắp xếp cơ bản trình bày về sắp xếp chọn (Selection Sort), sắp xếp chèn (Insertion Sort), sắp xếp nổi bọt (Bubble Sort), sắp xếp nhanh (Quick Sort). Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích. | CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN Thành viên nhóm: 1. Nguyễn Chánh Đại 2. Mai Phước Vinh 3. Tất Huỳnh Anh Khôi CẦN THƠ, 2015 MỤC LỤC 1. SẮP XẾP CHỌN (SELECTION SORT) . 1 2. SẮP XẾP CHÈN (INSERTION SORT) 1 3. SẮP XẾP NỔI BỌT (BUBBLE SORT) 2 4. SẮP XẾP NHANH (QUICK SORT) 3 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN 1. Sắp xếp chọn (Selection Sort) a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. b. Giải thuật: Bước 1: i = 1 Bước 2: Tìm phần tử a[Min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n] Bước 3: Hoán vị a[Min] và a[i] Bước 4: Nếu i ≤ n-1 thì i = i + 1 và lặp lại bước 2, ngược lại thì c. Độ phức tạp: O(n2) d. Code tham khảo: void selectionSort(int a[], int n) { for (int i = 0; i = 0 && a[x] > key){ a[x+1] = a[x]; --x; } a[x+1] = key; } } 3. Sắp xếp nổi bọt (Bubble Sort) a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 2 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN b. Giải thuật: Bước 1: i = 0 Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) .
