zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Kỹ thuật lập trình: Chương 3.3 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Báo xấu

12
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Chương 3.3 cung cấp cho người đọc những kiến thức như: Kỹ thuật sắp xếp; Thuật toán sắp xếp; kỹ thuật tìm kiếm;...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 Kỹ thuật lập trình: Chương 3.3 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
KỸ THUẬT SẮP XẾP
Sắp xếp • Sắp xếp (sorting): sắp xếp là tiến trình sắp xếp lại dữ liệu theo thứ tự nào đó • Ví dụ 1 4 3 2 1 2 3 4 1, a 4,b 3,c 2,d 1,a 2,d 3,c 4,b Key • Khóa (key): • Một dữ liệu (trong danh sách dữ liệu) có thể có nhiều fields. • Field (có thể vài fields) dùng để sắp xếp gọi là khóa (key) 3
Sắp xếp • Chúng ta có thể sắp xếp • Các số (numbers) • Các từ, các chuỗi (words) • Các cặp (pairs) giá trị • Thứ tự sắp xếp được sử dụng nhiều nhất • Sắp xếp các số theo thứ tự • Sắp xếp các chuỗi theo thứ tự alphabet (thứ tự từ điển) • Chúng ta xét hình thức đơn giản nhất: sắp xếp dãy số nguyên 4
Sắp xếp • Bài toán sắp xếp • Cho mảng có 𝑛 số nguyên:𝑎 = (𝑎1 , 𝑎2 , … , 𝑎 𝑛 ). Hãy sắp xếp các phần tử theo thứ tự tăng dần 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎 𝑛 • Mảng trước khi sắp xếp 1 4 3 2 8 9 4 6 • Mảng đã được sắp xếp 1 2 3 4 4 6 8 9 5
Sắp xếp • Tại sao phải sắp xếp dữ liệu? • Giúp tìm kiếm (search) nhanh hơn • Giúp trộn (merge) các danh sách với nhau nhanh hơn • Sorting có thể coi như là công cụ thiết kế thuật toán 6
Thuật toán sắp xếp • Các lớp thuật toán sắp xếp (tùy đặc điểm dữ liệu) • Thuật toán 𝑂 𝑛2 • Thuật toán 𝑂 𝑛. log 𝑛 • Thuật toán 𝑂 𝑛 • Ba thuật toán cơ bản • Interchange sort/Selection sort: 𝑂(𝑛2 ) • Quick sort (sắp xếp nhanh): 𝑂(𝑛. log 𝑛) • Counting sort/Distribution sort: 𝑂(𝑛) 7
Interchange sort • Ý tưởng interchange sort • Xét từng phần tử 𝑎 𝑖 từ trái sang phải • Với phần tử 𝑎 𝑖 , so sánh 𝑎 𝑖 với các phần tử 𝑎 𝑗 đứng sau 𝑎 𝑖 • Nếu 𝑎 𝑖 > 𝑎 𝑗 thì Hoán vị 𝑎 𝑖 với 𝑎 𝑗 8
Interchange sort • Interchange sort • Lần lặp 1 1 2 3 4 4 6 8 9 1 4 3 2 8 9 4 6 1 4 3 2 8 9 4 6 9
Interchange sort • Interchange sort • Lần lặp 2 1 4 3 2 8 9 4 6 1 4 3 2 8 9 4 6 10
Interchange sort • Interchange sort • Lần lặp 2 1 4 3 2 8 9 4 6 1 3 4 2 8 9 4 6 1 2 4 3 8 9 4 6 1 2 4 3 8 9 4 6 11
Interchange sort • Interchange sort • Lần lặp 3 1 2 4 3 8 9 4 6 1 2 4 3 8 9 4 6 12
Interchange sort • Interchange sort • Lần lặp 3 1 2 4 3 8 9 4 6 1 2 3 4 8 9 4 6 13
Interchange sort • Interchange sort • Lần lặp 4 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 14
Interchange sort • Interchange sort • Lần lặp 5 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 15
Interchange sort • Interchange sort • Lần lặp 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 16
Interchange sort • Interchange sort • Lần lặp 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 1 2 3 4 4 8 9 6 1 2 3 4 4 6 9 8 17
Interchange sort • Interchange sort • Lần lặp 7 1 2 3 4 4 6 9 8 1 2 3 4 4 6 9 8 1 2 3 4 4 6 8 9 18
Interchange sort • Chương trình void InterchangeSort(int[] a) { for (int i=0; i
Interchange sort • Ưu điểm • Cài đặt nhanh • Cài đặt ít lỗi • Khuyết điểm • Chạy chậm khi số phần tử lớn • Khi nào nên sử dụng? • Thuật toán sắp xếp Đổi chổ được dùng khi kích thước dữ liệu nhỏ (𝑛 ≤ 5000) 20

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.