Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chương 2: Các thuật toán sắp xếp - Coggle Diagram
Chương 2: Các thuật toán sắp xếp
Selection sort (sắp xếp chọn)
Ý tưởng: bắt đầu với mảng có n phần tử, duyệt qua mảng để chọn ra p.tử nhỏ nhất & đưa p.tử đó lên đầu mảng. Bỏ qua p.tử đã sắp xếp đó, tiếp tục thực hiện sắp xếp phần mảng còn lại đến hết mảng
Độ phức tạp của thuật toán này là O(n^2)
Thuật toán Seclection sort không phụ thuộc vào tính chất của dữ liệu vào
Insertion sort (sắp xếp chèn)
Ý tưởng: chọn 1 p.tử ngoại trừ p.tử đầu tiên (gọi là p.tử P), so sánh P với các p.tử bên trái và dịch chuyển P sang trái cho đến khi P lớn hơn các p.tử bên trái. Thực hiện như vậy với các p.tử còn lại đến khi đến hết mảng
Độ phức tạp của thuật toán này là O(n^2)
Thuật toán này phụ thuộc vào tính chất của dữ liệu vào. Tức việc dịch chuyển P sang trái có được thực hiện hay không tùy thuộc vào các p.tử bên trái P
Bubble sort (sắp xếp nổi bọt)
Ý tưởng: lần lượt so sánh từng cặp p.tử liên tiếp nhau nhằm đưa các p.tử có giá trị lớn dần dần về phía cuối mảng. Các p.tử đã nằm đúng vị trí sẽ không được xét đến trong các lần sắp xếp kế tiếp
Độ phức tạp của thuật toán này là O(n^2)
Thuật toán này không phụ thuộc tính chất của tập dữ liệu đầu vào
Quick sort (sắp xếp nhanh)
Ý tưởng: dựa trên thuật toán Chia để trị
Chọn ra 1 p.tử gọi là p.tử chốt (Pivot)
Chia mảng ra làm 2 mảng với mảng bên trái gồm các p.tử bé hơn Pivot, mảng bên phải gồm các p.tử lớn hơn hoặc bằng Pivot
Tiếp tục thực hiện 2 bước trên với mảng con bên trái & mảng con bên phải
Cách chọn p.tử chốt: p.tử lớn nhất trong 2 p.tử có giá trị khác nhau đầu tiên
Độ phức tạp của thuật toán: O(n.logn)
Cách phân hoạch mảng: dùng 2 biến, 1 biến bắt đầu từ đầu mảng, 1 biến bắt đầu từ cuối mảng. Vừa di chuyển 2 biến, vừa đưa các p.tử sang bên mảng thích hợp. Kết thúc khi 2 biến vượt qua nhau
Heap sort (sắp xếp vung đống)
Heap: là cây nhị phân mà node cha có quy luật với node con như sau
Nếu giá trị của node cha ≥ giá trị của 2 node con thì gọi là Max Heap
Nếu giá trị của node cha ≤ giá trị của 2 node con thì gọi là Min Heap
Ý tưởng thuật toán: dựng mảng thành Heap, lấy node gốc của Heap đặt vào vị trí đúng thứ tự trong mảng, số node còn lại tiếp tục dựng thành Heap mới. Tiếp tục cho đến khi chỉ còn 2 node. Hoán đổi giá trị giữa 2 node đó & đưa 2 node đó vào vị trí đúng thứ tự trong mảng
Dựng mảng thành Heap
Chuyển mảng thành cây nhị phân
a[0] là node gốc của Heap
P.tử a[i] sẽ có con trái là a[2i+1] & con phải là a[2i+2]
Các node từ a[0] → a[(n-2)/2] sẽ có 2 con nếu n lẻ, nếu n chẵn thì a[(n-2)/2] sẽ chỉ có 1 con
Tùy theo loại Heap muốn dựng lên mà sắp xếp các node trong cây đúng với quy luật của loại Heap đó
Nếu dựng mảng thành Max Heap, mảng sẽ được sắp xếp tăng dần, nếu dựng mảng thành Min Heap thì ngược lại
Độ phức tạp của thuật toán là O(n.logn)
Merge sort (sắp xếp trộn)
Ý tưởng: dựa trên thuật toán Chia để trị
Chia mảng đã cho làm 2 phần bằng nhau, tiếp tục chia mỗi mảng con thành 2 phần bằng nhau. Chia cho đến khi mảng chỉ còn có 1 p.tử
Vừa gộp các mảng đã chia lại, vừa sắp xếp các p.tử trong đó. Cuối cùng sẽ là mảng mà các p.tử đã được sắp xếp
Độ phức tạp của thuật toán là O(n.logn)
Shell sort
Ý tưởng: cải tiến từ thuật toán Insertion sort
Gọi i là khoảng cách giữa cặp p.tử. Ban đầu i có giá trị là n/2
Sắp xếp các cặp p.tử có khoảng cách là i
Tính lại i = i/2 rồi tiếp tục thực hiện so sánh các cặp p.tử có khoảng cách là i. Thực hiện cho đến khi hết mảng hoặc i = 0
Độ phức tạp của thuật toán là O(n.logn)