Bài giảng Sorting

Đặt vấn đề Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất địnhMục đích của sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu được dễ dàng nhanh chóng Ví dụ: Cho trước một dãy n số nguyên được sắp thứ tự tăng dầnViệc tìm kiếm một phần tử x nào đó được thực hiện bằng cách chia đôi dãy ban đầuChỉ cần k bước ta xác định được phần tử cần tìmTrường hợp xấu nhất Vậy với n = 1000  210 i.e chỉ cần 10 bước là ta xác định được phần tử cần tìm trong dãy 1000 phần tửn = 1.000.000  220n = 1 tỷ  230Rõ ràng sắp xếp là một việc làm hết sức cơ bản và được áp dụng rộng rãi trong các kỹ thuật lập trình nhằm xử lý thông tin. Đặt vấn đềSortingNội dungĐịnh nghĩaGiả thiếtSắp xếp tại chỗChiến lược sắp xếpTổng quan về thời gian thực hiệnSortingĐịnh nghĩaSắp xếp là một tiến trình:Tìm một bộ hoán vị trên tập hợp các đối tượng cho trước a1, a2, ..., an (ví dụ là các số nguyên), vàTrả về một thứ tự khác (a'1, a'2, ..., a'n) sao choa'1 ≤ a'2 ≤ · · · ≤ a'n Ít khi ta sắp xếp các giá trị đơn lẻ. Thông thường chúng ta sắp xếp một số các mẫu tin chứa một số các trường trên cơ sở trường khóa19991532StevensonMonica3 Glendridge Ave.19990253RedpathRuth53 Belton Blvd.19985832KiljiIslam37 Masterson Ave.20003541GroskurthKen12 Marsdale Ave.19989932CarolAnn81 Oakridge Ave.20003287RedpathDavid5 Glendale Ave.19989932CarolAnn81 Oakridge Ave.19985832KiljiIslam37 Masterson Ave.19990253RedpathRuth53 Belton Blvd.19991532StevensonMonica3 Glendridge Ave.20003287RedpathDavid5 Glendale Ave.20003541GroskurthKen12 Marsdale Ave.19989932CarolAnn81 Oakridge Ave.20003541GroskurthKen12 Marsdale Ave.19985832KiljiIslam37 Masterson Ave.20003287RedpathDavid5 Glendale Ave.19990253RedpathRuth53 Belton Blvd.19991532StevensonMonica3 Glendridge Ave.Theo ID numberTheo thứ tự họ tênSortingĐịnh nghĩaTrong phần này, ta giả sử rằng:Mảng đựợc sử dụng cho cả input và outputTập trung sắp xếp trường khóa và để lại mọi trường hợp tổng quát ở phần cài đặt,vàCác đối tượng sắp xếp là duy nhất,i.e., các đối tượng đã sắp xếp lại sẽ thỏa điều sau: a'1 < a'2 < · · · < a'n SortingĐịnh nghĩaSortingSắp tại chỗ (in-place)Giải thuật được sắp tại chỗ nghĩa là việc xin cấp phát vùng nhớ chỉ dành cho một số biến cục bộ mà thôi.Một số giải thuật khác cần cấp phát mảng phụ thứ hai có cùng kích thước với mảng ban đầu (cần O(n) bộ nhớ bổ sung)SortingPhân loạiNhiều giải thuật sắp xếp chỉ được phân loại qua các thao tác thực hiện:ChènHoán đổiPhân phốiChọnTrộnSortingRun-timeThời gian thực hiện giải thuật rơi vào 3 nhóm chính:O(n) O(n ln(n)) O(n2)Ta khảo sát trường hợp xấu nhất, trung bình và tốt nhất cho mỗi giải thuậtThời gian thực hiện thay đổi dựa vào sự phân bố ban đầu của dãy.SortingRun-timeTa sẽ khảo sát một số giải thuật cổ điển có độ phức tạp O(n2) :insertion sort, bubble sortMột số giải thuật chạy nhanh hơn O(n ln(n)) :heap sort, quick sort, và merge sortSortingCận dướiBất kỳ một giải thuật sắp xếp nào cũng phải khảo sát từng phần tử ít nhất 1 lầnKết luận, mọi giải thuật phải có cận dưới là W(n)SortingĐịnh nghĩa về nghịch thếXét 3 dãy sau: 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 923 dãy này chưa được sắp xếp ở mức độ nào ?Sorting Định nghĩa về nghịch thế 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 12 16 25 26 33 35 42 45 56 58 67 74 75 81 83 86 88 95 99 Dãy đầu tiên chỉ cần một ít sự hóan đổi là đủ để sắp xếp lại dãy này.Sorting Định nghĩa về nghịch thếDãy thứ hai có hai phần tử nằm rất xa vị trí đúng 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 1 17 21 23 24 27 32 35 42 45 47 57 66 69 70 76 85 87 95 99 Tuy nhiên có 13 phần tử đã đúng vị trí 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 1 10 12 16 20 22 26 31 38 44 48 79 80 81 84 87 92 95 96 99 Sorting Định nghĩa về nghịch thếDãy thứ ba, hầu hết các vị trí đều không đúng vị trí của nó Sorting Định nghĩa về nghịch thếCho trước một dãy bất kỳ có n phần tử, ta có  cặp sốVí dụ, dãy 1, 3, 5, 4, 2, 6 chứa 15 cặp số sau (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)Sorting Định nghĩa về nghịch thếLưu ý rằng 11 cặp trong số các cặp này đã có thứ tự: (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)Sorting Định nghĩa về nghịch thếTrong khi 4 cặp còn lại có thứ tự ngược (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)Sorting Định nghĩa về nghịch thếXét tập các phần tử SMột hoán vị của S là sự tái sắp xếp các phần tử trong SVí dụ: S = {0, 1, 2, 3}, có 4! = 24 phép hoán vị như sau: 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 0 3 1 2 0 3 2 1 2 0 1 3 2 0 3 1 2 1 0 3 2 1 3 0 2 3 0 1 2 3 1 0 3 0 1 2 3 0 2 1 3 1 0 2 3 1 2 0 3 2 0 1 3 2 1 0Sorting Định nghĩa về nghịch thếDo đó , phép hoán vị sau 1, 3, 5, 4, 2, 6 chứa 4 nghịch thế: (3, 2) (5, 4) (5, 2) (4, 2)Sorting Định nghĩa về nghịch thếHoán đổi 2 phần tử kề nhau hoặc là:Xóa một nghịch thế 1 3 5 4 2 6 1 3 5 2 4 6 xóa nghịch thế (4, 2)Tạo ra một nghịch thế mới, ví dụ cặp (5, 3) 1 3 5 4 2 6 1 5 3 4 2 6SortingSố các nghịch thếCó cặp số trong một tập bất kỳ có n phần tử.Mỗi cặp hoặc là ở trongTập có thứ tự đúng, hoặc làTập có thứ tự ngượcĐối với dãy ngẫu nhiên, ta giả sử có phân nửa các cặp có thứ tự ngược hoặc  nghịch thếSortingSố các nghịch thếVí dụ, dãy chưa được sắp sau có 56 phần tử 261 548 3 923 195 973 289 237 57 299 594 928 515 55 507 351 262 797 788 442 97 798 227 127 474 825 7 182 929 852 504 485 45 98 538 476 175 374 523 800 19 901 349 947 613 265 844 811 636 859 81 270 697 563 976 539 có 655 cặp có thứ tự ngược và 885 cặp có thứ tự đúng.Công thức dự báo là 770 nghịch thếSortingSố các nghịch thếHãy xem số các nghịch thế trong 3 dãy ban đầu có 20 phần tử : 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92Do đó:có 19·20/2 = 190 cặpTrung bình, 190/2 = 95 nghịch thếSorting Số nghịch thếDãy đầu tiên 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 có 13 nghịch thế: (16, 12) (26, 25) (35, 33) (58, 45) (58, 42) (58, 56) (45, 42) (83, 75) (83, 74) (83, 81) (75, 74) (86, 81) (99, 95)Số này rất thấp so với số mong đợi của ta là (95)Do đó,đây không phải là dãy ngẫu nhiên Sorting Số nghịch thếDãy thứ hai 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 cũng có 13 cặp ngược: (42, 24) (42, 27) (42, 32) (42, 35) (42, 23) (24, 23) (27, 23) (32, 23) (35, 23) (45, 23) (47, 23) (57, 23) (87, 85)Vì thế cũng không phải là dãy ngẫu nhiênSorting Số nghịch thếDãy thứ 3 : 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 có 100 cặp ngược: (22, 20) (22, 12) (22, 10) (22, 1) (22, 16) (20, 12) (20, 10) (20, 1) (20, 16) (81, 38) (81, 12) (81, 79) (81, 44) (81, 26) (81, 10) (81, 48) (81, 80) (81, 1) (81, 16) (81, 31) (38, 12) (38, 26) (38, 10) (38, 1) (38, 16) (38, 31) (95, 84) (95, 12) (95, 79) (95, 44) (95, 26) (95, 87) (95, 10) (95, 48) (95, 80) (95, 1) (95, 16) (95, 31) (95, 92) (84, 12) (84, 79) (84, 44) (84, 26) (84, 10) (84, 48) (84, 80) (84, 1) (84, 16) (84, 31) (99, 12) (99, 79) (99, 44) (99, 26) (99, 87) (99, 96) (99, 10) (99, 48) (99, 80) (99, 1) (99, 16) (99, 31) (99, 92) (12, 10) (12, 1) (79, 44) (79, 26) (79, 10) (79, 48) (79, 1) (79, 16) (79, 31) (44, 26) (44, 10) (44, 1) (44, 16) (44, 31) (26, 10) (26, 1) (26, 16) (87, 10) (87, 48) (87, 80) (87, 1) (87, 16) (87, 31) (96, 10) (96, 48) (96, 80) (96, 1) (96, 16) (96, 31) (96, 92) (10, 1) (48, 1) (48, 16) (48, 31) (80, 1) (80, 16) (80, 31) (31, 16)SortingTổng kếtGiới thiệu về sắp xếp:Các giả thiếtSắp xếp tại chỗ cần O(1) bộ nhớ bổ sungCác kỹ thuật sắp xếpinsertion, exchanging, selection, merging, distributionPhân loại thời gian thực hiện: O(n) O(n ln(n)) O(n2)Khảo sát phép chứng minh tổng quát của một giải thuật sắp xếp có cận dưới là W(n ln(n))