Sort « 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 …..

Chuyên mục: Cấu trúc dữ liệu, Thuật toán
Từ khóa: , , , ,

Thuật toán Sắp xếp chọn - Selection Sort

Thuật toán sắp xếp chọn - Selection Sort | MicrosoftTech.Net

1. Bài toán sắp xếp chọn

Trong quá trình thao tác dữ liệu, sẽ có những trường hợp cần phải sắp xếp dữ liệu trong danh sách theo một thứ tự nào đó theo các yêu cầu. Tùy từng loại cấu trúc dữ liệu khác nhau sẽ có phương án sắp xếp tối ưu cho cấu trúc dữ liệu đó. Xét giới hạn trong kiểu dữ liệu danh sách đơn giản là mảng các phần tử, Sắp xếp chọn – Selection Sort là một kiểu sắp xếp đơn giản nhất, thuật toán rõ ràng, dễ hiểu.

Tư tưởng của của thuật toán này như sau: Sẽ có n – 1 vòng lặp duyệt qua danh sách (n là tổng số phần tử), tại mỗi vòng lặp sẽ chọn phần tử nhỏ nhất đưa lên đầu danh sách. Như vậy sau vòng lặp thứ nhất thu được phần tử nhỏ nhất tại vị trí đầu tiên, sau vòng lặp thứ 2 thu được phần tử nhỏ nhất trong danh sách còn lại (không tính phần tử thứ 2) tại vị trí thứ hai… cứ như vậy cho đến vòng lặp thứ n – 1 sẽ còn 2 phần tử, ta lấy phần tử nhỏ hơn đưa vào vị trí thứ n – 1 và tất nhiên vị trí cuối cùng sẽ là phần tử lớn nhất. Tại mỗi vòng lặp để xác định phần tử có giá trị nhỏ nhất ta cần dùng thêm một …..

Chuyên mục: Cấu trúc dữ liệu, Thuật toán
Từ khóa: , ,

Array Method 3

Array Method | Tìm hiểu các phương thức thông dụng của class Array | MicrosoftTech.Net

1. Array.Find Phương thức Find hỗ trợ tìm kiếm phần tử trong một danh sách, và kết quả trả về chính là phần tử tìm thấy. Đối số tìm kiếm có thể linh hoạt thông qua các hàm xử lý chuỗi thông dụng hoạt động bên dưới đối tượng element như trong ví dụ bên dưới. Trong ví dụ tôi minh họa một số dạng Find khác nhau với các kiểu đối số tìm kiếm linh hoạt. Đầu tiên là phương thức Find với đối số là một chuỗi chính xác, thứ hai là tìm giá trị bắt đầu của một chuỗi, thứ ba là tìm theo chiều dài chuỗi và cuối cùng là tìm tất cả các phần tử thỏa mãn một yêu cầu đưa ra. Phương thức FindAll để tìm tất cả phần tử thỏa mãn một yêu cầu nào đó và tất nhiên kết quả trả về là một danh sách các phần tử chứ không phải là một phần tử độc lập như phương thức Find.

2. Array.IndexOf | Array.LastIndexOf Phương thức IndexOf trả về vị trí xuất hiện của một phần tử trong danh sách, nếu trường hợp danh sách có nhiều phần tử thỏa mãn điều kiện đưa ra thì kết quả trả về thuộc về phần tử đầu tiên. Trường hợp không tìm thấy phần tử thỏa mãn yêu cầu thì kết quả trả về là -1. Phương thức LastIndexOf hoạt động ngược lại với IndexOf, thay vì …..

Chuyên mục: Array - Collection, Csharp
Từ khóa: , , , , ,