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

Bài giảng Kỹ thuật lập trình C: Chương 7 - ThS. Trần Quang Hải Bằng

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

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

Trong chương 7 Các thuật toán sắp xếp nằm trong bài giảng kỹ thuật lập trình C nhằm trình bày về các nội dung chính: bài toán sắp xếp, các giải thuật sắp xếp, đổi chỗ trực tiếp, các giải thuật sắp xếp, chọn trực tiếp, chèn trực tiếp.

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 C: Chương 7 - ThS. Trần Quang Hải Bằng

  1. 04/2010 Bài toán s p x p • Cho t p N ph n t , m i ph n t có m t s thu c tính K THU T L P TRÌNH C • D a vào 1 (ho c vài) thu c tính c a các ph n t ñ s p x p l i chúng theo tr t t m i. Chương 7: Các thu t toán s p x p bangtqh@hotmail.com bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 2 04/2010 04/2010 Bài toán s p x p Các gi i thu t s p x p • G m 2 bài toán con: • S p x p đ i ch tr c ti p - Interchange Sort – D a theo khoá s p x p đ nh v l i th t các • S p x p ch n tr c ti p – Selection Sort ph n t • S p x p chèn tr c ti p – Insertion Sort – Chuy n các ph n t c n s p v v trí m i. • S p x p n i b t – Buble Sort • S p x p n i b t c i ti n - Shaker Sort • Hai thao tác cơ b n • Shell sort – So sánh • Heap sort – Gán • Quick sort • Merge sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 3 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 4
  2. 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort • Khái ni m ngh ch th : • Tìm t t c ngh ch th , tri t tiêu chúng b ng – Xét m t m ng các s a0, a1, . an. cách hoán v 2 ph n t tương ng trong – N u có i aj, thì ta g i đó là m t ngh ch ngh ch th th . • M ng chưa s p x p s có ngh ch th • M ng đã có th t s không ch a ngh ch th bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 5 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 6 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort • Bư c 1 : i = 1; // b t đ u t ñ u dãy • Cho dãy s a: • Bư c 2 : j = i+1; //tìm các ph n t a[j] < a[i], j>i 12 2 8 5 1 6 4 15 • Bư c 3 : Trong khi j < N th c hi n N u a[j]
  3. 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 9 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 10 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 11 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 12
  4. 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Interchange Sort - K t qu 12 2 8 5 1 6 4 15 2 12 8 5 1 6 4 15 1 12 8 5 2 6 4 15 1 8 12 5 2 6 4 15 1 5 12 8 2 6 4 15 1 2 12 8 5 6 4 15 1 2 8 12 5 6 4 15 1 2 5 12 8 6 4 15 1 2 4 12 8 6 5 15 1 2 4 8 12 6 5 15 1 2 4 6 12 8 5 15 1 2 4 5 12 8 6 15 1 2 4 5 8 12 6 15 1 2 4 5 6 12 8 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 13 1 2 bangtqh@hotmail.com 4 K thu t l p 5 C - Thu 6 toán s p x p trình t 8 12 15 14 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Các gi i thu t s p x p void InterchangeSort(int a[], int N ) • S p x p đ i ch tr c ti p - Interchange Sort { • S p x p ch n tr c ti p – Selection Sort • S p x p chèn tr c ti p – Insertion Sort int i, j; • S p x p n i b t – Buble Sort for (i = 0 ; i
  5. 04/2010 04/2010 Ch n tr c ti p – Selection Sort Ch n tr c ti p – Selection Sort • Ch n ph n t nh nh t trong N ph n t ban ñ u • Bư c 1: i = 1; • Đưa ph n t này v v trí ñúng là ñ u dãy hi n hành • Bư c 2: Tìm ph n t a[min] nh nh t trong dãy hi n • Xem dãy hi n hành ch còn N-1 ph n t c a dãy hành t a[i] ñ n a[N] ban đ u – B t đ u t v trí th 2; • Bư c 3 : N u min ≠ i thì ð i ch a[min] và a[i] – L p l i quá trình trên cho dãy hi n hành... ñ n khi dãy hi n hành ch còn 1 ph n t • Bư c 4 : N u i < N-1 thì i = i+1; L p l i Bư c 2 Ngư c l i: D ng. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 17 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 18 04/2010 04/2010 Ch n tr c ti p – Selection Sort Ch n tr c ti p – Selection Sort • Cho dãy s a: 12 2 8 5 1 6 4 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 19 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 20
  6. 04/2010 04/2010 Ch n tr c ti p – Selection Sort Ch n tr c ti p – Selection Sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 21 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 22 04/2010 04/2010 Selection sort Các gi i thu t s p x p void SelectionSort(int a[],int N ) • S p x p đ i ch tr c ti p - Interchange Sort { • S p x p ch n tr c ti p – Selection Sort int min; // chæ soá phaàn töû nhoû nhaát trong daõy hieän haønh for (int i=0; i
  7. 04/2010 04/2010 Chèn tr c ti p – Insertion Sort Chèn tr c ti p – Insertion Sort • Gi s có m t dãy a1 , a2 ,... ,an trong ñó i ph n t • Bư c 1: i = 2; // gi s có ño n a[1] ñã ñ c s p đ u tiên a1 , a2 ,... ,ai-1 ñã có th t . • Bư c 2: 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 • Tìm cách chèn ph n t ai vào v trí thích h p c a • Bư c 3: D i ch các ph n t t a[pos] ñ n đo n đã đư c s p đ có dãy m i a1 , a2 ,... ,ai tr nên a[i-1] sang ph i 1 v trí ñ dành ch cho a[i] có th t . V trí này chính là v trí gi a hai ph n t ak- • Bư c 4: a[pos] = x; // có ño n a[1]..a[i] ñã ñ c s p 1 và ak th a ak-1 < ai < ak (1≤k≤i). • Bư c 5: i = i+1; N u i < n : L p l i Bư c 2. Ngư c l i : D ng. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 25 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 26 04/2010 04/2010 Chèn tr c ti p – Insertion Sort Chèn tr c ti p – Insertion Sort • Cho dãy s : 12 2 8 5 1 6 4 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 27 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 28
  8. 04/2010 04/2010 Chèn tr c ti p – Insertion Sort Insertion Sort – Caøi ñaët void InsertionSort(int a[], int N ) { int pos, i; int x;//löu tröõ a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn töû. for(i=1 ; i0)&&(a[pos-1]>x);pos--) a[pos] = a[pos-1]; a[pos] = x;// cheøn x vaøo daõy } } bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 29 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 30 04/2010 04/2010 Insertion Sort - K t qu Các gi i thu t s p x p • S p x p đ i ch tr c ti p - Interchange Sort 12 2 8 5 1 6 4 15 • S p x p ch n tr c ti p – Selection Sort 12 2 8 5 1 6 4 15 • S p x p chèn tr c ti p – Insertion Sort 2 12 8 5 1 6 4 15 • S p x p n i b t – Buble Sort 2 8 12 5 1 6 4 15 • S p x p n i b t c i ti n - Shaker Sort 2 5 8 12 1 6 4 15 • Shell sort 1 2 5 8 12 6 4 15 1 2 5 6 8 12 4 15 • Heap sort 1 2 4 5 6 8 12 15 • Quick sort • Merge sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 31 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 32
  9. 04/2010 04/2010 N i b t – Bubble Sort N i b t – Bubble Sort • Ý tư ng chính c a gi i thu t là xu t phát t cu i • Bư c 1 : i = 1; // l n x lý ñ u tiên • Bư c 2 : j = N; //Duy t t cu i dãy ng c v v trí i dãy, ñ i ch các c p ph n t k c n đ ñưa ph n t Trong khi (j > i) th c hi n: nh hơn trong c p ph n t ñó v v trí ñúng đ u dãy N u a[j] N - 1: H t dãy. D ng Ngư c l i : L p l i Bư c 2. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 33 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 34 04/2010 04/2010 N i b t – Bubble Sort N i b t – Bubble Sort • Cho dãy s a: 2 12 8 5 1 6 4 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 35 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 36
  10. 04/2010 04/2010 N i b t – Bubble Sort N i b t – Bubble Sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 37 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 38 04/2010 04/2010 N i b t – Bubble Sort Bubble sort - Caøi ñaët void BubbleSort(int a[], int N) { int i, j; for (i = 0 ; i < N-1 ; i++) for (j = N-1; j>i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 39 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 40
  11. 04/2010 04/2010 Bubble Sort - K t qu Các gi i thu t s p x p 12 2 8 5 1 6 4 15 • S p x p đ i ch tr c ti p - Interchange Sort 12 2 8 5 1 4 6 15 • S p x p ch n tr c ti p – Selection Sort 12 2 8 1 5 4 6 15 12 2 1 8 5 4 6 15 • S p x p chèn tr c ti p – Insertion Sort 12 1 2 8 5 4 6 15 • S p x p n i b t – Buble Sort 1 12 2 8 5 4 6 15 • S p x p n i b t c i ti n - Shaker Sort 1 12 2 8 4 5 6 15 • Shell sort 1 12 2 4 8 5 6 15 • Heap sort 1 2 12 4 8 5 6 15 • Quick sort 1 2 12 4 5 8 6 15 1 2 4 12 5 8 6 15 • Merge sort 1 2 4 12 5 6 8 15 1 2 4 5 12 6 8 15 1 2 4 5 6 12 8 15 1 2 bangtqh@hotmail.com 4 K thu t l p trình C - Thu6t toán s p x 8 5 p 12 15 41 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 42 04/2010 04/2010 Shaker Sort Shaker Sort void ShakeSort(int data[], int n){ • D a trên nguyên t c đ i ch tr c ti p Kh c int i, j, left, right, k; left = 0; right = d.n-1; k = n-1; ph c như c đi m c a Bubble Sort. while (left < right) { • Trong m i l n s p x p, duy t m ng theo 2 lư t for (j = right; j > left; j--) if (data[j]< data[j-1]){ t 2 phiá khác nhau : Doicho(data[j], data[j-1]); k =j; – Lư t đi: đ y ph n t nh v ñ u m ng } left = k; – Lư t v : đ y ph n t l n v cu i m ng for (j = left; j < right; j++) if (data[j]> data[j+1]) { • Ghi nh n l i nh ng đo n đã s p x p nh m ti t Doicho(data[j],data[j-1]); k = j; ki m các phép so sánh th a. } right = k; } } bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 43 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 44
  12. 04/2010 04/2010 Các gi i thu t s p x p Saép xeáp vun ñoáng - Heap sort • S p x p đ i ch tr c ti p - Interchange Sort • Ñònh nghóa heap: • S p x p ch n tr c ti p – Selection Sort – Heap laø moät daõy caùc phaàn töû aleft, aleft+1,... , aright • S p x p chèn tr c ti p – Insertion Sort thoaû caùc quan heä: • S p x p n i b t – Buble Sort • ai ≥ a2i • ai ≥ a2i+1 • S p x p n i b t c i ti n - Shaker Sort vôùi ∀i ∈ [left, right] • Shell sort – Khi ñoù (ai , a2i), (ai ,a2i+1) ñöôïc goïi laø caùc caëp • Heap sort phaàn töû lieân ñôùi. • Quick sort – Heap ñöôïc ñònh nghóa nhö treân ñöôïc duøng trong • Merge sort tröôøng hôïp saép xeáp taêng daàn, khi saép xeáp giaûm daàn phaûi ñoåi chieàu caùc quan heä. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 45 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 46 04/2010 04/2010 Ví duï daõy laø heap: Saép xeáp vun ñoáng – Heap sort 1 2 3 4 5 6 7 8 a1 Caùc phaàn töû cuûa daõy ñöôïc bieåu dieãn theo 15 12 8 5 1 4 6 2 a2 a3 caùc moái quan heä lieân ñôùi a4 a5 a6 a7 a8 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 47 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 48
  13. 04/2010 04/2010 Saép xeáp vun ñoáng - Heap sort Saép xeáp vun ñoáng - Heap sort • Moät soá tính chaát cuûa Heap: – Tính chaát 1: Neáu aleft, aleft+1, …, aright laø moät heap • Saép xeáp daõy taêng daàn qua 2 giai ñoaïn: thì khi caét boû moät soá phaàn töû ôû hai ñaàu cuûa heap, – Giai ñoaïn 1: hieäu chænh daõy ban ñaàu thaønh heap daõy con coøn laïi vaãn laø moät heap. – Tính chaát 2: Neáu a1, a2, …, an laø moät heap thì phaàn – Giai ñoaïn 2: saép xeáp heap coù ñöôïc sau giai ñoaïn töû a1 (ñaàu heap) luoân laø phaàn töû lôùn nhaát trong 1 thaønh daõy taêng daàn heap. – Tính chaát 3: Moïi daõy con aleft, aleft+1, ..., aright thoûa: 2left > right ñeàu laø heap. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 49 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 50 04/2010 04/2010 Heap sort – Giai ñoaïn 1 T o heap 1 2 3 4 5 6 7 8 //input: daõy (a, N) 12 2 8 5 1 6 4 15 12 2 8 15 1 6 4 5 //output: daõy (a, N) laø moät heap 12 15 8 2 1 6 4 5 • Böôùc 1: left = N/2; //Theâm caùc phaàn töû aleft, .., 12 15 8 5 1 6 4 2 a1 vaøo heap 15 12 8 5 1 6 4 2 • Böôùc 2: Trong khi left > 0 • n = 8, n/2 = 4 //Löu yù: ñoaïn aleft+1, …, aN ñaõ laø heap • Xu t phát t a[4], so sánh v i a[8] ñ i ch • Böôùc 21: Hieäu chænh ñoaïn aleft, …, aN thaønh heap • a[3] so sánh v i a[6], a[7] • Böôùc 22: left = left - 1; • a[2] so sánh v i a[4], a[5] ↔ a[2]↔a[4] //Heát laëp lan truy n so sánh a[4] v i a[8] • … bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 51 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 52
  14. 04/2010 04/2010 Heap sort – Giai ñoaïn 2 Heap sort – Giai ñoaïn 2 • Vaán ñeà: Saép xeáp heap a1, …, aN thaønh daõy taêng daàn //input: daõy (a, N) laø heap //Ñaët: right = N Ł daõy a1, …, aright laø heap. //output: daõy (a, N) saép taêng daàn • YÙ töôûng: • Böôùc 1: right = N; //Baét ñaàu thöïc hieän töø cuoái daõy – Theo tính chaát 2: a1 seõ laø phaàn töû lôùn nhaát, vì vaäy vò trí ñuùng • Böôùc 2: Trong khi right > 1 cuûa a1 phaûi laø right - cuoái daõy. //Ñöa phaàn töû lôùn nhaát (a1)veà vò trí right Ł Ñoåi choå (a1, aright) Ł ñöôïc theâm moät phaàn töû ôû ñuùng vò trí • Böôùc 2.1: Hoaùnvò (a1 , aright); q Theo tính chaát 3: daõy con a2, …, aright-1 vaãn laø heap //Loaïi boû phaàn töû lôùn nhaát ra khoûi heap Ł Giaûm right, theâm a1 vaøo daõy vaø hieäu chænh laïi • Böôùc 2.2: right := right -1; Ł daõy a1, …, aright laø heap. • Böôùc 2.3: Hieäu chænh ñoaïn a1, a2, …, aright thaønh heap //Heát laëp bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 53 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 54 04/2010 04/2010 Hi u ch nh heap Các gi i thu t s p x p 1 2 3 4 5 6 7 8 • S p x p đ i ch tr c ti p - Interchange Sort 15 12 8 5 1 6 4 2 • S p x p ch n tr c ti p – Selection Sort 2 12 8 5 1 6 4 15 12 2 8 5 1 6 4 15 • S p x p chèn tr c ti p – Insertion Sort 12 5 8 2 1 6 4 15 • S p x p n i b t – Buble Sort 4 5 8 2 1 6 12 15 • S p x p n i b t c i ti n - Shaker Sort • Shell sort • Đ i ch a[1] ↔ a[8] có 1 ph n t ñã ñúng v trí • Heap sort • Ti n hành tương t cho dãy n-1 ph n t • Quick sort Lưu ý: Ch c n xét ph n t a[1] • Merge sort bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 55 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 56
  15. 04/2010 04/2010 Quick sort – YÙ töôûng Quick sort – YÙ töôûng • Giaûi thuaät QuickSort saép xeáp daõy a1, a2 ..., aN döïa treân vieäc phaân hoaïch daõy ban ñaàu thaønh 3 phaàn : • Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc – Phaàn 1: Goàm caùc phaàn töû coù giaù trò khoâng lôùn hôn x phaân thaønh 3 ñoaïn: – Phaàn 2: Goàm caùc phaàn töû coù giaù trò baèng x – 1. ak < x , vôùi k = 1 .. j – Phaàn 3: Goàm caùc phaàn töû coù giaù trò khoâng beù hôn x – 2. ak = x , vôùi k = j+1 .. i-1 vôùi x laø giaù trò cuûa moät phaàn töû tuøy yù trong daõy – 3. ak > x , vôùi k = i..N ban ñaàu. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 57 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 58 04/2010 04/2010 Quick sort – YÙ töôûng Quick sort – YÙ töôûng • Ñoaïn thöù 2 ñaõ coù thöù töï. • Ñoaïn thöù 2 ñaõ coù thöù töï. • Neáu caùc ñoaïn 1 vaø 3 chæ coù 1 phaàn töû: ñaõ coù • Neáu caùc ñoaïn 1 vaø 3 coù nhieàu hôn 1 phaàn töû thöù töï thì daõy ban ñaàu chæ coù thöù töï khi caùc ñoaïn 1, 3 ñöôïc saép. khi ñoù daõy con ban ñaàu ñaõ ñöôïc saép. • Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh vieäc phaân hoaïch töøng daõy con theo cuøng phöông phaùp phaân hoaïch daõy ban ñaàu vöøa trình baøy … bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 59 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 60
  16. 04/2010 04/2010 Quick sort – Gi i thu t Quick sort – Phaân hoaïch daõy //input: daõy con aleft, …, aright • Böôùc 1: Neáu left ≥ right //daõy coù ít hôn 2 phaàn töû //output: daõy con chia thaønh 3 ñoaïn: ñoaïn 1 ≤ ñoaïn 2 ≤ ñoaïn 3 Keát thuùc; //daõy ñaõ ñöôïc saép xeáp • Böôùc 1: Choïn tuøy yù moät phaàn töû a[p] trong daõy con laø giaù trò moác: x = a[p]; • Böôùc 2: Phaân hoaïch daõy aleft … aright thaønh caùc • Böôùc 2: Duyeät töø 2 ñaàu daõy ñeå phaùt hieän vaø hieäu chænh caëp phaàn töû ñoaïn: aleft.. aj, aj+1.. ai-1, ai.. Aright a[i], a[j] vi phaïm ñieàu kieän – Böôùc 21: i = left; j = right; Ñoaïn 1 ≤ x – Böôùc 22: Trong khi (a[i]x) j--; Ñoaïn 3: ai.. aright ≥ x – Böôùc 24: Neáu i
  17. 04/2010 04/2010 Quick sort – Ví d Quick sort – Ví d • Phân ho ch đo n l =1, r = 3: • Phân ho ch đo n l = 5, r = 8: x = A[2] = 2 x = A[6] = 6 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 65 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 66 04/2010 04/2010 Quick sort – Caøi ñaët void QuickSort(int a[], int left, int right) • Phân ho ch đo n l = 7, r = 8: { x = A[7] = 6 int i, j, x; if (left ≥ right) return; x = a[(left+right)/2]; // choïn phaàn töû giöõa laøm giaù trò moác i = left; j = right; while(i < j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i
  18. 04/2010 04/2010 Các gi i thu t s p x p Merge sort – YÙ töôûng • S p x p đ i ch tr c ti p - Interchange Sort • Giaûi thuaät Merge sort saép xeáp daõy a1, a2, ..., • S p x p ch n tr c ti p – Selection Sort an döïa treân nhaän xeùt sau: • S p x p chèn tr c ti p – Insertion Sort – Moãi daõy a1, a2, ..., an baát kyø laø moät taäp hôïp caùc • S p x p n i b t – Buble Sort daõy con lieân tieáp maø moãi daõy con ñeàu ñaõ coù thöù töï. • S p x p n i b t c i ti n - Shaker Sort • Ví duï: daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi nhö • Shell sort goàm 5 daõy con khoâng giaûm (12); (2, 8); (5); (1, 6); • Heap sort (4, 15). • Quick sort – Daõy ñaõ coù thöù töï coi nhö coù 1 daõy con. • Merge sort Ł Höôùng tieáp caän: tìm caùch laøm giaûm soá daõy con khoâng giaûm cuûa daõy ban ñaàu. bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 69 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 70 04/2010 04/2010 Merge sort Merge sort – Ví d • Böôùc 1 : k = 1; // daõy con coù 1 phaàn töû laø daõy khoâng giaûm k = 1; Phaân phoái ñeàu luaân phieân • Böôùc 2 : Laëp trong khi (k < N) // daõy coøn hôn 1 daõy con – Böôùc 21: Phaân phoái ñeàu luaân phieân daõy a1, a2, …, an thaønh 2 1 2 3 4 5 6 7 8 daõy b, c theo töøng nhoùm k phaàn töû lieân tieáp nhau. 12 2 8 5 1 6 4 15 //b = a1, …, ak, a2k+1, …, a3k, … //c = ak+1, …, a2k, a3k+1, …, a4k, … – Böôùc 22: Troän töøng caëp daõy con goàm k phaàn töû cuûa 2 daõy b, c vaøo a. – Böôùc 23: k = k*2; bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 71 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 72
  19. 04/2010 04/2010 Merge sort – Ví d Merge sort – Ví d k = 1; Phaân phoái ñeàu luaân phieân k = 1; Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 12 8 1 4 2 5 6 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 73 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 74 04/2010 04/2010 Merge sort – Ví d Merge sort – Ví d k = 1; Troän töøng caëp ñöôøng chaïy k = 2; Phaân phoái ñeàu luaân phieân 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 12 5 8 1 6 4 15 12 8 1 4 2 5 6 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 75 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 76
  20. 04/2010 04/2010 Merge sort – Ví d Merge sort – Ví d k = 2; Troän töøng caëp ñöôøng chaïy k = 2; Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 12 1 6 2 12 1 6 5 8 4 15 5 8 4 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 77 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 78 04/2010 04/2010 Merge sort – Ví d Merge sort – Ví d k = 4; Phaân phoái ñeàu luaân phieân k = 4; Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 5 8 12 1 4 6 15 2 5 8 12 1 4 6 15 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 79 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 80
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