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 1: Chương 2 - Lương Trần Hy Hiến

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST
Báo xấu
65
lượt xem 5
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 1 chương 2 cung cấp các kiến thức về tìm kiếm và sắp xếp. Mục tiêu của chương này là giới thiệu một số thuật toán tìm kiếm và sắp xếp nội; phân tích, đánh giá độ phức tạp của các giải thuật tìm kiếm, sắp xếp. 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 1: Chương 2 - Lương Trần Hy Hiến

  1. Đại Họ Học Sư Phạ Phạm Tp. Hồ Hồ Chí Chí Minh Tìm kiếm & Sắp xếp Muïc tieâu: • Giôùi thieäu moät soá thuaät toaùn tìm kieám vaø saép xeáp noäi. CẤU TRÚC DỮ LIỆU 1 • Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa caùc giaûi thuaät tìm kieám, saép xeáp. Noäi dung: • Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong moät heä thoáng thoâng tin. • Caùc giaûi thuaät tìm kieám noäi. Chương 2: Tìm kiếm & Sắp xếp • Caùc giaûi thuaät saép xeáp noäi. 2 Tìm kiếm Caùc giaûi thuaät tìm kieám noäi Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû coù • Tìm tuần tự giaù trò x treân danh saùch ñaëc a •Caùc Tìmgiaûi nhị phân thuaät •Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá a1, a2, ... ,aN tìm kieám noäi int a[N]; •Khoaù caàn tìm laø x int x; 3 4
  2. Tìm kieám tuaàn töï Tìm kieám tuaàn töï • Böôùc 1: i = Vò trí ñaàu; • Ví duï: Cho daõy soá a • Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò trí 12 2 8 5 1 6 4 15 xuaát hieän: i • Giaù trò caàn tìm: 8 • Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn töû keá trong maûng • i=1 • Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng Khoâng tìm thaáy. Döøng. Ngöôïc laïi: Laëp laïi Böôùc 2. 5 6 Tìm kieám tuaàn töï Tìm kieá kieám tuaà tuaàn töï töï • i=2 int LinearSearch(int a[], int N, int x) { for (int i=0; (i
  3. Tìm kieám tuaàn töï Tìm kieám tuaàn töï • Caûi tieán caøi ñaët: duøng phöông phaùp “đặt lính int LinearSearch(int a[], int N, int x) { canh” // maûng goàm N phaàn töû töø a[0]..a[N-1] – Ñaët theâm moät phaàn töû coù giaù trò x vaøo cuoái maûng a[N] = x; // theâm lính canh vaøo cuoái daõy – Baûo ñaûm luoân tìm thaáy x trong maûng for (int i=0; (a[i]!=x); i++); – Sau ñoù döïa vaøo vò trí tìm thaáy ñeå keát luaän. if (i
  4. Tìm kieám nhò phaân Tìm kieám nhò phaân • Ñoái vôùi nhöõng daõy ñaõ sắp thöù töï (giaû söû thöù töï • YÙ töôûng cuûa giaûi thuaät laø taïi moãi böôùc tieán taêng), caùc phaàn töû trong daõy coù quan heä haønh so saùnh x vôùi phaàn töû naèm ôû vò trí giöõa ai -1 ≤ ai ≤ ai+1 cuûa daõy tìm kieám hieän haønh, döïa vaøo keát quaû Neáu x > ai thì x chæ coù theå xuaát hieän trong so saùnh naøy ñeå quyeát ñònh giôùi haïn daõy tìm ñoaïn [ai+1 ,aN] cuûa daõy kieám ôû böôùc keá tieáp laø nöûa treân hay nöûa döôùi cuûa daõy tìm kieám hieän haønh Neáu x < ai thì x chæ coù theå xuaát hieän trong ñoaïn [a1 ,ai-1] cuûa daõy 13 14 Tìm kieám nhò phaân Tìm kieám nhò phaân Böôùc 1: left = VTÑ; right = VTC; • Ví duï: Cho daõy soá a goàm 8 phaàn töû: Böôùc 2: Trong khi left ≤ right laëp: //ñoaïn tìm kieám chöa roãng Böôùc 2.1: mid = (left+right)/2; // laáy moác so saùnh 1 2 4 5 6 8 12 15 Böôùc 2.2: Neáu a[mid] = x: //Tìm thaáy. • Giaù trò caàn tìm laø 8 Döøng, vò trí xuaát hieän: mid Böôùc 2.3: Neáu a[mid] > x: //tìm x trong daõy con aleft .. amid -1 right = mid - 1; Ngöôïc laïi //tìm x trong daõy con amid +1 .. aright left = mid + 1; //Heát laëp Böôùc 3: Döøng, khoâng tìm thaáy. 15 16
  5. Tìm kieám nhò phaân Tìm kieám nhò phaân • left = 1, right = 8, mid = 4 • left = 5, right = 8, mid = 6 17 18 Tìm kieám nhò phaân Tìm kieám nhò phaân int BinarySearch(int a[],int N,int x ) • Ñaùnh giaù giaûi thuaät: { int left =0, right = N-1, midle; while (left
  6. Tìm kieám nhò phaân Tìm kieám nhò phaân Nhaän xeùt: Nhaän xeùt: – Giaûi thuaät tìm nhò phaân döïa vaøo quan heä giaù trò – Khi muoán aùp duïng giaûi thuaät tìm nhò phaân caàn cuûa caùc phaàn töû maûng ñeå ñònh höôùng trong quaù phaûi xeùt ñeán thôøi gian saép xeáp daõy soá ñeå thoûa trình tìm kieám, do vaäy chæ aùp duïng ñöôïc cho ñieàu kieän daõy soá coù thöù töï. Thôøi gian naøy khoâng nhöõng daõy ñaõ coù thöù töï. nhoû, vaø khi daõy soá bieán ñoäng caàn phaûi tieán haønh – Giaûi thuaät tìm nhò phaân tieát kieäm thôøi gian hôn saép xeáp laïi => khuyeát ñieåm chính cho giaûi thuaät raát nhieàu so vôùi giaûi thuaät tìm tuaàn töï do tìm nhò phaân. Tnhò phaân (n) = O(log 2 n) < Ttuaàn töï (n) = O(n). – Caàn caân nhaéc nhu caàu thöïc teá ñeå choïn moät trong hai giaûi thuaät tìm kieám treân sao cho coù lôïi nhaát. 21 22 Ñònh nghóa baøi toaùn saép xeáp Khaùi nieäm nghòch theá • Saép xeáp laø quaù trình xöû lyù moät danh saùch caùc • Khaùi nieäm nghòch theá: phaàn töû (hoaëc caùc maãu tin) ñeå ñaët chuùng theo – Xeùt moät maûng caùc soá a0, a1, … an. moät thöù töï thoûa maõn moät tieâu chuaån naøo ñoù – Neáu coù i aj, thì ta goïi ñoù laø moät nghòch döïa treân noäi dung thoâng tin löu giöõ taïi moãi theá. phaàn töû. • Maûng chöa saép xeáp seõ coù nghòch theá. • Löu yù: Thöù töï ñöôïc ñeà caäp ôû ñaây laø moät thöù • Maûng ñaõ coù thöù töï seõ khoâng chöùa nghòch theá. töï toång quaùt. a0 ≤ a1 ≤ … ≤ an • Ví duï: Haõy ñònh nghóa moät thöù töï ñeå daõy soá sau laø daõy taêng theo thöù töï naøy. 1 3 5 7 22 20 10 623 24
  7. Caùc phöông phaùp saép xeáp thoâng duïng Selection sort – YÙ töôûng • Selection sort • Shell sort • Nhaän xeùt: Maûng coù thöù töï thì Phöù Phöùc taï taïp hôn • Insertion sort • Heap sortHieä Hieä u quaû qua û cao ai = min(ai, ai+1, …, an-1) YÙ töôûng: moâ phoûng moät trong nhöõng caùch saép • Interchange sort • Quick sort xeáp töï nhieân nhaát trong thöïc teá: • Bubble sort • Merge sort – Choïn phaàn töû nhoû nhaát trong N phaàn töû ban ñaàu, • Shaker sort • Radix sort ñöa phaàn töû naøy veà vò trí ñuùng laø ñaàu daõy hieän haønh • Binary Insertion • … – Xem daõy hieän haønh chæ coøn N-1 phaàn töû cuûa daõy sort Lôù Lôùp thuaä thuaät toaù toaùn ban ñaàu, baét ñaàu töø vò trí thöù 2; laëp laïi quaù trình khaù khaùc treân cho daõy hieän haønh... ñeán khi daõy hieän haønh Ñôn giaû giaûn, n, chæ coøn 1 phaàn töû. Chi phí phí cao 25 26 Selection sort – Thuaät toaùn Selection sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp Find MinPos(1, 8) Swap(ai, amin) • Böôùc 1 : i = Vò trí ñaàu; min • Böôùc 2 : Tìm phaàn töû a[min] nhoû nhaát trong daõy 1 2 3 4 5 6 7 8 hieän haønh töø a[i] ñeán a[N] 12 2 8 5 1 6 4 15 • Böôùc 3 : Neáu min ≠ i: Hoaùn vò a[min] vaø a[i] • Böôùc 4 : Neáu i chöa laø Vò trí cuoái i » i = Vò trí keá(i); » Laëp laïi Böôùc 2 Ngöôïc laïi: Döøng. //N phaàn töû ñaõ naèm ñuùng vò trí. 27 28
  8. Selection sort – Ví duï Selection sort – Ví duï Find MinPos(2, 8) Swap(ai, amin) Find MinPos(3, 8) Swap(ai, amin) min min 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 8 5 12 6 4 15 1 2 8 5 12 6 4 15 i i 29 30 Selection sort – Ví duï Selection sort – Ví duï Find MinPos(4, 8) Swap(ai, amin) Find MinPos(5, 8) Swap(ai, amin) min min 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 5 12 6 8 15 1 2 4 5 12 6 8 15 i i 31 32
  9. Selection sort – Ví duï Selection sort – Ví duï Find MinPos(6, 8) Swap(ai, amin) Find MinPos(7, 8) Swap(ai, amin) min min 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 5 6 12 8 15 1 2 4 5 6 8 12 15 i i 33 34 Selection sort Selection sort – Ñaùnh giaù giaûi thuaät void SelectionSort(int a[],int N ) { • Soá laàn hoaùn vò (moät hoaùn vò baèng 3 pheùp int min; // chæ soá phaàn töû nhoû nhaát trong daõy hieän haønh for (int i=0; i
  10. Selection sort – Ñaùnh giaù giaûi thuaät Insertion Sort – YÙ töôûng • ÔÛû löôït thöù i, caàn (N-i) laàn so saùnh ñeå xaùc • Nhaän xeùt: moïi daõy a1 , a2 ,..., an luoân coù i-1 phaàn töû ñònh phaàn töû nhoû nhaát hieän haønh. ñaàu tieân a1 , a2 ,... ,ai-1 ñaõ coù thöù töï (2 ≤ i). YÙ töôûng chính: tìm caùch cheøn phaàn töû ai vaøo vò trí • Soá löôïng pheùp so saùnh khoâng phuï thuoäc vaøo thích hôïp cuûa ñoaïn ñaõ ñöôïc saép ñeå coù daõy môùi a1 , tình traïng cuûa daõy soá ban ñaàu. a2 ,... ,ai trôû neân coù thöù töï. • Trong moïi tröôøng hôïp, soá laàn so saùnh laø: – Vò trí naøy chính laø pos thoûa apos-1 ≤ ai < apos (1≤ ≤pos≤ ≤i). Chi tieát hôn: n −1 n(n − 1) – Daõy ban ñaàu a1 , a2 ,..., an, xem nhö ñaõ coù ñoaïn goàm moät ∑ (n − i) = i =1 2 phaàn töû a1 ñaõ ñöôïc saép. – Theâm a2 vaøo ñoaïn a1 seõ coù ñoaïn a1 a2 ñöôïc saép – Theâm a3 vaøo ñoaïn a1 a2 ñeå coù ñoaïn a1 a2 a3 ñöôïc saép – Tieáp tuïc cho ñeán khi theâm xong aN vaøo ñoaïn a1 a2 ...aN-1 seõ 37 coù daõy a1 a2.... aN ñöôïc saép. 38 Insertion Sort – Thuaät toaùn Insertion Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp • Böôùc 1: i = 2; // giaû söû coù ñoaïn a[1] ñaõ ñöôïc saép • Böôùc 2: x = a[i]; Tìm vò trí pos thích hôïp trong ñoaïn 1 2 3 4 5 6 7 8 a[1] 12 2 8 5 1 6 4 15 ñeán a[i] ñeå cheøn x vaøo • Böôùc 3: Dôøi choã caùc phaàn töû töø a[pos] ñeán a[i-1] sang phaûi 1 vò trí ñeå daønh choå cho x • Böôùc 4: a[pos] = x; // coù ñoaïn a[1]..a[i] ñaõ ñöôïc saép • Böôùc 5: i = i+1; Neáu i ≤ n : Laëp laïi Böôùc 2. Ngöôïc laïi : Döøng. 39 40
  11. Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a2 into (1, 2) Insert a3 into (1, 3) pos pos 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 12 2 2 8 5 1 6 4 15 2 12 8 8 5 1 6 4 15 i i x x 41 42 Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a4 into (1, 4) Insert a5 into (1, 5) pos pos 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 8 5 12 5 1 6 4 15 2 1 5 8 12 1 6 4 15 i i x x 43 44
  12. Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a6 into (1, 6) Insert a7 into (1, 7) pos pos 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 5 8 6 12 6 4 15 1 2 5 4 6 8 12 4 15 i i x x 45 46 Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a8 into (1, 8) pos pos 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 i x 47 48
  13. Insertion Sort – Caøi ñaët Insertion Sort – Nhaän xeùt void InsertionSort(int a[], int N ) { • Khi tìm vò trí thích hôïp ñeå cheøn a[i] vaøo ñoaïn int pos, i; a[0] ñeán a[i-1], do ñoaïn ñaõ ñöôïc saép  coù theå int x;//löu tröõ a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn töû. söû duïng giaûi thuaät tìm nhò phaân ñeå thöïc hieän for(int i=1 ; i0)&&(a[pos-1]>x);pos--) khoâng laøm giaûm soá laàn dôøi choã. a[pos] = a[pos-1]; • Ngoaøi ra, coù theå caûi tieán giaûi thuaät cheøn tröïc a[pos] = x;// cheøn x vaøo daõy tieáp vôùi phaàn töû caàm canh ñeå giaûm ñieàu kieän } kieåm tra khi xaùc ñònh vò trí pos. } 49 50 Binary Insertion Sort – Caøi ñaët Insertion Sort – Ñaùnh giaù giaûi thuaät void BInsertionSort(int a[], int N ) { int l,r,m,i; • Caùc pheùp so saùnh xaûy ra trong moãi voøng laëp tìm vò trí int x;//löu tröõ giaù trò a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn thích hôïp pos. Moãi laàn xaùc ñònh vò trí pos ñang xeùt töû. khoâng thích hôïp  dôøi choã phaàn töû a[pos-1] ñeán vò trí for(int i=1 ; i
  14. Interchange Sort – YÙ töôûng • Nhaän xeùt: Ñeå saép xeáp moät daõy soá, ta coù theå xeùt caùc nghòch theá coù trong daõy vaø laøm trieät tieâu daàn chuùng ñi.  YÙ töôûng chính: – Xuaát phaùt töø ñaàu daõy, tìm taát caû nghòch theá chöùa phaàn töû naøy, trieät tieâu chuùng baèng caùch ñoåi choã phaàn töû naøy vôùi phaàn töû töông öùng trong caëp nghòch theá. Phương pháp đổi chỗ trực tiếp – Laëp laïi xöû lyù treân vôùi caùc phaàn töû tieáp theo Interchange Sort trong daõy 54 Interchange Sort – Thuaät toaùn Interchange Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp • Böôùc 1 : i = 1; // baét ñaàu töø ñaàu daõy j • Böôùc 2 : j = i+1; //tìm caùc caëp phaàn töû 1 2 3 4 5 6 7 8 a[j] < a[i], j>i 12 1 2 8 5 1 6 4 15 • Böôùc 3 : Trong khi j ≤ N thöïc hieän • Neáu a[j]
  15. Interchange Sort – Ví duï Interchange Sort – Ví duï j j 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 12 8 5 2 6 4 15 1 2 12 4 8 5 6 4 15 i i 57 58 Interchange Sort – Ví duï Interchange Sort – Ví duï j 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 12 5 8 6 5 15 1 2 4 5 6 8 12 15 i 59 60
  16. Interchange Sort - Caøi ñaët Interchange Sort void InterchangeSort(int a[], int N) Ñaùnh giaù giaûi thuaät • Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï { thuoäc vaøo tình traïng cuûa daõy soá ban ñaàu int i, j; • Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc for (i = 0 ; i
  17. Bubble sort – Thuaät toaùn Bubble Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp • Böôùc 1 : i = Vò trí ñaàu; j 1 2 3 4 5 6 7 8 • Böôùc 2 : j = Vò trí cuoái;//Duyeät töø cuoái daõy ngöôïc veà vò trí i 12 1 2 8 5 1 6 4 15 – Trong khi (j > i) thöïc hieän: ↔a[j-1];//xeùt caëp phaàn töû keá caän • Neáu a[j]
  18. Bubble Sort – Ví duï Bubble Sort – Ví duï j j 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 5 12 8 5 6 15 1 2 4 5 6 12 8 6 15 i i 69 70 Bubble Sort – Ví duï Bubble Sort – Ví duï j j 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 4 5 6 12 8 8 15 1 2 4 5 6 8 12 15 i i 71 72
  19. Bubble sort - Caøi ñaët Bubble sort - Ñaùnh giaù giaûi thuaät • Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï void BubbleSort(int a[], int N) thuoäc vaøo tình traïng cuûa daõy soá ban ñaàu { int i, j; • Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc for (i = 0 ; i < N-1 ; i++) vaøo keát quaû so saùnh for (j = N-1; j>i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } 73 74 Bubble sort - Ñaùnh giaù giaûi thuaät Bubble sort – Caûi tieán • Giaûi thuaät ShakerSort: • Khuyeát ñieåm: – Döïa treân nguyeân taéc ñoåi choã tröïc tieáp – Khoâng nhaän dieän ñöôïc tình traïng daõy ñaõ coù thöù töï hay coù thöù töï töøng phaàn. – Tìm caùch khaéc phuïc caùc nhöôïc ñieåm cuûa BubleSort – Caùc phaàn töû nhoû ñöôïc ñöa veà vò trí ñuùng raát • Trong moãi laàn saép xeáp, duyeät maûng theo 2 löôït nhanh, trong khi caùc phaàn töû lôùn laïi ñöôïc töø 2 phía khaùc nhau : ñöa veà vò trí ñuùng raát chaäm. – Löôït ñi: ñaåy phaàn töû nhoû veà ñaàu maûng – Löôït veà: ñaåy phaàn töû lôùn veà cuoái maûng • Ghi nhaän laïi nhöõng ñoaïn ñaõ saép xeáp nhaèm tieát kieäm caùc pheùp so saùnh thöøa. 75 76
  20. Giaûi thuaät ShakerSort Giaûi thuaät ShakerSort //input: daõy (a, N) • Böôùc 2 : //output: daõy (a, N) ñaõ ñöôïc saép xeáp – Böôùc 2b : j = l ; // ñaåy phaàn töû lôùn veà cuoái maûng • Böôùc 1 : • Trong khi (j < r) : – l = 1; r = n; //töø l ñeán r laø ñoaïn caàn ñöôïc saép xeáp – Neáu a[j]>a[j+1]: a[j] ↔ a[j+1]; – k = n; // ghi nhaän laïi vò trí k xaûy ra hoaùn vò sau cuøng » k = j;//löu laïi nôi xaûy ra hoaùn vò // ñeå laøm cô sôû thu heïp ñoaïn l ñeán r – j = j+1; • Böôùc 2 : • r = k; //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû cuoái daõy – Böôùc 2a : j = r ; // ñaåy phaàn töû nhoû veà ñaàu maûng • Trong khi (j > l) : • Böôùc 3 : Neáu l < r: Laëp laïi Böôùc 2. – Neáu a[j]
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