Kiến trúc máy tính - Phần 11

Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dầntheo một hoặc một vài thuộc tính của nó (các thuộc tính nàygọi là thuộc tính khóa). Thuộc tính khóa được sắp xếp theo một hàm logic, ví dụ(
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - Phần 11Hômnay1. Cácphươngphápsắpxếp2. Giaobàitậplớn Sorting 1 Bài11.Sắpxếp(Sorting) Sorting 2 SortingBàitoán Input: Dãycácphầntử(vàmộtthứtự)  (Dãycácphầntửthườngđượclưubằngmảng.)  Output: Dãycácphầntửđượcsắptheothứtựtănghoặcgiảmdần  theomộthoặcmộtvàithuộctínhcủanó(cácthuộctínhnày gọilàthuộctínhkhóa). Thuộctínhkhóađượcsắpxếptheomộthàmlogic,vídụ  (CácthuậttoánvớithờigianchạyO(n2)  Nổibọt – Bubble sort  Chèn – Insertion sort  Chọn – Selection sort Sorting 4Sắpxếpnổibọt–BubblesortÝtưởng:Thựchiệnchuyểndầncácphântửcógiátrị khóanhỏvềđầudẫy,cácphầntửcókhóalớnvề cuốidãy.Vídụsắpxếpdãysautheothứtựtăngdần: 5 4 2 3 1 1 2 5 4 3 1 2 3 5 4Bước1 Bước3 5 4 2 3 1 1 5 4 2 3 1 2 3 5 4 1 5 4 2 3 1 2 3 4 5 Bước4Bước2 1 2 5 4 3 Sorting 5ThuậttoánAlgorithmBubbleSort(ArrayA,n)Input:MảngAcónphầntửOutput:MảngAđượcsắptheothứtựtăngdầncủakhóa fori←1ton1do forj←ndowntoi+1do ifA[j].KeyChứngminhthờigianchạycủathuậttoán trongtrườnghợpxấunhấtlàO(n2) ? Sorting 7ThờigianchạyAlgorithmBubbleSort(ArrayA,n)Input:MảngAcónphầntửOutput:MảngAđượcsắptheothứtựtăngdầncủakhóa fori←1ton1do n+2 forj←ndowntoi+1doni ifA[j].KeyVídụ:Môtảquátrìnhsắpxếpcủadãysố124311342343 Sorting 9SắpxếpchọnSelectionsort 5 4 2 3 1 • Ýtưởng:Chọn phầntửcókhóa 1 4 2 3 5 Bước1 nhỏnhấttrong cácphầntửcòn 1 2 4 3 5 Bước2 lạichuyểnnóvề đầuvàloạibỏ Bước3 1 2 3 4 5 nókhỏidãy. 1 2 3 4 5• Ví dụ sắp xếp Bước4dãy sau theo thứ 1 2 3 4 5tựtăngdần: 5 4 2 3 1 Sorting 10ThuậttoánAlgorithmSelectionSort(ArrayA,n)Input:MảngAcónphầntửOutput:MảngAđượcsắptheothứtựtăngdầncủakhóafori←1ton1do posmin←i; forj←i+1tondo ifA[posmin].Key>A[j].Keythen posmin←j; ifposmin≠ithen swap(A[i],A[posmin]); Sorting 11Chứngminhthờigianchạycủathuậttoán trongtrườnghợpxấunhấtlàO(n2) ? Sorting 12Thờigianchạyfori←1ton1do n+2 posmin←i; 1 forj←i+1tondo ni2 ifA[posmin].KeyVídụ:Môtảquátrìnhsắpxếpcủadãysố1243113423435 Sorting 14Sắpxếpchèn–Insertionsort 5 4 2 3 1 Ý tưởng: Lấy phần tử thứ A[j] chèn vào dãy 4 5 2 3 1 gồm các phần tử từ A[1]..A[j-1] sao cho ta được dãy A[1]..A[j] 2 4 5 3 1 được sắp. Trong đó dãy A[1]..A[j-1] là dãy đã 2 3 4 5 1 được sắp. 1 2 3 4 5Ví dụ sắp xếp dãysau theo thứ tự 1 2 3 4 5tăngdần: 5 4 2 3 1 Sorting 15Thuậttoán AlgorithmInsertionSort(ArrayA,n) Input:MảngAcónphầntử Output:MảngAđượcsắptheothứtựtăng dầncủakhóa fori←2tondo j←i1; x←A[i]; while(A[j].Key>x.Key)and(j>0)do A[j+1]←A[j]; j←j1; A[j+1]←x; Sorting 16Chứngminhthờigianchạycủathuậttoán trongtrườnghợpxấunhấtlàO(n2) ? Sorting 17Vídụ:Môtảquátrìnhsắpxếpcủadãysố12431134234312435 Sorting 18 ...