Các giải thuật. Sắp xếp nội

CÁC GIảI THUậTSắP XếP NộI * ĐịNH NGHĨA BÀI TOÁN SắP XếP Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử * KHÁI NIệM NGHịCH THế Khái niệm nghịch thế: Xét một mảng các số a0, a1, … an Nếu có i aj, thì ta gọi đó là một nghịch thế. Mảng chưa sắp xếp sẽ có nghịch thế. Mảng đã có thứ tự sẽ không chứa nghịch thế. a0 ≤ a1 ≤ … ≤ an * CÁC PHƯƠNG PHÁP SắP XếP THÔNG DụNG Selection sort Insertion sort Interchange sort Bubble sort Shaker sort Binary Insertion sort * Shell sort Heap sort Quick sort Merge sort Radix sort … Phức tạp hơn Hiệu quả cao Đơn giản, Chi phí cao Lớp thuật toán khác PHƯƠNG PHÁPCHọN TRựC TIếP Selection sort * Vị trí 5-8 phần tử nhỏ nhất là : * 1 0 3 2 5 4 7 6 8 5 3 6 1 7 12 10 4 2 Min =a For (j=a+1;j0)&&(a[pos-1]>x); pos--) a[pos] = a[pos-1]; a[pos] = x;// chèn x vào dãy } } * PHƯƠNG PHÁP CHÈN TRựC TIếP INSERTION SORT void InsertionSort(){ int pos, i; int x;//lưu trữ giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. K=0; While(a[k]0)&&(a[pos-1]>x); pos--) a[pos] = a[pos-1]; a[pos] = x;// chèn x vào dãy } } * PHƯƠNG PHÁP CHÈN TRựC TIếP INSERTION SORT Nhận xét: Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn đã được sắp, nên có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos, khi đó có giải thuật sắp xếp chèn nhị phân Binary Insertion Sort * PHƯƠNG PHÁP CHÈN TRựC TIếP INSERTION SORT void BInsertionSort( ) { int left,right,mid,i; int x;//lưu trữ giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=1 ; ileft ; j--) a[j] = a[j-1]; // dời chỗ các phần tử sẽ đứng sau x a[left] = x; // chèn x vào dãy } } * PHƯƠNG PHÁP CHÈN TRựC TIếP INSERTION SORT Đánh giá giải thuật: Các phép so sánh xảy ra trong mỗi vòng lặp tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau * PHƯƠNG PHÁP CHÈN TRựC TIếP INSERTION SORT Đánh giá giải thuật: * PHƯƠNG PHÁPĐổI CHỗ TRựC TIếP Interchange Sort * PHƯƠNG PHÁP ĐổI CHỗ TRựC TIếPINTERCHANGE SORT Để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và làm triệt tiêu dần chúng đi. Ý tưởng chính: Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy * PHƯƠNG PHÁP ĐổI CHỗ TRựC TIếPINTERCHANGE SORT Bước 1 : i = 1;// bắt đầu từ đầu dãy Bước 2 : j = i+1;//tìm các phần tử a[j] i Bước 3 : Trong khi j ≤ N thực hiện Nếu a[j]1 giam dan { int i, j; for (i = 0 ; i i) thực hiện: Nếu a[j]N-1: Hết dãy. Dừng Ngược lại : Lặp lại Bước 2. * PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 5 3 6 1 7 12 10 4 2 1 0 3 2 5 4 7 6 8 Ví dụ: sắp xếp dãy số sau 3,5,1,6,12,7,4,10,2 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 2 1 0 3 2 5 4 7 6 8 i=0 j=8 5 3 6 1 7 12 10 4 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 10 1 0 3 2 5 4 7 6 8 i=0 j=7 5 3 6 1 7 12 2 4 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 4 2 10 1 0 3 2 5 4 7 6 8 i=0 5 3 6 1 7 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 7 2 4 10 1 0 3 2 5 4 7 6 8 i=0 5 3 6 1 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 2 7 2 4 10 1 0 3 2 5 4 7 6 8 i=0 5 3 6 1 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 2 6 7 2 4 10 1 0 3 2 5 4 7 6 8 i=0 5 3 1 12 j=3 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 2 1 6 7 2 4 10 1 0 3 2 5 4 7 6 8 i=0 5 3 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 1 5 2 6 7 2 4 10 1 0 3 2 5 4 7 6 8 i=0 3 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 10 3 1 5 2 6 7 2 4 1 0 3 2 5 4 7 6 8 i=1 12 J=8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 10 4 3 1 5 2 6 7 2 1 0 3 2 5 4 7 6 8 i=1 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 7 10 4 3 1 5 2 6 2 1 0 3 2 5 4 7 6 8 i=1 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 4 7 10 3 1 5 2 6 1 0 3 2 5 4 7 6 8 i=1 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 6 12 4 7 10 3 1 5 2 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 4 6 12 2 7 10 3 1 5 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 5 4 6 12 2 7 10 3 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 3 10 5 4 6 12 7 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 10 3 7 5 4 6 12 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 3 7 5 4 6 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 7 12 10 3 6 5 4 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 6 7 12 10 3 4 5 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 5 6 7 12 10 3 4 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 10 5 6 7 12 3 4 2 1 1 0 3 2 5 4 7 6 8 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 4 4 10 12 10 5 6 7 3 2 1 1 0 3 2 5 4 7 6 8 7 6 5 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 5 6 7 3 4 2 1 1 0 3 2 5 4 7 6 8 10 10 5 6 7 7 6 5 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 5 6 7 3 4 2 1 1 0 3 2 5 4 7 6 8 10 10 5 6 7 7 6 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 5 6 7 3 4 2 1 1 0 3 2 5 4 7 6 8 10 10 5 6 7 7 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 5 6 7 3 4 2 1 1 0 3 2 5 4 7 6 8 10 10 5 6 7 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT * 12 10 5 6 7 3 4 2 1 1 0 3 2 5 4 7 6 8 10 5 6 7 12 12 PHƯƠNG PHÁP NổI BọTBUBBLE SORT void BubbleSort() { int i, j; for (i = 0 ; ii ; j --) if(a[j] i; j--) { if (tam l) : Nếu a[j]a[j+1]: a[j] ↔ a[j+1]; k = j;//lưu lại nơi xảy ra hoán vị j = j+1; r = k; //loại bớt các phần tử đã có thứ tự ở cuối dãy Bước 3 : Nếu l < r: Lặp lại Bước 2. * BÀI TậP Cài đặt các thuật toán sắp xếp trên mảng số nguyên In từng bước thực hiện (kết qua sau từng vòng lặp) khi chạy thuật toán Viết bài toán quản lý sinh viên (maso, ten, email, ngaysinh,diem ) và sắp xếp in danh sách sinh vien theo Điểm tăng dần Danh sách sinh viên theo ngày sinh Tương ứng với từng loại sắp xếp Sắp xếp phân số theo thứ tự tăng dần bằng bubble sort, insertion sort *