Xem mẫu
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 4: Các phương pháp sắp xếp cơ bản
Định nghĩa bài toán sắp xếp
Phương pháp chọn (Selection sort)
Phương pháp chèn (Insertion sort)
Phương pháp đổi chỗ (Interchange sort)
Phương pháp nổi bọt (Bubble sort)
Phương pháp sắp xếp nhanh (Quick sort)
Định nghĩa bài toán sắp xếp
Phát biểu bài toán:
- Cho tập n đối tượng (phần tử).
- Hãy sắp xếp n đối tượng trên theo thứ tự tăng (giảm)
Tổ chức dữ liệu
- int n Số phần tử cần sắp xếp
- int A[n] Lưu trữ tập hợp n phần tử
Định nghĩa bài toán sắp xếp
Sắp xếp là một quá trình xử lý bố trí lại một danh sách
các đối tượng theo thứ tự nào đó.
Ví dụ: Cần sắp xếp danh sách thí sinh theo tên với thứ
tự Alphabet, hoặc sắp xếp danh sách sinh viên theo
điểm trung bình với thứ tự từ cao đến thấp.
Các đối tượng cần được sắp xếp thường có nhiều thuộc
tính chúng ta cần chọn một thuộc tính làm khóa và sắp
xếp theo khóa này.
Phương pháp chọn (Selection sort)
1. Ý tưởng
Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử
này về vị trí đầu của dãy.
Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị trí
thứ 2, lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại.
Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ
nhất trong dãy hiện hành về vị trí dẫn đầu
nguon tai.lieu . vn
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 4: Các phương pháp sắp xếp cơ bản
Định nghĩa bài toán sắp xếp
Phương pháp chọn (Selection sort)
Phương pháp chèn (Insertion sort)
Phương pháp đổi chỗ (Interchange sort)
Phương pháp nổi bọt (Bubble sort)
Phương pháp sắp xếp nhanh (Quick sort)
Định nghĩa bài toán sắp xếp
Phát biểu bài toán:
- Cho tập n đối tượng (phần tử).
- Hãy sắp xếp n đối tượng trên theo thứ tự tăng (giảm)
Tổ chức dữ liệu
- int n Số phần tử cần sắp xếp
- int A[n] Lưu trữ tập hợp n phần tử
Định nghĩa bài toán sắp xếp
Sắp xếp là một quá trình xử lý bố trí lại một danh sách
các đối tượng theo thứ tự nào đó.
Ví dụ: Cần sắp xếp danh sách thí sinh theo tên với thứ
tự Alphabet, hoặc sắp xếp danh sách sinh viên theo
điểm trung bình với thứ tự từ cao đến thấp.
Các đối tượng cần được sắp xếp thường có nhiều thuộc
tính chúng ta cần chọn một thuộc tính làm khóa và sắp
xếp theo khóa này.
Phương pháp chọn (Selection sort)
1. Ý tưởng
Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử
này về vị trí đầu của dãy.
Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị trí
thứ 2, lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại.
Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ
nhất trong dãy hiện hành về vị trí dẫn đầu