Thực tập Kỹ thuật lập trình: Thực hiện các chức năng sắp xếp

Tài liệu trình bày các kiến thức về một số thuật toán sắp xếp và một số kỹ thuật xử lý xâu để áp dụng cho bài toán sắp xếp trong quản lý sinh viên. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Thực tập Kỹ thuật lập trình: Thực hiện các chức năng sắp xếp ThựctậpKỸTHUẬTLẬPTRÌNH Tuần79:ThựchiệncácchứcnăngsắpxếpYêu cầu: Với dữ liệu sinh viên gồm các thông tin:  Mãlớp  Mãsinhviên  Họvàtên  Ngàysinh  Điểmtrungbìnhtíchlũyđã nhập và lưu trữ trên file.Ví dụ đã nhập được danh sách sinh viên như sau: Mãlớp Mãsinhviên Họvàtên Ngàysinh ĐTBTL 13A 2014000001 NguyễnĐìnhGiang 02/12/1996 3.4 13C 2014000002 TrịnhVănAnh 24/10/1996 2.8 13B 2014000003 HoàngXuânĐạt 15/06/1996 3.2Hãy thực hiện các các yêu cầu sau: - Sắp xếp danh sách sinh viên theo Mã lớp. Ví dụ danh sách trên sau khi xếp theo mã lớp ta được: Mãlớp Mãsinhviên Họvàtên Ngàysinh ĐTBTL 13A 2014000001 NguyễnĐìnhGiang 02/12/1996 3.4 13B 2014000003 HoàngXuânĐạt 15/06/1996 3.2 13C 2014000002 TrịnhVănAnh 24/10/1996 2.8 - Sắp xếp danh sách sinh viên theo Mã sinh viên (như sanh sách đã cho). - Sắp xếp danh sách sinh viên theo Họ và tên. Họ và tên sinh viên được so sánh theo tên rồi đến họ đệm. Ví dụ danh sách sinh viên ở trên đặc xếp lại theo họ tên là Mãlớp Mãsinhviên Họvàtên Ngàysinh ĐTBTL 13C 2014000002 TrịnhVănAnh 24/10/1996 2.8 13B 2014000003 HoàngXuânĐạt 15/06/1996 3.2 13A 2014000001 NguyễnĐìnhGiang 02/12/1996 3.4 - Sắp xếp danh sách sinh viên theo Ngày sinh. Ngày sinh được so sánh theo năm, đến tháng, và cuối là đến ngày. Ví dụ danh sách trên sau khi sắp xếp ta được: Mãlớp Mãsinhviên Họvàtên Ngàysinh ĐTBTL 13B 2014000003 HoàngXuânĐạt 15/06/1996 3.2 13C 2014000002 TrịnhVănAnh 24/10/1996 2.8 13A 2014000001 NguyễnĐìnhGiang 02/12/1996 3.4 - Sắp xếp danh sách sinh viên theo mã lớp, cùng mã lớp sắp xếp theo họ tên, cùng họ tên thì sắp xếp theo ngày sinh.Kiến thức liên quan:A. MỘT SỐ THUẬT TOÁN SẮP XẾP - Bàitoánsắpxếpthườngđượcmôtảnhưsau: - ChodanhsáchXchứanphầntử X[1], X[2],...,X[n].Giả thiếtlàcácphần tử củadanhsáchXcóthểsosánhhơnkémvớinhautheomộttiêuchínàođó. Theotiêuchíđượcchọntrước,cầnsắpxếplạimảng X theothứ tự không giảm(hoặckhôngtăng). - Trongmụcnàychúngtaxéttrườnghợpcácphầntử củamảngXlàsốthựcvà yêucầusắpxếpXsaochothànhdãykhônggiảm.Cókhánhiềuthuậttoánsắp xếpđể giảiquyếtbàitoánđãnêu.Trongphầntiếptheochúngtaxemxétmột số thuậttoánsắpxếpđơngiảnnhư sắpxếpchọn(selectionsort),sắpxếp chèn(insertionsort)vàsắpxếpnổibọt(bublesort).5.2.1.SắpxếpchọnÝtưởng:- Xéttừngvị trí,từ 1đếnn1,tạimỗivị trítìmphầntử thíchhợpvàchuyểnđến. Nhưvậy,phầntửthíchhợpvớivịtríthứ nhấtphảilàphầntử bénhấttrongdanh sách(vớibàitoánsắpxếpthànhdãykhôngtăngthìphầntửđầutiênphảilàphần tử lớnnhấttrongdãy). Ở vị tríthứ haiphảilàphầntử bénhấttrongcácphầntử cònlại(vớibàitoánsắpxếpthànhdãykhôngtăngthìphầntửthứhaiphảilàphần tửlớnnhấttrongcácphầntửcònlạicủadãy).- Cứnhưvậy,giảsửđãchọnđượccácphầntử thíchhợpchocácvịtrítừ thứnhất đếnvịtríthứi1.Rõràngphầntửthíchhợpvớivịtríthứ iphảilàphầntửbénhất (hoặcphầntử lớnnhấtđốivớibàitoánsắpxếpthànhdãykhôngtăng)trongcác phầntử cònlại{X[i],X[i+1],...,X[n]}.Việcchọnphầntửthứ icóthểmôtảnhư sau: Kíhiệu X[k] = min{X[i],X[i+1],...,X[n]}; Nếuk>ithìđổichỗhaiphầntửX[k]vàX[i];Docóthểxétvịtríitừ1nêncóthểmôtảthuậttoánnhưsau: Dữliệuvào: DãyX[1],X[2],....,X[n] Dữliệura: DãyXkhônggiảm:X[1] X[2] .... X[n]; 2 for (i=1;ii)swap(X[k],X[i]); }KỹthuậtđổichỗX[k]vàX[i]: { tg=X[k]; X[k]=X[i]; X[i]=tg; }Vídụ5.:Sắpxếpdãysốsauthànhkhônggiảm: 1 13,22,30,14,21,5,21,12,15,19Ápdụngthuậttoánsắpxếpchọnđốivới3vịtríđầ ucủadãy: 1)i=1: 13 22 30 14 21 5 21 12 15 19 ...