Sorting « MicrosoftTech.Net

Thuật toán Sắp xếp Nổi bọt– Bubble Sort

Thuật toán sắp xếp Nổi bọt - Bubble Sort | MicrosoftTech.Net

1. Bài toán sắp xếp Nổi bọt

Như đã biết ở bài viết trước về thuật toán Sắp xếp chọn ta thấy rằng sau mỗi vòng lặp ta lựa được một phần tử nhỏ nhất đưa về đầu danh sách, các phần tử còn lại hầu như không ảnh hưởng. Ta thấy rằng kết quả của vòng lặp trước không ảnh hưởng đến vòng lặp sau. Trong bài viết này chúng ta sẽ xét tới thuật toán sắp xếp Nổi bọt – Cải tiển hơn so với Thuật toán sắp xếp chọn.

Với thuật toán này, sẽ có 2 vòng lặp lồng nhau. Tại mỗi vòng lặp con sẽ chạy từ cuối danh sách trở về đầu danh sách. tại mỗi bước sẽ so sánh 2 phần tử kế cận nhau nếu phần tử nào nhỏ hơn sẽ được đảo về phía trước. Trong mỗi vòng lặp con, phần tử nhỏ nhất sẽ lần lượt được đưa về đầu dòng theo phương pháp tráo đổi – Đúng với tư tưởng “Nổi bọt” phần tử nhỏ sẽ dần được nổi lên trên cùng. Đặc điểm tối ưu hơn so với Sắp xếp chọn là tại mỗi vòng lặp con do có quá trình tráo đổi phần tử nhỏ về đầu dãy nên các phần tử lớn dần được đưa về cuối dãy và đồng thời những giá trị nhỏ cũng dần được đưa về đầu dãy. Đối với phương pháp sắp xếp chọn có tối …..

Sorting Dictionary

Ở bài viết trước chúng ta vừa tìm hiểu về một kiểu dữ liệu dạng danh sách là Dictionary, qua bài viết vừa rồi chắc bạn phần nào cũng thấy được những ưu điểm của như tính tiện dụng khi dùng kiểu dữ liệu này. Với bài viết hôm nay chúng ta sẽ tìm hiểu cách để sắp xếp danh sách giá trị trong Dictionary, nói cụ thể là sắp xếp danh sách Keys và Values. Xét về bản chất của Dictionary không có phương thức hỗ trợ sắp xếp theo Keys hay theo Values, các giá trị sau khi Add() luôn nằm cố định như vậy. (Cũng có thể có phương thức nào đó mà tôi chưa biết!.. ) Như vậy để có thể sắp xếp được ta cần chuyển qua một kiểu dữ liệu khác có hỗ trợ phương thức Sort(); Hoặc nếu không thích sử dụng phương thức Sort thì bạn cũng có thể tự viết hàm để sắp xếp nhưng như thế sẽ mất thời gian hơn mặc dù hiệu quả không khác gì nhiều…

1. Sorting Values In Dictionary

Trong ví dụ bên dưới ta sẽ tạo danh sách products với với trường có kiểu dữ liệu là string và int. Giã sử ta dùng để lưu giá tiền một số mặt hàng văn phòng phẩm. Sau đó tiến hành Add() một số phần tử mẫu cho danh sách. Ở đây sẽ sắp theo thứ tự tăng dần danh …..