Bài giảng Phân tích thiết kế thuật toán: Chương 2 - Nguyễn Văn Linh

Bài giảng "Phân tích thiết kế thuật toán - Chương 2: Sắp xếp" cung cấp các kiến thức giúp người đọc có thể hiểu các giải thuật sắp xếp, vận dụng được giải thuật để minh họa việc sắp xếp, hiểu các lưu đồ của các giải thuật sắp xếp,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế thuật toán: Chương 2 - Nguyễn Văn Linh CHƯƠNG2:SẮPXẾP NguyễnVănLinh KhoaCôngnghệThôngtin&Truyềnthông ĐẠIHỌCCẦNTHƠ nvlinh@ctu.edu.vnNguyễn Văn Linh Mụctiêu Saukhihoàntấtbàihọcnàybạncầnphải: • Hiểucácgiảithuậtsắpxếp. • Vậndụngđượcgiảithuậtđểminhhọaviệc sắpxếp. • Hiểucáclưuđồcủacácgiảithuậtsắpxếp. • Hiểucácchươngtrìnhsắpxếp. • Hiểuđượcviệcđánhgiácácgiảithuật.Nguyễn Văn Linh Tầmquantrọngcủabàitoánsắp xếp • Sắpxếpmộtdanhsáchcácđốitượngtheo mộtthứtựnàođólàmộtbàitoánthường đượcvậndụngtrongcácứngdụngtinhọc. • Sắpxếplàmộtyêucầukhôngthểthiếu trongkhithiếtkếcácphầnmềm. • Dođóviệcnghiêncứucácphươngphápsắp xếplàrấtcầnthiếtđểvậndụngtrongkhi lậptrình.Nguyễn Văn Linh Sắpxếptrongvàsắpxếpngoài• Sắpxếptronglàsựsắpxếpdữliệuđượctổchứctrongbộ nhớtrongcủamáytính.• Cácđốitượngcầnđượcsắpxếplàcácmẩutingồmmộthoặc nhiềutrường.Mộttrongcáctrườngđượcgọilàkhóa(key),kiểu củanólàmộtkiểucóquanhệthứtự(nhưcáckiểusốnguyên,số thực,chuỗikýtự...).• Danhsáchcácđốitượngcầnsắpxếpsẽlàmộtmảngcủacác mẩutinvừanóiởtrên.• Mụcđíchcủaviệcsắpxếplàtổchứclạicácmẩutinsaochocác khóacủachúngđượcsắpthứtựtươngứngvớiquyluậtsắpxếp.• Mộtcáchmặcnhiên,quyluậtsắpxếplàthứtựkhônggiảm.Khi cầnsắpxếptheothứtựkhôngtăngthìphảinóirõ.• Sắpxếpngoàilàsựsắpxếpđượcsửdụngkhisốlượngđối tượngcầnsắpxếplớnkhôngthểlưutrữtrongbộnhớtrongmà phảilưutrữtrênbộnhớngoài. Nguyễn Văn Linh Tổchứcdữliệuvàngônngữcài đặt • Ðểtrìnhbàycácvídụminhhọachúngtasẽ dùngC(TurboC++,Version3.0)làmngôn ngữthểhiệnvàsửdụngkhaibáosau. typedefintkeytype; typedeffloatothertype; typedefstructrecordtype{ keytypekey; othertypeotherfields; };Nguyễn Văn Linh Tổchứcdữliệuvàngônngữcàiđặt(tt) voidSwap(recordtype&x,recordtype&y) { recordtypetemp; temp=x; x=y; y=temp; } • CầnthấyrằngthủtụcSwaplấyO(1)thờigianvì chỉthựchiện3lệnhgánnốitiếpnhau.Nguyễn Văn Linh Giảithuậtsắpxếpchọn(Selection Sort) • Bước0,chọnphầntửcókhóanhỏnhấttrongn phầntửtừa[0]đếna[n1]vàhoánvịnóvớiphần tửa[0]. • Bước1,chọnphầntửcókhóanhỏnhấttrongn1 phầntửtừa[1]đếna[n1]vàhoánvịnóvớia[1]. • Tổngquátởbướcthứi,chọnphầntửcókhoánhỏ nhấttrongniphầntửtừa[i]đếna[n1]vàhoánvị nóvớia[i]. • Saun1bướcnàythìmảngđãđượcsắpxếp.Nguyễn Văn Linh Phươngphápchọnphầntử• Đầutiêntađặtkhoánhỏnhấtlàkhoácủaa[i](lowkey =a[i].key)vàchỉsốcủaphầntửcókhoánhỏnhấtlài (lowindex=i).• Xétcácphầntửa[j](vớijtừi+1đếnn1),nếukhoá củaa[j]nhỏhơnkhoánhỏnhất(a[j].keyn1)thìphầntửcókhoánhỏ nhấtlàa[lowindex].Nguyễn Văn Linh VídụsắpxếpchọnKhóa a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]BướcBanđầu 5 6 2 2 10 12 9 10 9 3Bước0Bước1Bước2Bước3Bước4Bước5Bước6Bước7Bước8Kếtquả 2 2 3 5 6 9 9 10 10 12 Nguyễn Văn Linh Begin i=0 S i Chương trình sắp xếp chọn a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]Ban đầu 5 6 2 2 10 12 9 10 9 3Bước 0Bước 1 void SelectionSort(recordtype a[], int n){ int i,j, lowindex; keytype lowkey; /*1*/ for(i=0; i Đánhgiásắpxếpchọn • HàmSwaptốnO(1). • Toànbộchươngtrìnhchỉbaogồmlệnh/*1*/.Lệnh/*1*/ chứacáclệnh“đồngcấp”/*2*/,/*3*/,/*4*/và/*8*/,trong đócáclệnh/*2*/,/*3*/và/*8*/đềutốnthờigianO(1). • Lệnh/*6*/và/*7*/đềutốnO(1)nênlệnh/*5*/tốnO(1). • Vònglặp/*4*/thựchiệnni1lần,vìjchạytừi+1đếnn 1,mỗilầnlấyO(1),nênlấyO(ni1)thờigian. • GọiT(n)là ...