Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dần theo một hoặc một vài thuộc tính của nó (các thuộc tính này gọ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ụ ( | Hôm nay Các phương pháp sắp xếp Giao bài tập lớn Sorting Bài 11. Sắp xếp (Sorting) Sorting Sorting Input: Dãy các phần tử (và một thứ tự) (Dãy các phần tử thường được lưu bằng mảng.) Output: Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dần theo một hoặc một vài thuộc tính của nó (các thuộc tính này gọ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ụ ( Sorting Các thuật toán với thời gian chạy O(n2) Nổi bọt – Bubble sort Chèn – Insertion sort Chọn – Selection sort Sorting Sắp xếp nổi bọt – Bubble sort Ý tưởng: Thực hiện chuyển dần các phân tử có giá trị khóa nhỏ về đầu dẫy, các phần tử có khóa lớn về cuối dãy. 5 4 2 3 1 5 4 2 3 1 1 5 4 2 3 1 2 5 4 3 1 2 5 4 3 1 2 3 5 4 1 2 3 5 4 1 2 3 4 5 Bước 1 Bước 2 1 5 4 2 3 Bước 3 Bước 4 Ví dụ sắp xếp dãy sau theo thứ tự tăng dần: Sorting Thuật toán Algorithm BubbleSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của . | Hôm nay Các phương pháp sắp xếp Giao bài tập lớn Sorting Bài 11. Sắp xếp (Sorting) Sorting Sorting Input: Dãy các phần tử (và một thứ tự) (Dãy các phần tử thường được lưu bằng mảng.) Output: Dãy các phần tử được sắp theo thứ tự tăng hoặc giảm dần theo một hoặc một vài thuộc tính của nó (các thuộc tính này gọ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ụ ( Sorting Các thuật toán với thời gian chạy O(n2) Nổi bọt – Bubble sort Chèn – Insertion sort Chọn – Selection sort Sorting Sắp xếp nổi bọt – Bubble sort Ý tưởng: Thực hiện chuyển dần các phân tử có giá trị khóa nhỏ về đầu dẫy, các phần tử có khóa lớn về cuối dãy. 5 4 2 3 1 5 4 2 3 1 1 5 4 2 3 1 2 5 4 3 1 2 5 4 3 1 2 3 5 4 1 2 3 5 4 1 2 3 4 5 Bước 1 Bước 2 1 5 4 2 3 Bước 3 Bước 4 Ví dụ sắp xếp dãy sau theo thứ tự tăng dần: Sorting Thuật toán Algorithm BubbleSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i 1 to n-1 do for j n downto i+1 do if A[j].Key Sorting Chứng minh thời gian chạy của thuật toán trong trường hợp xấu nhất là O(n2) ? Sorting Thời gian chạy Algorithm BubbleSort(Array A, n) Input: Mảng A có n phần tử Output: Mảng A được sắp theo thứ tự tăng dần của khóa for i 1 to n-1 do n+2 for j n downto i+1 do n-i if A[j].Key Sorting Ví dụ: Mô tả quá trình sắp xếp của dãy số 12 43 11 34 23 43 Sorting Sắp xếp chọn - Selection sort Ý tưởng: Chọn phần tử có khóa nhỏ nhất trong các phần tử còn lại chuyển nó về đầu và loại bỏ nó khỏi dãy. 5 4 2 3 1 Bước 1 Bước 2 Bước 3 Bước 4 5 4 2 3 1 1 4 2 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 Ví dụ sắp xếp .
