intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P1)

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST
Báo xấu
75
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp (P1)" có cấu trúc gồm 3 phần cung cấp cho người học các kiến thức: Sắp xếp chọn (selection sort), sắp xếp nổi bọt (bubble sort), sắp xếp chèn (insertion sort). Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P1)

  1. Các thuật toán sắp xếp (p1) (sorting algorithms) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
  2. Các thuật toán sắp xếp - phần 1 • Sắp xếp chọn (selection sort) • Sắp xếp nổi bọt (bubble sort) • Sắp xếp chèn (insertion sort)
  3. Sắp xếp chọn (selection sort) • Cho dãy A gồm N phần tử a0, a1, …, aN-1 • Mỗi bước xét một danh sách con chưa sắp xếp (unsorted sublist - USL) • Có N-1 bước: − Bước 1: USL = {a0, a1, …, aN-1} − Bước 2: USL = {a1, …, aN-1} −… − Bước N-1: USL = {aN-2, aN-1}
  4. Sắp xếp chọn (tiếp) • Mỗi bước: − Tìm phần tử nhỏ nhất (amin) trong USL − Đổi chỗ amin và phần tử đầu tiên của USL − Dịch chuyển biên của USL sang phải một phần tử
  5. Sắp xếp chọn: Ví dụ • Ban đầu: 64, 25, 12, 22, 11 • Sau bước 1: 11, 25, 12, 22, 64 • Sau bước 2: 11, 12, 25, 22, 64 • Sau bước 3: 11, 12, 22, 25, 64 • Sau bước 4: 11, 12, 22, 25, 64 (danh sách con chưa sắp xếp được gạch chân)
  6. Cài đặt và phân tích sắp xếp chọn • Viết hàm selectionSort() • Chứng minh thời gian chạy là O(N2)
  7. Sắp xếp nổi bọt (bubble sort) • Mỗi bước: − So sánh hai phần tử kề nhau − Đổi chỗ nếu chúng chưa đúng thứ tự • Sau mỗi bước, phần tử lớn nhất sẽ được đặt (“nổi bọt”) xuống cuối dãy • Thời gian chạy: O(N2)
  8. Sắp xếp nổi bọt: Ví dụ • Ban đầu: 2, 3, 1, 15 • Sau bước 1: 2, 1, 3, 15 • Sau bước 2: 1, 2, 3, 15 • Sau bước 3: 1, 2, 3, 15 (danh sách con chưa sắp xếp được gạch chân)
  9. Sắp xếp nổi bọt: Cài đặt for (i = 0; i < N-1; i++) { for (j = 0; j < N-1-i; j++) if (a[j+1] < a[j]) { tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } • Trong trường hợp tốt nhất (dãy đã sắp xếp rồi), sắp xếp nổi bọt chỉ nên mất thời gian O(N)  hãy tối ưu hóa cài đặt bên trên!
  10. Sắp xếp chèn (insertion sort) • Có N-1 bước ứng với p = 1, 2, …, N-1 • Ở bước p: (khi bắt đầu bước p, các vị trí 0, …, p-1 đã được sắp xếp rồi) − Xác định vị trí phù hợp trong các vị trí 0, …, p-1 cho phần tử ở vị trí p (ap) − Chèn ap vào vị trí đã xác định, vì vậy các vị trí từ 0 đến p được sắp xếp
  11. Sắp xếp chèn: Ví dụ
  12. Sắp xếp chèn: Cài đặt
  13. Phân tích sắp xếp chèn • Trường hợp tốt nhất: O(N) • Trường hợp tồi nhất: O(N2)
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2