Tin tức mới

Chương 8 – Thuật toán sắp xếp(Tiếp*)_

Thuật toán sắp xếp

Sắp xếp được dữ liệu theo các trật tự và tiêu chí khác nhau

7. Bài tập

Bài 1: Minh hoạ thuật toán sắp xếp nổi bọt

Mục tiêu:

Hiểu rõ về cơ chế hoạt động của thuật toán sắp xếp nổi bọt.

Mô tả:

Hãy hiển thị tất cả các kết quả của từng bước sắp xếp để hiểu hơn về thuật toán sắp xếp nổi bọt.


Bài 2: Minh hoạ thuật toán sắp xếp chèn

Mục tiêu:

Hiểu rõ về cơ chế hoạt động của thuật toán sắp xếp chèn.

Mô tả:

Hãy hiển thị tất cả các kết quả của từng bước sắp xếp để hiểu hơn về thuật toán sắp xếp chèn.

Bài 3: Minh hoạ thuật toán sắp xếp chọn

Mục tiêu:

Hiểu rõ về cơ chế hoạt động của thuật toán sắp xếp chọn.

Mô tả:

Hãy hiển thị tất cả các kết quả của từng bước sắp xếp để hiểu hơn về thuật toán sắp xếp chọn.

Bài 4: Nối mảng đã được sắp xếp

Mục tiêu:

Luyện tập triển khai thuật toán sắp xếp chèn.

Mô tả:

Hãy viết một hàm để nối hai mảng arr1 và arr2 trong đó mảng arr1 đã được sắp xếp. Kết quả là mảng arr1 sẽ bao gồm các phần tử của arr2 và vẫn giữ được trật tự sắp xếp. Hàm này có mô tả như sau:

    function orderedMerge(arr1, arr2);

Trong đó:

  • arr1 là một mảng đã được sắp xếp
  • arr2 là một mảng bất kỳ

Ví dụ, nối mảng [1, 3, 5, 8, 9] với mảng [2, 1, 7, 4] thì sẽ được mảng [1, 1, 2, 3, 4, 5, 7, 8, 9].

8. Bài kiểm tra

Câu 1: Độ phức tạp của thuật toán sắp xếp nổi bọt là bao nhiêu?

  1. O(n)
  2. O(log(n))
  3. O(n2)
  4. O(1)

Câu 2: Độ phức tạp của thuật toán sắp xếp chèn là bao nhiêu?

  1. O(n)
  2. O(log(n))
  3. O(n2)
  4. O(1)

Câu 3: Độ phức tạp của thuật toán sắp xếp chọn là bao nhiêu?

  1. O(n)
  2. O(log(n))
  3. O(n2)
  4. O(1)

Câu 4: Nếu một danh sách có n phần tử và đã được sắp xếp thì thuật toán sắp xếp nổi bọt sẽ thực hiện bao nhiêu phép so sánh?

  1. n
  2. n – 1
  3. n!
  4. (n – 1)!

Câu 5: Trong thuật toán sắp xếp chọn, nếu chúng ta muốn sắp xếp theo trật tự giảm dần thì thao tác đầu tiên là sẽ tìm ra phần tử nhỏ nhất hay lớn nhất?

  1. Tìm phần tử nhỏ nhất
  2. Tìm phần tử lớn nhất

9. Tổng kết

  • Thuật toán sắp xếp nổi bọt so sánh hai phần tử liền kề nhau và hoán đổi vị trí cho nhau nếu cần thiết
  • Thuật toán sắp xếp chèn duyệt lần lượt qua phần tử và chèn nó vào vị trí phù hợp trong một danh sách con
  • Thuật toán sắp xếp chọn tìm ra phần tử nhỏ nhất (hoặc lớn nhất) trong danh sách và đưa nó về vị trí đầu tiên (hoặc cuối cùng)
  • Độ phức tạp trong trường hợp tệ nhất của các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt là O (n2)

Phụ lục: Tài nguyên lập trình

Sau khi bạn hoàn thành cuốn cẩm nang này, bạn đã có được các kiến thức và kỹ năng căn bản để có thể học nâng cao lên để chọn lựa việc tạo ra các ứng dụng chuyên biệt như web, ứng dụng di động, game… Dưới đây là danh sách các nơi mà bạn có thể tìm thấy thêm các tài liệu hỗ trợ cho quá trình học tập đó mà CodeGym cung cấp:

Blog của CodeGym (https://codegym.vn/blog)

Đây là nơi tập hợp nhiều bài viết liên quan đến việc học lập trình, bao gồm cả các bài viết kỹ thuật, các bài viết về công nghệ và cả các bài viết định hướng về nghề nghiệp.

GitHub của CodeGym (https://github.com/codegym-vn)

Đây là nơi tập trung các mã nguồn mà CodeGym sử dụng trong quá trình dạy học, các bạn có thể tìm thấy ở đây hàng trăm mã nguồn để tham khảo thuộc các công nghệ khác nhau như Java, PHP, .NET, Javascript, Android, React…

Ứng dụng luyện tập CodeGym Bob (https://bob.codegym.vn/home)

Đây là ứng dụng rất phù hợp cho những bạn mới bắt đầu đến để luyện tập và khẳng định các năng lực của mình. Ứng dụng này hoàn toàn miễn phí và sẽ tự động giúp bạn đánh giá mức độ thuần thục của mình trong việc áp dụng các kiến thức đã học được.

Trang blog của học viên của CodeGym (https://blog.codegym.vn)

Đây là nơi mà các học viên của CodeGym lưu lại những suy nghĩ của mình và những trải nghiệm trong suốt quá trình học tập. Bạn có thể tìm thấy ở đây những chia sẻ thú vị và hữu ích, giúp cho mình có thêm được những góc nhìn từ những người giống như mình.

Nhóm Học lập trình (https:// facebook.com/groups/hoclaptrinh.cg)

Đây là nơi mà những người mới bắt đầu học lập trình có thể tham gia và thảo luận, nhận được các tư vấn và lời khuyên từ những người đi trước.

Tạp chí Lập trình (https://tapchilaptrinh.vn)

Trang Tạp chí Lập trình cùng với các ấn phẩm hằng tháng của nó là nơi mà các lập trình viên tìm được rất nhiều kiến thức bổ ích, từ nhập môn cho đến chuyên sâu.

Các trang web về các công nghệ


Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

One thought on “Chương 8 – Thuật toán sắp xếp(Tiếp*)_”

Leave a Reply

Your email address will not be published.