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

PHÂN TÍCH CÁC GIẢI THUẬT SẮP XẾP

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:103

Báo xấu

220
lượt xem 63
download

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

Loop invariant là điều kiện cần đúng ngay trước khi bắt đầu vòng lặp và ngay sau mỗi lần lặp của vòng lặp. Trường hợp xấu nhất: khi dãy được sắp xếp theo chiều ngược lại, mỗi phần tử Ai được so sáng với mỗi phần tử của mảng con đã sắp.

Chủ đề:

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

Lưu

Nội dung Text: PHÂN TÍCH CÁC GIẢI THUẬT SẮP XẾP

1 P HÂN TÍCH CÁC GIẢI THUẬT S ẮP XẾP
Nội dung 2 Giải thuật InsertionSort  Các giải thuật chia để trị  Giải thuật Quicksort  Giải thuật Mergesort  Giải thuật HeapSort  Giải thuật Couting Sort 
Insertion Sort 3 DEMO_HUNG
Insertion Sort – Ý tưởng 4 Nhận xét:  Mọi dãy a[0] , a[1] ,..., a[n-1] luôn có i-1 phần tử đầu tiên a[0] ,  a[1] ,... , a[i-2] đã có thứ tự (i ≥ 2) Ý tưởng chính:  Tìm cách chèn phần tử a[i] vào vị trí thích hợp của đoạn đã  được sắp để có dãy mới a[0] , a[1] ,... , a[i-1] trở nên có thứ tự Vị trí này chính là pos thỏa :  a[pos-1] ≤ a[i ]< a[pos] (1≤ pos≤ i) Chương 4: Sắp xếp
Insertion Sort – Ví dụ 5 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 15 Chương 4: Sắp xếp
Insertion Sort – Ví dụ 6 Chèn a[1] vào (a[0], a[1]) pos 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 15 2 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 7 Chèn a[2] vào (a[0] … a[2]) pos 0 1 2 3 4 5 6 7 1 8 2 12 8 5 6 4 15 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 8 Chèn a[3] vào (a[0] … a[3]) pos 0 1 2 3 4 5 6 7 2 8 12 5 1 6 4 15 5 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 9 Chèn a[4] vào (a[0] … a[4]) pos 0 1 2 3 4 5 6 7 2 5 8 12 1 6 4 15 1 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 10 Chèn a[5] vào (a[0]… a[5]) pos 0 1 2 3 4 5 6 7 1 2 5 8 12 6 4 15 6 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 11 Chèn a[6] vào (a[0] … a[6]) pos 0 1 2 3 4 5 6 7 1 2 5 6 8 12 4 15 4 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 12 Chèn a[7] vào (a[0] … a[7]) pos 0 1 2 3 4 5 6 7 15 1 2 4 5 6 8 12 i x Chương 4: Sắp xếp
Insertion Sort – Ví dụ 13 pos 0 1 2 3 4 5 6 7 1 2 4 5 6 8 12 15 Chương 4: Sắp xếp
Insertion Sort – Đánh giá thuật toán 14 void InsertionSort(int a[], int n){ Cost times 0 int pos, key; c1 n 1 for(int i=1; i0 && key
̉ ̣ Giai thuât gia tăng (incremental algorithm) 15
Giải thuật Insertion Sort cost times INSERTION-SORT(A) c1 n 1 fo r j ← 2 to n c2 n1 do key ← A[ j ] 2 3 0 n1 Insert A[ j ] into the sorted sequence A[1 . . j -1] n2/2 so sánh ≈ 4 i← j-1 c4 n1n ∑ t w hile i >0 and A[i] >key 5 j =2 j c5 ∑ n (t j − 1) 6 do A[i +1] ← A[i] j =2 c6 ∑ n n /2 gán (t j − 1) 2 7 i← i– 1 ≈ j =2 c7 8 A[i +1] ← key
Insertion Sort – Đánh giá thuật toán 17 Đối với mỗi i = 1, 3,..., n -1, trong đó n  =length[A], gọi tJ là số lần kiểm tra vòng lặp while trong dòng 5 được thực thi Gọi T(n) là thời gian thực hiện thuật giải  T(n) = c1n + c2(n-1)+ c4(n-1)+ c5Σj=2,ntj+ c6Σj=2,n (tj-  1) + c7Σj=2,n (tj-1)+ c8(n-1) Chương 4: Sắp xếp
Insertion Sort – Đánh giá thuật toán 18 Trường hợp tốt nhất: Khi dãy đã được sắp xếp,j = 1   Dang an + b  đô phức tap la O(n) ̣ ̣ ̣ ̀ Chương 4: Sắp xếp
Trường hợp xấu nhất: khi day được săp theo chiêu ngược ̃ ́ ̀ ̣ lai, Môi phân tử A[i] được so sanh với môi phân tử cua mang ̃ ̀ ́ ̃ ̀ ̉ ̉ con đã săp A[1 .. i − 1], vì vây ti = j vơi j = 2, 3,..., n. ́ ̣ ́ n(n − 1) n n(n + 1) n ∑ ( j − 1) = 2 ∑ j= −1 2 j =2 j =2
Insertion Sort – Đánh giá thuật toán 20  Dang an2 + bn + c  đô phức tap la O(n2) ̣ ̣ ̣ ̀ Chương 4: Sắp xếp

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.