Đề tài Công nghệ thông tin: Các thuật toán sắp xếp cơ bản

CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN<br /> <br /> Thành viên nhóm:<br /> 1. Nguyễn Chánh Đại<br /> 2. Mai Phước Vinh<br /> 3. Tất Huỳnh Anh Khôi<br /> <br /> CẦN THƠ, 2015<br /> <br /> MỤC LỤC<br /> 1. SẮP XẾP CHỌN (SELECTION SORT) ....................................................................................................... 1<br /> 2. SẮP XẾP CHÈN (INSERTION SORT)........................................................................................................ 1<br /> 3. SẮP XẾP NỔI BỌT (BUBBLE SORT) ........................................................................................................ 2<br /> 4. SẮP XẾP NHANH (QUICK SORT) .............................................................................................................. 3<br /> <br /> CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN<br /> <br /> 1. Sắp xếp chọn (Selection Sort)<br /> a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa<br /> phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành,<br /> sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu<br /> dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.<br /> b. Giải thuật:<br />  Bước 1: i = 1<br />  Bước 2: Tìm phần tử a[Min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]<br />  Bước 3: Hoán vị a[Min] và a[i]<br />  Bước 4: Nếu i ≤ n-1 thì i = i + 1 và lặp lại bước 2, ngược lại thì<br /> c. Độ phức tạp: O(n2)<br /> d. Code tham khảo:<br /> void selectionSort(int a[], int n) {<br /> for (int i = 0; i key){<br /> a[x+1] = a[x];<br /> --x;<br /> }<br /> a[x+1] = key;<br /> }<br /> }<br /> <br /> 3. Sắp xếp nổi bọt (Bubble Sort)<br /> a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa<br /> phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành,<br /> sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu<br /> dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.<br /> NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI<br /> <br /> TRANG 2<br /> <br /> CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN<br /> <br /> b. Giải thuật:<br />  Bước 1: i = 0<br />  Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần<br /> từ từ a[n] đến a[i]<br />  Bước 3: i = i + 1<br />  Bước 4: Nếu i < n thì quay lại Bước 2, ngược lại dừng.<br /> c. Độ phức tạp: O(n2)<br /> d. Code tham khảo<br /> void BubbleSort(int a[], int n){<br /> for (int i = 0; i < n-1; ++i){<br /> for (int j = i+1; j < n; ++j) {<br /> if (a[i] > a[j]) {<br /> int tmp = a[i];<br /> a[i] = a[j];<br /> a[j] = tmp;<br /> }<br /> }<br /> }<br /> }<br /> <br /> 4. Sắp xếp nhanh (Quick Sort)<br /> a. Ý tưởng: Tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt<br /> (pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái<br /> dãy, tất cả các phần tử lớn hơn hoặc bằng phần tử chốt thì đưa về bên phải dãy. Sau<br /> bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu phân chia làm hai dãy<br /> con nằm hai bên chốt. Tiếp tục phân chia các dãy con theo cách tương tự đến khi<br /> mọi dãy con đều có độ dài bằng 1. Có thể lựa chọn phần tử chốt nằm đầu, cuối hay<br /> giữa dãy. Ở đây ta sẽ lựa chọn phần tử chốt nằm gần giữa dãy nhất.<br /> b. Giải thuật:<br /> NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI<br /> <br /> TRANG 3<br /> <br />