zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Chương 3: KỸ THUẬT SẮP XẾP

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:21

Báo xấu

52
lượt xem 6
download

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

Sắp xếp là thao tác cần thiết thường được thực hiện trong quá trình lưu trữ và quản lý dữ liệu. Thứ tự dữ liệu có thể tăng hay giảm, tăng hay giảm thuật toán sắp xếp là tương tự.

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: KỸ THUẬT SẮP XẾP

Môn: CẤU TRÚC DỮ LIỆU Chương 3: KỸ THUẬT SẮP XẾP 1
NỘI DUNG CHƯƠNG 3 Khái quát về sắp xếp 1. Các phương pháp sắp xếp (Sắp xếp trên dãy) 2. Sắp xếp bằng phương pháp chọn trực tiếp (Selection)  Sắp xếp bằng phương pháp chèn trực tiếp (Insertion)  Sắp xếp bằng phương pháp đổi chỗ trực tiếp  (Exchange) Sắp xếp bằng phương pháp trộn (Merge)  Các phương pháp sắp xếp (Sắp xếp trên tập tin) 1. Sắp xếp tập tin bằng phương pháp trộn  Sắp xếp tập tin theo chỉ mục  BÀI TẬP 2
1. Khái quát về sắp xếp Sắp xếp là thao tác cần thiết thường được th ực hiện trong quá trình lưu trữ và quản lý dữ liệu. Thứ tự dữ liệu có thể tăng hay giảm, tăng hay giảm thu ật toán sắp xếp là tương tự. Hai nhóm giải thuật sắp xếp Các giải thuật sắp xếp thứ tự nội (sx thứ tự trên mảng)  Các giải thuật sắp xếp thứ tự ngoại (sx thứ tự trên tập tin)  Xem như mỗi phần tử dữ liệu được xem xét có một thành phần khóa (Key) để nhận diện có kiểu dữ liệu T, các thành ph ần còn lại là thông tin (Info), như vậy mỗi phần tử có cấu trúc như sau: typedef struct DataElement { T Key; InfoData Info; } DataType; Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nh ận di ện 3
2. Sắp xếp trên dãy/mảng (tt) 2.1. Sắp xếp bằng phương pháp chọn trực tiếp (Selection Sort) Dãy a có N phần tử chưa có thứ tự. Chọn phần tử  nhỏ nhất của dãy này đưa lên đầu dãy. Sau lần chọn thứ nhất, còn lại N-1 phần tử chưa có  thứ tự. Tiếp tục thực hiện, sau N-1 lần lựa chọn và đưa phần tử nhỏ nhất lên trên  dãy a có thứ tự tăng dần. Để tìm phần tử nhỏ nhất của dãy dựa vào cách tìm  kiếm duyệt dãy tuần tự. 4
2. Sắp xếp trên dãy/mảng (tt) 2.1. (tt) Selection Sort: Thuật toán B1: i=1 B2: Tìm phần tử nhỏ nhất a[min] trong dãy từ a[i] đến a[n] B3: Hoán vị a[min] với a[i] B4: Nếu i
2. Sắp xếp trên dãy/mảng (tt) 2.1. (tt) Straight Selection Sort: Cài đặt thuật toán void SelectionSort(int a[], int n) { int i,j,min; for(i=0; i
2. Sắp xếp trên dãy/mảng (tt) 2.1. (tt) Straight Selection Sort: Cài đặt thuật toán void hoanvi(int &a, int &b) { int temp; temp=a; a=b; b=temp; } 7
2. Sắp xếp trên dãy/mảng (tt) 2.1. (tt) Chọn trực tiếp (Straight Selection Sort) Phân tích thuật toán: Trong mọi trường hợp  Số phép so sánh S = (N-1) + (N-2) +… + 1 = ½N(N-1)  Số phép hoán vị H = N-1  Trong trường hợp tốt nhất  Số phép gán Gmin = 2 x (N-1)  Trong trường hợp xấu nhất  Số phép gán Gmax = 2 x [(N-1) + (N-2) +… + 1]  Trong trường hợp trung bình  Số phép gán Gavg = (Gmin+Gmax)/2  8
2. Sắp xếp trên dãy/mảng (tt) 2.2. Sắp xếp bằng phương pháp chèn trực tiếp (Insertion Sort) a. thuật toán: Giả sử ta có dãy a1,a2,…,an trong đó i phần tử đầu tiên a1,a2,…,ai-1 đã có thứ tự. Ý tưởng của giải thuật là tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã sắp xếp để có dãy a1,a2,…,ai có thứ tự. Cho dãy a1,a2,…, an . Ta có thể xem như đã có đoạn gồm một phần tử a1 đã sắp xếp. Sau đó ta thêm a2 vào đoạn a1, sẽ có đoạn a1,a2 sắp xếp. Tương tự thêm a3 vào a1, a2… tiếp tục cho đến khi thêm an vào a1,a2,…,an-1. Các bước tiến hành như sau: 9
2. Sắp xếp trên dãy/mảng (tt) //giả sử a[1] đã được sắp B1: i=2; B2: x=a[i] Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào B3: Dời chổ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để dành chổ cho a[i] //có đoạn a[1],…,a[i] đã được sắp B4: a[pos]=x; B5: i=i+1 Nếu i
2. Sắp xếp trên dãy/mảng (tt) b. Ví dụ minh hoạ: vd-t50 c. Cài đặt: Void intersectionsort( int a[], int n) { int i,pos; int x; for(i=1;i=0)&&(a[pos]>x)) { a[pos+1]=a[pos]; //dời sang phải pos--; } a[pos+1]=x; // chèn x vào dãy } } 11
2. Sắp xếp trên dãy/mảng (tt) 2.3. Chèn trực tiếp (Straight Insertion Sort) (tt) Phân tích thuật toán Trong trường hợp tốt nhất  Số phép gán Gmin = 2 × (N-1)  Số phép so sánh Smin = 1 + 2 + … +(N-1) = N ×(N-1)/2  Số phép hoán vị Hmin = 0  Trong trường hợp xấu nhất  Số phép gán Gmax = [2 × (N-1)] + [1+2+…+(N-1)]  Số phép so sánh Smax = (N-1)  Số phép hoán vị Hmax = 0  Trong trường hợp trung bình  Số phép gán Gavg = (Gmin+Gmax)/2  Quá trình tìm vị trí chèn của phần t ử thứ K+1 và quá trình d ời 12
2. Sắp xếp trên dãy/mảng (tt) 2.3. Phương pháp đổi chỗ trực tiếp: a. Ý tưởng: Xuất phát từ đầu dãy, tìm tất cả các phần tử nhỏ hơn phần tử này, đổi chổ các phần tử tương ứng. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy 13
2. Sắp xếp trên dãy/mảng (tt) 2.3. Phương pháp đổi chỗ trực tiếp: b. Thuật toán: B1: i=1; //bắt đầu từ đầu dãy B2: j=i+1; //tìm các phần tử a[j]i B3: Trong khi j
2. Sắp xếp trên dãy/mảng (tt) 2.3. Phương pháp đổi chỗ trực tiếp: c. Ví dụ minh hoạ: d. Cài đặt: Void interchangesort (int a[], int n) { int i,j; for( i=0; i
2. Sắp xếp trên dãy/mảng 2.4. a. Thuật toán sắp xếp nổi bọt (Bubble Sort) Ý tưởng: Đi từ cuối mảng đến đầu mảng, nếu phần tử ở dưới  < phần tử đứng trên nó thì sẽ được “đưa lên trên”. Sau mỗi lần đi duyệt dãy, 1 phần tử sẽ được đưa lên  đúng chỗ của nó. Đối với mảng M có N phần tử thì sau N-1 lần đi duyệt dãy  dãy M có thứ tự tăng. 16
2. Sắp xếp trên dãy/mảng (tt) 2.4. a. Bubble Sort (tt) Thuật toán: B1: i = 1; // lần xử lý đầu tiên B2: j=n; //duyệt từ cuối dãy về I Trong khi i
2. Sắp xếp trên dãy/mảng (tt) 2.4. a. Bubble Sort (tt) Cài đặt thuật toán: void Swap(int &X, int &Y) { int Temp = X; X = Y; Y = Temp; } void BubbleSort(int a[], int n) { for(int i =0; ii; j--) if (a[j] < a[j-1]) Swap(a[j], a[j-1]); } 18
2. Sắp xếp trên dãy/mảng (tt) 2.4. a. Bubble Sort (tt) Phân tích thuật toán: Trong mọi trường hợp  Số phép gán G = 0  Số phép so sánh S = (N-1) + (N-2) +… + 1 = ½N(N-1)  Trong trường hợp tốt nhất  Số phép hoán vị các phần tử Hmin = 0  Trong trường hợp xấu nhất  Số phép hoán vị các phần tử Hmax = (N-1) + (N-2) +… + 1  19
2. Sắp xếp trên dãy/mảng (tt) 2.4. a. Bubble Sort (tt) Nhận xét thuật toán: Thuật toán đơn giản dễ cài đặt  Vói Bubble Sort, phần tử “nhỏ” ở dưới được đưa lên  rất nhanh nhưng phần tử “lớn” lại đi xuống chậm, không tận dụng được chiều ngược lại Thuật toán không nhận diện được các phần tử ở 2  đầu của mảng đã nằm đúng vị trí để giảm bớt quãng đường trong mỗi lần duyệt. 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.