quang cao hosting

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

Xem: 1033    Tải: 0   Thảo luận: 0   Mục: C / C++ / MFC   Lĩnh vực: Khác

0 điểm   ( 7 đánh giá ) File đã được kiểm thử

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 vòng lặp bên trong, như vậy sẽ có 2 vòng lặp lồng nhau. Ta nhận thấy rằng, đối với vòng lặp ngoài, khi đến lượt lặp lại thứ 2 thì phần tử đầu tiên sẽ không còn giá trị vì nó đã được đưa vào đúng vị trí, tương tự đến lần lặp thứ 3 thì 2 phần tử đầu tiên không còn giá trị, hay nói cách khác chúng là mảng có tính thứ tự đã được sắp xếp. Cứ như vậy đến lần lặp n – 1 thì n – 2 phần tử đầu tiên sẽ không còn giá trị. Ý nghĩa của việc này nhằm thu hẹp “quãng đường” của vòng lặp bên trong, nhằm tối ưu chi phí.

2. Cài đặt bài toán với mã nguồn Csharp

Chương trình được tổ chức trong class SelectionSort, thuộc tính của class là một mảng số nguyên. Ở phương thức khởi tạo (Constructure) sẽ đưa vào số lượng phần tử của mảng, sau đó gọi tới phương thức createRandom() để khởi tạo ngẫu nhiên giá trị cho mảng. Phương thức show() để xuất các phần tử của mảng ra màn hình. Cốt lõi của class nằm ở phương thức sort()

Trong phương thức sort ta thấy đầu tiên sẽ khởi tạo 2 biến: Min và temp. temp là biến tạm còn Min dùng để lưu giá trị nhỏ nhất ở mỗi vòng lặp. Ta thấy có 2 vòng lặp lồng nhau: Vòng lặp ngoài chạy từ 0 -> array.Length-1 (array.Length là số lượng phần tử của mảng) Vòng lặp bên trong sẽ có số bước lặp giảm dần theo vòng ngoài. Tại đầu mỗi bước của vòng lặp ngoài sẽ xác định phần tử thứ i là phần tử nhỏ nhất (tạm thời) tiếp đó trong vòng lặp trong sẽ tìm xem có phần tử nào có giá trị nhỏ hơn hay không. Mỗi lần kết thúc vòng lặp trong sẽ thu được 1 phần tử nhỏ nhất. Cứ như vậy cho đến khi hết danh sách.

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

Bài toán sắp xếp chọn Đăng ngày 15-02-2014  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. 5/10 1033

Thảo luận:

Để bình luận bạn phải đăng nhập thành viên.

File tương tự

Files cùng mục

 
Hỗ trợ kỹ thuật cho thành viên:
Số di động (Hotline): 085.99999.25
Thời gian làm việc:
Sáng: 8h-12h; Chiều: 13h30-17h30
(Nghỉ chiều T7, CN và các ngày lễ, tết)
Chat với Megacode
https://www.facebook.com/megacodevn
File gợi ý cho bạn
File tải nhiều nhất
Megacode.vn - Thư viện mã nguồn chia sẻ, tải file cho cộng đồng
Copyright © 2013-2016. All rights reserved. Bản quyền thuộc VinaGon
Địa chỉ: Số 38 Hàng Bè, Hàng Bạc, Hoàn Kiếm, Hà Nội.
Văn phòng giao dịch: Phòng 28, Tầng 6, HH1A Linh Đàm, Hoàng Mai, Hà Nội
Email: info@vinagon.com | Website: www.vinagon.com | Điện thoại: 085.99999.25;