Bé Bi học code

[Shaker Sort]
👋👋👋 Chào các bạn, ngày hôm nay các bạn hãy cùng mình tìm hiểu về giải thuật Shaker Sort nhé!

🤓🤓Shaker Short hay còn được gọi là thuật toán sắp xếp Cocktail là một phiên bản nâng cấp của giải thuật Bubble Sort mà chúng mình đã giới thiệu ở bài viết trước (bạn nào chưa biết Bubble Sort là gì thì có thể xem lại trong trang của bọn mình)

🧠Ý tưởng:👇👇
Thay vì đưa lần lượt từng phần tử nhỏ nhất (hoặc lớn nhất) về 1 phía của mảng như Bubble Sort thì Shaker Sort sau khi đưa phần tử nhỏ/lớn nhất lên đầu dãy, sau đấy lại đưa phần tử lớn/nhỏ nhất về cuối dãy. Như vậy, trong một lần duyệt, Shaker sort sẽ đưa ít nhất hai số về đúng với vị trí của nó.🍀🍀🍀

💡💡Độ phức tạp của thuật toán Shaker Sort:
● Tốt nhất là O(n).
● Xấu nhất là O(n2).
● Trung bình là O(n2).

🌈Dưới đây là hình ảnh minh họa cho Shaker Sort 👇
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Radix Sort]
👋👋 Hôm nay chúng ta sẽ có một cách tiếp cận mới trong việc sắp xếp. Thay vì sử dụng các thuật toán để so sánh các phần tử để xếp các phần tử vào đúng vị trí của mình, Radix sort lại đi theo một cách tiếp cận khác, nó là một thuật toán sắp xếp không so sánh. Cơ sở để Radix sort sắp xếp các phần tử dựa vào nguyên tắc phân loại thư. Vì vậy, Radix sort còn có tên là Postmans sort.

Chúng ta sẽ chia thành các nhóm dựa trên số hạng đơn vị, chục, trăm, ngàn,... để sắp xếp lại thứ tự của dãy số.
🧪 Để dễ hiểu, chúng ta xem xét ví dụ sau: [43, 613, 831, 987, 17, 210, 1990, 1234]
👉 Sắp xếp theo chữ số hàng đơn vị (theo thứ tự ban dầu của dãy số), ta được:
+ 210, 1990 // 0
+ 831 // 1
+ 43, 613 // 3
+ 1234 // 4
+ 987, 17 // 7
🔀 [210, 1990, 831, 43, 613, 1234, 987, 17]
👉 Tiếp theo ta sẽ lần lượt lấy từng số theo thứ tự ở bước 1 để chia nhóm theo chữ số hàng chục:
+ 210, 613, 17 // 1
+ 831, 1234 // 3
+ 43 // 4
+ 987 // 8
+ 1990 // 9
🔀 [210, 613, 17, 831, 1234, 43, 987, 1990]
👉 Tiếp tục là chữ số hàng trăm, ta được:
🔀 [17, 43, 210, 1234, 613, 831, 987, 1990]
👉 Tiếp tục là chữ số hàng nghìn, ta được:
🔀 [17, 43, 210, 613, 831, 987, 1234, 1990]

❗ Vì số lớn nhất chỉ có 4 chữ số nên khi đến hàng nghìn, dãy của chúng ta đã được sắp xếp !

✍Độ phức tạp của thuật toán: O(n) 🤔🤔

🔭Tham khảo: geeksforgeeks, Viblo
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Quick Sort - Sắp xếp nhanh]

👋👋Hello mọi người, sau thời gian nghỉ tết khá dài thì tụi mình đã quay trở lại rồi đây🥳. Hôm nay, để tiếp tục với series những thuật toán sắp xếp, chúng ta sẽ đến với giải thuật Quick Sort hay còn gọi là sắp xếp nhanh.

✍Giống như Merge Sort, Quick Sort cũng là dùng phương pháp chia để trị để sắp xếp.
📌Thuật toán sẽ chia mảng thành hai phần bằng cách so sách từng phần tử trong mảng với một phần tử được chọn gọi là Pivot:
👉Một bên sẽ bao gồm các phần tử nhỏ hơn Pivot,
👉Bên còn lại sẽ chứa các phần tử lớn hơn hoặc bằng Pivot.
Quá trình chia này sẽ tiếp diễn cho tới khi độ dài của các mảng con đều bằng một.

✍Kỹ thuật chọn phần tử Pivot:
Có rất nhiều cách để chọn một phần tử Pivot. Tuy nhiên để đơn gian, chúng ta sẽ thường sử dụng một trong 3 cách sau:
👉Luôn chọn phần tử đầu tiên hoặc cuối cùng làm Pivot.
👉Chọn phần tử đứng giữa danh sách làm Pivot.
👉Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm Pivot.
👉Chọn một phần tử ngẫu nhiên làm Pivot. Tuy nhiên, hãy cẩn thận với cách này nha, bởi vì nó có thể rới vào một số trường hợp đặc biệt.

✍Độ phức tạp của thuật toán:
👉Trường hợp tốt nhất: O(nlog(n))
👉Trung bình: O(nlog(n))
👉Trường hợp xấu nhất: O(n^2)
Khi chúng ta luôn chọn đúng phần tử lớn nhất hoặc nhỏ nhất làm Pivot. Nếu chọn phần tử đầu tiên hay cuối cùng làm Pivot thì trường hợp xấu nhất sẽ xảy ra😭😭.
Tuy nhiên, bạn không cần lo lắng điều này bởi vì chúng ta có thể hiện thực Quick Sort theo các cách khác nhau tùy vào cách chọn phần tử Pivot🤩🤩.

Các bạn có thể xem hình minh họa dưới đây để dễ hiểu hơn nhé!😍😍
🔭Tham khảo: geeksforgeeks, codelearn
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Merge Sort] - Sắp xếp trộn
👋👋👋Chào các bạn, hôm nay mình sẽ giới thiệu cho các bạn một trong những thuật toán có độ phức tạp ở mức trung bình và cùng sử dùng phương pháp chia để trị.

Ứng dụng của merge sort:
📌Sắp xếp linked list.
📌Sử dụng trong External Sorting (*)
📌Bài toán số lượng đảo ngược (Inversion Count Problem)

Cách Merge Sort hoạt động
🔥 Chia nhỏ dãy để có thể dễ dàng sắp xếp những dãy nhỏ hơn.
🔥 Khi trộn 2 dãy nhỏ hơn đã được sắp xếp trước, ta sẽ dễ dàng sắp xếp để tạo ra dãy to hơn.
🕵Đánh giá thuật toán
✍Độ phức tạp của thuật toán:
👉Trường hợp tốt nhất: O(nlog(n))
👉Trung bình: O(nlog(n))
👉Trường hợp xấu: O(nlog(n))
Trong cả 3 trường hợp thì độ phức tạp không đổi!

Các bạn có thể xem hình minh họa dưới đây để dễ hiểu hơn nhé!😍😍
🔭Tham khảo: geeksforgeeks.org
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Shell Sort]

👋👋👋Chào các bạn, hôm nay mình sẽ giới thiệu cho các bạn 1 thuật toán sắp xếp mới dựa trên Insertion Sort (bọn mình đã giới thiệu ở bài trước) đó chính là Shell Sort. 💪Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Shell Sort được sử dụng khi:
📌Việc gọi một ngăn xếp là tốn kém. Thư viện uClibc sử dụng kiểu thuật toán sắp xếp này.
📌Kỹ thuật đệ quy vượt quá giới hạn cho phép. Trình nén bzip2 sử dụng kiểu sắp xếp này.
📌Sắp xếp chèn không hoạt động tốt khi các phần tử gần bằng nhau nằm ở cách xa nhau. Sắp xếp Shell giúp giảm khoảng cách giữa các phần tử gần bằng nhau. Do đó, sẽ có ít số lần hoán đổi được thực hiện hơn.

Các shell sort hoạt động
🔥Bước 1: Khởi tạo giá trị h
🔥Bước 2: Chia list thành các sublist nhỏ hơn tương ứng với h
🔥Bước 3: Sắp xếp các sublist này bởi sử dụng sắp xếp chèn (Insertion Sort)
🔥Bước 4: Lặp lại cho tới khi list đã được sắp xếp

🕵Đánh giá thuật toán
✍Độ phức tạp của thuật toán:
👉Trường hợp tốt nhất: O(n*logn)
👉Trung bình: O(n*logn)
👉Trường hợp xấu: O(n^2)

Các bạn có thể xem hình minh họa dưới đây để dễ hiểu hơn nhé!😍😍
🔭Tham khảo: codecrucks.com, viettuts.vn, tek4.vn
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Insertion Sort]

👋Tiếp tục trong series những thuật toán sắp xếp hôm nay mình sẽ giới thiệu đến các bạn thuật toán Insertion Sort.

📌Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

🤔Giả sử chúng ta có 1 dãy có 2 phần gồm phần đầu đã được sắp xếp theo thứ tự và phần sau chưa được sắp xếp. Chúng ta sẽ thực hiện duyệt từng phần tử và chèn từng phần tử vào đó đúng vị trí trong mảng đã được sắp xếp. Cụ thể:
✍ Khởi tạo mảng với dãy con có k = 1 phần tử đã được sắp xếp.
✍ Duyệt từng phần tử từ ví trị thứ 2 và chèn phần tử đó vào trong đoạn [0...i] sao cho dãy này vần đảm bảo tính thứ tự. sau mồi lần duyệt thì phần được sắp xếp sẽ tăng lên 1 và phần còn lại chưa được sắp xếp sẽ giảm đi 1.
✍ Cứ tiếp tục như vậy cho đến khi duyệt hết tất cả các phần tử của mảng.

🕵Đánh giá thuật toán
✍Độ phức tạp của thuật toán:
👉Trường hợp tốt nhất: O(n)
👉Trung bình: O(n^2)
👉Trường hợp xấu: O(n^2)

✍Không gian bộ nhớ sử dụng: O(1)

Chi tiết về minh họa bạn có thể xem ở bên dưới.👇👇
Tham khảo: codelearn, nguyenvanhieu, wikipedia
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍

[Selection Sort]

👏 Tiếp tục trong series những thuật toán sắp xếp của tụi mình là Selection Sort - một trong những cách sắp xếp tự nhiên nhất trong thực tế.

🧠 Khi bạn muốn sắp xếp 1 dãy số chẳng hạn, một trong những ý tưởng đơn giản nhất là tìm số nhỏ nhất, bỏ vào vị trí đầu tiên, tiếp tục tìm số nhỏ nhất trong những số còn lại, bỏ vào vị trí thứ 2,... cứ tiếp tục như thế, bạn sẽ sắp xếp xong khi dãy còn lại chỉ còn 1 phần tử.

🎯 Xuất phát từ ý tưởng đó, Selection Sort sẽ đưa lần lượt những phần tử vào đúng vị trí của mình trong dãy được sắp xếp.

🤔 Về độ phức tạp, ta xét số phép so sánh và số phép gán:
- Số phép so sánh: để tìm được số nhỏ nhất trong n số cần (n-1) bước, tiếp theo là (n-2),...
⏩n(n-1)/2 bước
- Số phép gán: trong trường hợp dãy đã được sắp xếp sẵn, ta không cần dùng phép gán nhưng trong trường hợp xấu nhất, ta sẽ phải swap để đưa 1 số về đúng vị trí nên sẽ là 3n (3 là số phép gán trong phép swap, n là số phép swap để đưa n số về đúng vị trí trong trường hợp xấu nhất).

🧮 Đánh giá: Selection Sort khá là dễ hiểu và khá cơ bản. Độ phức tạp là O(n^2). Không gian bộ nhớ là O(1).

Tham khảo: codelearn

[Thuật toán sắp xếp]
🥳🥳🥳Chào các bạn, đã bao giờ các bạn gặp phải tốn kha khá thời chỉ để tìm một tờ giấy trong mớ tài liệu hay là tìm một cuốn sách đang bị nhét vào một góc nào đó trong kệ hay không😁😁? Giả sử như những tờ giấy hay quyển sách đó được sắp xếp ngăn nắp và có thứ tự thì mình đoán là các bạn sẽ chỉ cần vài giây để tìm ra nó🤏🤏.
🍀🍀Trong lập trình cũng vậy, việc sắp xếp data để thuận tiện cho việc truy xuất luôn là một vấn đề được rất nhiều người quan tâm do đó có rẩt nhiều thuật toán sắp xếp thú vị được ra đời. Ngày hôm nay mình sẽ giới thiệu cho các bạn thuật toán đầu tiên và mình nghĩ rằng nó cũng là thuật toán đơn giản nhất đó chính là Bubble Sort🎈🎈 .
🧠Ý tưởng:👇👇
● Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo.
● Ở lần xử lý thứ i có vị trí đầu 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.
Các bạn có thể xem hình minh họa dưới đây để dễ hiểu hơn nhé!😍😍
Để biết thêm nhiều điều thú vị về lập trình hãy like 👍 và follow 👀 tụi mình nha.😍😍