0912. Sort An Array
- Nhãn: Mảng, Phân chia, Sắp xếp thùng, Sắp xếp đếm, Sắp xếp cơ số, Sắp xếp, Heap (hàng đợi ưu tiên), Sắp xếp trộn
- Độ khó: Trung bình
Tóm tắt đề bài
Mô tả: Cho một mảng số nguyên .
Yêu cầu: Sắp xếp mảng theo thứ tự tăng dần.
Giải thích:
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng giải quyết
Đây là một bài tốt để ôn tập các thuật toán sắp xếp và kiểm tra độ phức tạp thời gian của các thuật toán. Tôi đã thử nghiệm mười thuật toán sắp xếp. Dưới đây là kết quả:
- Thuật toán quá chậm (độ phức tạp thời gian là ): Sắp xếp nổi bọt (Bubble Sort), Sắp xếp chọn (Selection Sort), Sắp xếp chèn (Insertion Sort).
- Thuật toán vừa phải (độ phức tạp thời gian là ): Sắp xếp Shell (Shell Sort), Sắp xếp trộn (Merge Sort), Sắp xếp nhanh (Quick Sort), Sắp xếp heap (Heap Sort).
- Thuật toán vừa phải (độ phức tạp thời gian là ): Sắp xếp đếm (Counting Sort), Sắp xếp thùng (Bucket Sort).
- Thuật toán không đúng (Sắp xếp cơ số thông thường chỉ phù hợp cho số không âm): Sắp xếp cơ số (Radix Sort).
Ý tưởng 1: Sắp xếp nổi bọt (quá chậm)
Sắp xếp nổi bọt (Bubble Sort) ý tưởng cơ bản: Thông qua nhiều lần lặp, thông qua so sánh và trao đổi giữa các phần tử kề nhau, để các phần tử nhỏ hơn dần từ sau lên trước, các phần tử lớn hơn dần từ trước xuống sau.
Giả sử mảng có phần tử, thuật toán sắp xếp nổi bọt như sau:
- Lần lặp thứ “nổi bọt”: Thực hiện “nổi bọt” cho phần tử đầu tiên, để phần tử có giá trị lớn nhất đứng ở vị trí cuối cùng.
- So sánh phần tử thứ và phần tử thứ , nếu phần tử thứ lớn hơn phần tử thứ , hoán đổi vị trí của hai phần tử.
- Tiếp tục so sánh phần tử thứ và phần tử thứ , nếu phần tử thứ lớn hơn phần tử thứ , hoán đổi vị trí của hai phần tử.
- Tiếp tục quá trình so sánh và hoán đổi cho đến khi so sánh phần tử thứ và phần tử thứ .
- Sau lần lặp này, phần tử lớn nhất trong phần tử đầu tiên sẽ được đặt ở vị trí cuối cùng.
- Lần lặp thứ “nổi bọt”: Thực hiện “nổi bọt” cho phần tử đầu tiên, để phần tử có giá trị lớn nhất thứ đứng ở vị trí thứ .
- So sánh phần tử thứ và phần tử thứ , nếu phần tử thứ lớn hơn phần tử thứ , hoán đổi vị trí của hai phần tử.
- Tiếp tục so sánh phần tử thứ và phần tử thứ , nếu phần tử thứ lớn hơn phần tử thứ , hoán đổi vị trí của hai phần tử.
- Tiếp tục quá trình so sánh và hoán đổi cho đến khi so sánh phần tử thứ và phần tử thứ .
- Sau lần lặp này, phần tử lớn nhất thứ trong phần tử đầu tiên sẽ được đặt ở vị trí thứ .
- Tiếp tục lặp lại quá trình trên cho đến khi không có sự hoán đổi nào xảy ra trong một lần lặp. Khi đó, mảng đã được sắp xếp.
Ý tưởng 1: Code
Ý tưởng 1: Độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 2: Sắp xếp chọn (quá chậm)
Sắp xếp chọn (Selection Sort) ý tưởng cơ bản: Chia mảng thành hai phần, bên trái là phần đã sắp xếp và bên phải là phần chưa sắp xếp. Tại mỗi bước, tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đặt nó vào cuối phần đã sắp xếp.
Giả sử mảng có phần tử, thuật toán sắp xếp chọn như sau:
- Lần lặp thứ : Tìm phần tử nhỏ nhất trong phần tử và đặt nó vào vị trí đầu tiên.
- Lần lặp thứ : Tìm phần tử nhỏ nhất trong phần tử còn lại và đặt nó vào vị trí thứ .
- Lặp lại quá trình trên cho đến khi không còn phần tử nào cần sắp xếp.
Ý tưởng 2: Code
Ý tưởng 2: Độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 3: Sắp xếp chèn (Insertion Sort) (Quá chậm)
Ý tưởng cơ bản của sắp xếp chèn (Insertion Sort): Chia mảng thành hai phần, phần bên trái là một mảng đã được sắp xếp và phần bên phải là một mảng chưa được sắp xếp. Mỗi lần lấy một phần tử từ mảng chưa được sắp xếp và chèn nó vào đúng vị trí trong mảng đã được sắp xếp.
Giả sử mảng có n phần tử, các bước của thuật toán sắp xếp chèn như sau:
- Ban đầu, mảng đã được sắp xếp chỉ có một phần tử là phần tử đầu tiên của mảng ban đầu.
- Lần lượt lấy từng phần tử trong mảng chưa được sắp xếp và chèn nó vào đúng vị trí trong mảng đã được sắp xếp.
- Để chèn một phần tử vào mảng đã được sắp xếp, ta so sánh phần tử đó với các phần tử trong mảng đã được sắp xếp từ phải qua trái. Nếu phần tử đó nhỏ hơn các phần tử đã được sắp xếp, ta dịch chuyển các phần tử sang phải để tạo chỗ trống cho phần tử đó và chèn phần tử đó vào vị trí thích hợp.
- Lặp lại quá trình trên cho đến khi tất cả các phần tử trong mảng chưa được sắp xếp đều được chèn vào mảng đã được sắp xếp.
Ý tưởng 3: Code
Ý tưởng 3: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 4: Sắp xếp Shell (Shell Sort) (Hoạt động)
Ý tưởng cơ bản của sắp xếp Shell (Shell Sort): Chia mảng thành các mảng con bằng cách chọn một khoảng cách nhất định, sau đó sắp xếp từng mảng con bằng thuật toán sắp xếp chèn. Tiếp tục giảm khoảng cách và sắp xếp lại các mảng con cho đến khi khoảng cách là 1, sau đó sắp xếp toàn bộ mảng bằng thuật toán sắp xếp chèn.
Giả sử mảng có n phần tử, các bước của thuật toán sắp xếp Shell như sau:
- Chọn một khoảng cách giữa các phần tử.
- Chia mảng thành các mảng con dựa trên khoảng cách này, bắt đầu từ phần tử thứ 1 và cách nhau khoảng cách.
- Sắp xếp từng mảng con bằng thuật toán sắp xếp chèn.
- Giảm khoảng cách và chia lại mảng thành các mảng con mới, sau đó sắp xếp lại các mảng con.
- Lặp lại quá trình trên cho đến khi khoảng cách là 1, sau đó sắp xếp toàn bộ mảng bằng thuật toán sắp xếp chèn.
Ý tưởng 4: Code
Ý tưởng 4: Phân tích độ phức tạp
- Độ phức tạp thời gian: Trung bình từ đến .
- Độ phức tạp không gian: .
Ý tưởng 5: Sắp xếp trộn (Merge Sort)
Ý tưởng cơ bản của sắp xếp trộn (Merge Sort): Sử dụng phương pháp chia để trị, trước tiên chia đều mảng hiện tại thành hai nửa, sau đó kết hợp hai mảng đã sắp xếp thành một mảng đã sắp xếp.
Giả sử mảng có phần tử, thuật toán sắp xếp trộn có các bước như sau:
- Quá trình chia: Đầu tiên, chia đều mảng hiện tại thành hai nửa bằng cách đệ quy cho đến khi độ dài của mảng con là .
- Tìm vị trí trung tâm của mảng và chia mảng thành hai mảng con và .
- Đệ quy chia mảng con và .
- Cuối cùng, mảng được chia thành mảng con đã được sắp xếp có độ dài .
- Quá trình trộn: Bắt đầu từ các mảng con đã được sắp xếp có độ dài , kết hợp lần lượt hai mảng con đã sắp xếp cho đến khi có một mảng đã sắp xếp có độ dài .
- Sử dụng một mảng để lưu trữ mảng đã được kết hợp.
- Sử dụng hai con trỏ và để trỏ đến vị trí bắt đầu của hai mảng con đã sắp xếp và .
- So sánh hai phần tử mà con trỏ đang trỏ đến, lấy phần tử nhỏ hơn và thêm vào mảng kết quả , sau đó di chuyển con trỏ đến vị trí tiếp theo.
- Lặp lại bước 3 cho đến khi một trong hai con trỏ đến cuối mảng con.
- Thêm các phần tử còn lại của mảng con còn lại vào mảng kết quả .
- Trả về mảng đã được kết hợp .
Ý tưởng 5: Code
Ý tưởng 5: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 6: Sắp xếp nhanh (Quick Sort)
Ý tưởng cơ bản của sắp xếp nhanh (Quick Sort): Sử dụng phương pháp chia để trị, chọn một phần tử trong mảng làm “phần tử chốt” và sắp xếp các phần tử trong mảng sao cho các phần tử nhỏ hơn “phần tử chốt” nằm bên trái và các phần tử lớn hơn “phần tử chốt” nằm bên phải. Sau đó, tiếp tục sắp xếp các phần tử bên trái và bên phải “phần tử chốt” theo cùng phương pháp cho đến khi mảng đã được sắp xếp.
Giả sử mảng có phần tử, thuật toán sắp xếp nhanh có các bước như sau:
- Phân hoạch: Chọn một phần tử trong mảng làm “phần tử chốt” và sắp xếp các phần tử trong mảng sao cho các phần tử nhỏ hơn “phần tử chốt” nằm bên trái và các phần tử lớn hơn “phần tử chốt” nằm bên phải.
- Chọn một phần tử làm “phần tử chốt” (ở đây chọn phần tử đầu tiên trong mảng làm “phần tử chốt”, tức ).
- Sử dụng hai con trỏ và để duyệt mảng, bắt đầu từ đầu mảng, bắt đầu từ cuối mảng.
- Di chuyển con trỏ từ phải sang trái, tìm phần tử đầu tiên nhỏ hơn “phần tử chốt”.
- Di chuyển con trỏ từ trái sang phải, tìm phần tử đầu tiên lớn hơn “phần tử chốt”.
- Hoán đổi vị trí của hai phần tử mà con trỏ và đang trỏ đến.
- Lặp lại bước 3 đến bước 5 cho đến khi con trỏ và gặp nhau, sau đó đặt “phần tử chốt” vào vị trí cuối cùng của mảng con đã phân hoạch.
- Đệ quy chia: Sau khi phân hoạch xong, tiếp tục sắp xếp các phần tử bên trái và bên phải “phần tử chốt” bằng cùng phương pháp.
- Dựa vào vị trí “phần tử chốt” để chia mảng thành hai mảng con.
- Đệ quy sắp xếp các mảng con bên trái và bên phải, cho đến khi mỗi mảng chỉ còn một phần tử, sau đó kết hợp các mảng con đã sắp xếp.
Ý tưởng 6: Code
Ý tưởng 6: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 7: Sắp xếp vun đống (Heap Sort)
Ý tưởng cơ bản của sắp xếp heap (Heap Sort): Sử dụng cấu trúc dữ liệu heap để thiết kế thuật toán sắp xếp. Chuyển mảng thành một max heap, lặp lại việc lấy ra phần tử lớn nhất từ heap và duy trì tính chất heap cho phần còn lại của mảng.
Giả sử mảng có phần tử, thuật toán sắp xếp heap có các bước như sau:
- Xây dựng heap ban đầu:
- Định nghĩa một mảng để lưu trữ cấu trúc dữ liệu heap và sao chép các phần tử của mảng gốc vào mảng heap (giữ nguyên thứ tự ban đầu).
- Bắt đầu từ vị trí giữa của mảng, từ phải sang trái, lần lượt thực hiện việc “điều chỉnh xuống” để chuyển mảng thành một max heap.
- Hoán đổi và điều chỉnh heap:
- Hoán đổi phần tử đầu tiên của heap (phần tử thứ nhất) với phần tử cuối cùng (phần tử cuối cùng của mảng), sau đó giảm kích thước của heap đi .
- Sau khi hoán đổi phần tử, do phần tử đầu tiên của heap thay đổi, cần thực hiện “điều chỉnh xuống” từ gốc của heap để duy trì tính chất heap.
- Lặp lại việc hoán đổi và điều chỉnh heap:
- Lặp lại bước , cho đến khi kích thước của heap là , tức là mảng đã được sắp xếp hoàn chỉnh theo thứ tự tăng dần.
Ý tưởng 7: Code
Ý tưởng 7: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 8: Sắp xếp đếm (Counting Sort)
Ý tưởng cơ bản của sắp xếp đếm (Counting Sort): Thông qua việc đếm số lần xuất hiện của mỗi phần tử trong mảng, dựa trên thông tin đếm này, sắp xếp các phần tử của mảng vào vị trí đúng để đạt được mục đích sắp xếp.
Giả sử mảng có phần tử, thuật toán sắp xếp đếm được thực hiện như sau:
-
Tính toán phạm vi sắp xếp: Duyệt qua mảng để tìm phần tử lớn nhất và phần tử nhỏ nhất trong mảng, tính toán phạm vi sắp xếp là .
-
Định nghĩa mảng đếm: Định nghĩa một mảng đếm có kích thước bằng phạm vi sắp xếp, dùng để đếm số lần xuất hiện của mỗi phần tử. Trong đó:
- Chỉ số của mảng đếm đại diện cho giá trị của phần tử .
- Giá trị của mảng đếm đại diện cho số lần xuất hiện của phần tử .
-
Thống kê số lần xuất hiện của các phần tử trong mảng: Duyệt qua mảng , đếm số lần xuất hiện của mỗi phần tử trong mảng đếm bằng cách tăng giá trị lên .
-
Tạo mảng tích lũy: Bắt đầu từ phần tử thứ của mảng đếm, tích lũy giá trị của mỗi phần tử bằng tổng giá trị của phần tử trước đó và chính nó. Lúc này, đại diện cho vị trí cuối cùng mà phần tử có giá trị xuất hiện trong mảng sắp xếp.
-
Điền ngược vào mảng kết quả: Duyệt qua mảng theo thứ tự ngược, điền mỗi phần tử vào vị trí đúng.
- Điền vào vị trí của mảng kết quả .
- Sau khi điền, giảm giá trị tại vị trí tương ứng trong mảng tích lũy, để có được vị trí đặt phần tử tiếp theo.
Ý tưởng 8: Code
Ý tưởng 8: Phân tích độ phức tạp
- Độ phức tạp thời gian: . Trong đó, là phạm vi giá trị của mảng đầu vào.
- Độ phức tạp không gian: . Trong đó, là phạm vi giá trị của mảng đầu vào.
Ý tưởng 9: Sắp xếp xô (Bucket Sort)
Ý tưởng cơ bản của sắp xếp xô (Bucket Sort): Chia các phần tử trong mảng thành các “xô” (bucket) và sau đó sắp xếp riêng từng xô.
Giả sử mảng có phần tử, thuật toán sắp xếp xô được thực hiện như sau:
- Xác định số lượng xô: Dựa trên phạm vi giá trị của mảng đầu vào, chia mảng thành xô, mỗi xô tương ứng với một khoảng giá trị.
- Phân phối các phần tử: Duyệt qua mảng đầu vào, phân phối từng phần tử vào xô tương ứng dựa trên giá trị của nó.
- Sắp xếp từng xô: Sắp xếp riêng từng xô, có thể sử dụng các thuật toán sắp xếp như sắp xếp chèn, sắp xếp trộn, sắp xếp nhanh, v.v.
- Kết hợp các phần tử trong các xô: Kết hợp các phần tử đã được sắp xếp trong các xô theo thứ tự khoảng giá trị để tạo thành một mảng đã sắp xếp hoàn chỉnh.
Ý tưởng 9: Code
Ý tưởng 9: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: . Trong đó, là số lượng xô.
Ý tưởng 10: Sắp xếp cơ số (Radix Sort)
Ý tưởng cơ bản của sắp xếp cơ số (Radix Sort): Chia các số thành các chữ số riêng biệt và sau đó sắp xếp từng chữ số theo thứ tự từ thấp đến cao.
Chúng ta sẽ lấy ví dụ với phương pháp ưu tiên số thấp nhất để giải thích các bước của thuật toán sắp xếp cơ số.
- Xác định số lượng chữ số lớn nhất trong dãy số: Duyệt qua các phần tử của mảng, tìm giá trị lớn nhất và xác định số lượng chữ số của nó.
- Từ chữ số thấp nhất (đơn vị) đến chữ số cao nhất, sắp xếp từng chữ số một:
- Định nghĩa một mảng xô có kích thước 10, mỗi xô đại diện cho một chữ số từ 0 đến 9.
- Dựa trên chữ số hiện tại của mỗi phần tử, đặt phần tử vào xô tương ứng.
- Xóa mảng ban đầu và sau đó lấy các phần tử từ các xô theo thứ tự và thêm vào mảng ban đầu.
- Trả về mảng đã được sắp xếp.
Ý tưởng 10: Code
Ý tưởng 10: Phân tích độ phức tạp
- Độ phức tạp thời gian: . Trong đó, là số lượng phần tử cần sắp xếp và là số lượng chữ số lớn nhất trong dãy số.
- Độ phức tạp không gian: .