Giải thuật đổi chỗ trực tiếp (Interchange Sort)

Chào mừng các bạn đã đến với nhóm 3 Ở video này mình sẽ giới thiệu với các bạn Các bác sếp một hình án Bằng phương pháp Đổi chỗ trực tiếp Hay cũng gọi là IntegerSort Cùng các thành viên trong nhóm Nhánh tưởng là bạn Trung Gia Huy Mình là thành viên là Hàng Trần Nguyễn Bạn Vũ Ngọc Trân và Lê Thị Mai Linh Bạn Bạn Nhật Ánh Chúng ta sẽ tới với ý tưởng của thuộc toán IntegerSort sau Chúng ta sẽ trong một mãn Chỉ tiêu chốn bằng cách đổi chỗ Phần tử này với phần tử tương ứng Trong cặp nhịp thế Lặp lại xử lý trên các phần tử tiếp theo Trong dãy Ở ý tưởng của thuộc toán Chúng ta cần phải hiểu từ Nhịp thế Nhịp thế nào Nhịp thế ở đây Có thể hiểu như là Chúng ta sẽ xét 2 phần tử Y và Z Nếu Y nằm trước Z nằm sau Chúng ta có thể hiểu Y bé hơn Z Hay A thứ Y Nhịp thế nào Với A thứ Z A thứ Y sẽ lỡ vô A thứ Z Chúng ta cứ dịch vụ Y này xét trước Y này là chữ số trước là 1 Còn Z này là 2 Vậy nếu A thứ Y này lớn hơn A thứ Z Thì chúng ta sẽ tiến hành Swap lại với nhau Ví dụ như A thứ Y là 5 A thứ Z là 2 5 lớn hơn 2 Thì chúng ta sẽ tiến hành Swap lại với nhau Và chúng ta cứ tiếp tục tăng Z lên Đường vị cho Y Đó chúng ta sẽ tìm được Các cặp nhịp thế như thế này Và chúng ta chỉ tiêu chốn Bằng cách đổi chỗ Phần thử này với phần thử Tương ứng chung cập nhịp thế Chúng ta cứ lặp lại để xử lý Các phần thử tiếp theo trong giấy Nguyên tắc hoạt động Sắp xếp này là như thế nào Vậy nếu giả sử Chúng ta cần sắp xếp từ từ tăng dần Ta sẽ tiến hành Chỉ tiêu tất cả các cặp nhịp thế Trong danh sách Đổi chỗ khác Trong danh sách này Đây là một ví dụ Mà trong nhóm mình đưa ra Chúng ta sẽ tiến tới Các bước cặp nhịp Thì đây là một toán Rất là dễ hiểu đơn giản Và dễ áp dụng Và các bước của nó Chỉ có 4 bước đơn giản Bước thứ nhất Chúng ta sẽ cho xếp từ đầu dãy Hay chúng ta sẽ cho y bằng 0 Và chúng ta sẽ tái tạo Một cái dì Cho cái dì này chạy từ y 1 Có nghĩa là chúng ta sẽ tìm Các cặp nhịp thế A thứ y Bắt đầu so sánh A thứ y Và A thứ y Bước ba là cho Trong một cái dọc y bé hơn n Thì chúng ta sẽ thực hiện Điều kiện A thứ y Bé hơn A thứ y Chúng ta sẽ xếp 2 cái cặp này với nhau Tiếp theo chúng ta sẽ tiến hành Swap cái này Đây là bước swap Chúng ta tiếp tục cố tăng Cái dì này lên một đơn vị Để so sánh với cái vị trí y Khi mà chúng ta So sánh hết trong cái dãy đó rồi Chúng ta sẽ tới bước 4 Là cho y bằng y cộng 1 Chúng ta sẽ tăng y Lên một đơn vị Với điều kiện là y Má bé hơn n chủ 1 Chúng ta cứ tiếp tục lập lại tới thứ 2 Nếu như y không còn trong N chủ 1 nữa Chúng ta sẽ dừng lại Chúng ta sẽ có một Dãy sắp xếp như chúng ta muốn Tiếp theo Tới các bước tiến hành Để dễ hiểu cho Thực toán này Ví dụ cho các bạn Chúng ta cũng cho ra Dãy số nguyên Là dãy số A này Gồm các số 12, 2, 8 5, 1, 6, 4, 15 Chúng ta cần phải sử dụng Cái dãy này để tự tăng dường Chúng ta sẽ cho nó diệt Từ đầu Y bằng 0 là vị trí đầu tiên Và dì này bằng 1 Có nghe chúng ta hiểu dì này Y cộng 1 Chúng ta tăng Y lên một đơn vị Thì nó sẽ là dì Ngay lúc này A thứ Y sẽ bằng 12 Và A thứ D sẽ bằng 2 Lúc này 12 lớn hơn 2 Chúng ta sẽ phải tiến hành Swap 12 lớn hơn 2 Chúng ta sẽ đổi chỗ Lúc này là 2 ra đầu đầu tiên Nó chỉ đơn giản như vậy thôi Tiếp theo chúng ta cứu lại Tăng dì lên một đơn vị Cho tăng dì lên một đơn vị Là cho lúc này là dì bằng 2 Thì A thứ D lúc này là bằng 8 Mà Mình sẽ trao hãnh với vị trí Y bằng 0 này A thứ Y là bằng 2 Thì 2 nó là bé hơn 8 rồi Chúng ta sẽ không swap nó Chúng ta sẽ không đổi chỗ nó Còn tăng dì lên tiếp theo Là lúc này là dì bằng 3 Thì 2 bé hơn 5 rồi Chúng ta cũng sẽ không tiến hành swap Chúng ta tăng đến khi dì bằng 4 Thì A thứ Y lúc này là 1 Thì 2 lớn hơn 1 Thì chúng ta sẽ tiến hành swap nó lại với nhau Còn chúng ta tăng dì bằng 5 Là bằng 6 Chúng ta cứ tăng dì cho đến hết Tới 15 Thì dì bằng 15 Thì là 2 bé Lúc này là 1 Thì 1 bé hơn 15 Chúng ta sẽ không tiến hành swap nữa OK Chúng ta cứ so sánh hết dãy Và chúng ta sẽ có được Cái số nhỏ nhất trong cái dãy này Chúng ta đã tiến hành so sánh được Cái dì này hết rồi Thì cái dì này lúc này là Hết rồi tiến hành tăng dì Nên vị trí này lên Thì lúc này là dì bằng 1 Thì dì sẽ bằng 2 Tại vì dì này sẽ bằng cho là Y cộng 1 Chúng ta lại tiếp tục so sánh So sánh A thứ Y này lúc này là 12 A thứ Y là bằng 8 Thì 12 Lúc này là lớn hơn 8 Thì chúng ta sẽ tiến hành swap lại với nhau 8 sẽ là trước 12 Rồi chúng ta tiếp tục tăng Cái dì này lên Thêm 1 đơn vị nữa là dì bằng 3 Mà lúc này là A thứ Y là 5 Thì tăng lại lớn hơn 5 Chúng ta sẽ tiến hành Swap lại Có nghĩa là 5 này là trước Chúng ta lại tiếp tục Tăng cái dì này lớn Lúc này là A thứ dì bằng 2 Mà 5 lại lớn hơn 2 Thì chúng ta sẽ tiến hành Swap lại với nhau 12 sẽ đổi ra trước Đây nha Chúng ta cứ tăng cái dì này lớn Cứ hết và chúng ta sẽ so sánh Và chúng ta sẽ tìm ra được Cái số Nhỏ nhất trong cái dãy này Chúng ta sẽ lôi ra trước Cứ tăng cái Y bằng 2 này lớn Trước lần cái dì này chúng ta sẽ tăng Thêm 1 đơn vị Chúng ta sẽ so sánh 12 mà lớn hơn 8 Thì 8 sẽ chỉ xuống đây Có 1 nghĩa nữa là Khi mà chúng ta mà tăng hết rồi á Thì tăng lên đến Khi cái số 15 này nè Chúng ta sẽ tăng cho đến Dì mà Dì này 7 rồi đúng không Thì chúng ta sẽ tăng lên 10 vị đúng không Thì cái dì này sẽ bằng 8 8 thì nó lớn hơn Cái dãy này gỗ nè Nó lớn hơn cái A len nè mọi người Nó lớn hơn cái A len nè Nó lớn hơn rồi thì nó sẽ Brack ra, nó phát ra khỏi cái chương trình này Nó phát ra khỏi cái chương trình này Thì nó sẽ quay lại cái bước Nó sẽ tiến hành hướng mức tư Rồi nó tăng cái Y này lên Và nó sẽ tăng cái dì này lên Nó cứ tiến hành so sánh so sánh Thì tăng lên Khúc này là Y bằng 2 Thì cái số 5 này Dì này sẽ bằng 4 Cái dì này bằng 4 thì 8 8 là lớn hơn 5 thì chúng ta sẽ tiến hành Swap nó Rất là đơn giản 5 này sẽ ra trước Đến khi mà dì bằng 5 Thì dì này sẽ bằng 6 Mà 5 lại nhỏ hơn 6 rồi Thì chúng ta sẽ không tiến hành swap Đến khi mà dì bằng 6 Thì 5 với lại 4 Thì 5 lớn hơn 4 Thì chúng ta sẽ tiến hành swap nó lại với nhau Rồi chúng ta sẽ tăng tiếp lên Cái dì này bằng 7 Dì này bằng 6 rồi Thì dì này sẽ bằng 7 Khúc này Cái vị trí Y bằng 2 này là 4 Thì 4 đã nhỏ hơn 15 rồi Chúng ta không tiến hành swap Rồi chúng ta cứ tiếp tục tăng Cái dì này lớn Ở dì bằng 8 Nó lớn hơn cái len này Giống như cái hồi nãy mình giải thích Thì nó sẽ thoát ra Rồi nó sẽ tăng cái Y này lên Nó rất là đơn giản và dễ hiểu Ví dụ này Nó là tăng Y này lên 3 Nó sẽ cứ Cứ so sánh Nó cứ tăng Y này lên Xong rồi tăng cái dì này lên Để so sánh với Y bằng 3 này hết Đây Y bằng 3 Thì khúc này là Y bằng 4 Dì bằng 4 Rồi dì bằng Y cộng 1 Thì A thứ Y bằng 12 Và A thứ dì bằng 8 Rồi 12 lớn hơn 8 Thì chúng ta sẽ tiến hành Swap lại với nhau Rồi dì bằng 5 Tăng cái dì này lên Thấy không nó cứ tăng cái dì này lên Thì cái dì này bằng 5 Thì A thứ Y bằng 8 Và A thứ dì bằng 6 Thì nó sẽ 8 lớn hơn 6 Thì chúng ta sẽ tiến hành swap Là lôi cái 6 này phía trước Rồi chúng ta cứ tăng cái dì này lên Dì này cộng lên 1 đơn vị nữa là dì bằng 6 Thì lúc này A thứ dì mới bằng 5 Thì 6 mà lớn hơn 5 Thì nó sẽ tiến hành Swap lại với nhau Nó cứ swap lại với nhau Thì nó sẽ lớn cái 5 này Và đến khi mà nó so sánh tới vị trí Thứ 15 là dì bằng 7 Thì 15 Nó lớn hơn 5 thì nó sẽ không swap lại với nhau Và nếu có tăng cái dì này lên 8 Thì nó lớn hơn K lên Thì nó sẽ tăng cái Y nhiều hơn Lúc này là Y bằng 4 Rồi chúng ta sẽ tăng cái dì này lên là dì bằng 5 Dì mà bằng 5 thì Lúc này là A thứ Y bằng 12 Mà dì bằng 5 thì 8 lớn hơn Mà 12 lớn hơn 8 Thì chúng ta sẽ tiến hành Vị trí Swap lại với nhau Rồi chúng ta tiếp tục tăng cái dì này bằng 6 lên Thì A thứ Y bằng 8 A thứ dì bằng 6 Thì 8 lớn hơn 6 Thì chúng ta sẽ tiến hành swap lại với nhau Đưa 6 lên đây Chúng ta tăng cái dì này lên 7 Thì A thứ dì này bằng 15 Thì chúng ta sẽ Mà A thứ Y là bằng 6 Thì chúng ta sẽ không tiến hành swap nữa Chúng ta cứ tăng cái A thứ Y này lên Lúc này là A thứ Y bằng 5 Thì A thứ dì bằng A thứ Y bằng 12 A thứ dì bằng 8 Nhà ấy lớn hơn 8 Chúng ta cứ tiến hành swap lại với nhau Cho đến khi tăng lên So sắn lên là A thứ A thứ dì này bằng 15 Mà 15 lại lớn hơn 8 Thì chúng ta sẽ không tiến hành swap nữa Thì bây giờ Đây Cho đến khi tới cuối giải Thì A thứ Y này bằng 6 và dì này bằng 7 Thì Tới khúc này Tăng tới Y bằng 6 thì mình có một câu hỏi là Mình có cần phải tăng cái Y này lên Lên 7 không Có nghĩa là Sau khi mình so sánh 2 cái này 7 với nhau rồi Thì cái dì này bằng 8 rồi Thì nó sẽ Nó sẽ lớn cái len rồi Nó sẽ thoát khỏi chương trình rồi Thì mình đặt câu hỏi là Có cần phải cho cái Y này bằng 7 không Lúc mà Y này bằng 7 Thì các bạn phải tăng cái dì này lên 1,5 Bởi vì dì nó bằng Y cộng 1 Y bằng 8 Thì nó sẽ không thoải cái len này rồi Nó sẽ không thoải cái len này rồi Tại vì cái len này nó chỉ tới Tới đây thôi Thì câu trả lời sẽ là không ha Mình chỉ tăng cái Y này lên thứ 6 thôi Có nghĩa là mình tới cái bước này là mình được rồi nè Tới cái bước này thôi là mình đã hoàn thành ra được Cái giải rồi Tại vì khi mà mình tăng cái Y này tới thứ 7 Thì nó là lần cuối cùng rồi nó sẽ không có cái gì để so sánh nữa Nên mình không cần phải tăng cái Y này lên 7 Cho nên có cái điều kiện là Y này Nó sẽ chạy Và nó sẽ nhỏ hơn là Nồn chùm 1 Các bạn nghĩ là sao Mà Y nó chạy tới nồn chùm 1 luôn Là nó sẽ như vậy Đây là video Minh họa cho Sắp xếp của cái giải thuật Các bạn xem vào trong cảnh nha Nó cứ đổi Nó cứ cho Y xong rồi nó tăng Vì dì nó sẽ đổi chỗ Thực tiếp Vị trí Chúng ta sẽ tới cái giải thuật Cái code mà của nhóm mình làm Đầu tiên thì chúng ta cứ Nhập mãn, xúc mãn Chúng ta sẽ viết cái menu Cho nó ha Và đây thường chính là Thuật integer sort Các bạn thấy nè cho trong gồm là Y và 0 Và Y nồn chùm 1 Hồi nãy mình cũng giải thích điều kiện Vì sao mà Y nó sẽ chạy tới cái vòng Y bằng nồi chùm 1 Và chúng ta sẽ tái tạo cho dì Y cầm 1 Cho dì chạy bé hơn nồn Và đây là bước tiến hành swap Chúng ta sẽ tiến hành cái điều kiện Đây là điều kiện Còn đây là bước swap Đây là một cái phái rất dễ hiểu Phần tiếp theo sẽ là phần đánh giá Cho cái thuật toán này Nhóm mình cũng đưa ra ưu điểm của nó Nó là đơn giản và dễ hiểu Và dễ cài đặt Integer sort có cơ chế hoạt động thực quan Và nó đặc biệt là chỉ hiệu quả với những danh sách Hiệu quả với những danh sách nhỏ Không cần mỗi nhớ phụ thêm Bên cạnh những ưu điểm đó Thì còn có những điểm như sau Hiệu suất kém với danh sách lớn Cần nhiều bước so sánh Và trao đổi không cần thiết Không thích hợp cho dữ liều động Và không tối ưu trong thực tế Đây là phần đánh giá Tiếp theo cũng là phần cuối cùng Đó là phần ứng dụng Trong giáo dục Vì sắp xếp trong danh sách Sinh viên thứ tự từ cao đến thấp Hoặc từ thấp đến cao Có thể giúp quản lý và đánh giá hiệu quả hơn Thuật toán đổi chỗ trực tiếp Có thể được sử dụng để sắp xếp danh sách này Một cách nhanh chóng và dễ dàng Mình cũng cảm ơn các bạn Đã lắng nghe Và nhờ mình quyết trình Để hiểu rõ hơn về dạy thuật này Cảm ơn các bạn