BubbleSort (Nổi bọt)

• Độ phức tạp: O(n²)
• Ưu điểm: Dễ cài đặt, nhìn là hiểu ko yêu cầu logic cao siêu.
• Nhược điểm: Tất nhiên là chậm so với các thuật toán sắp xếp mà đòi hỏi khâu cài đặt khó nhằn hơn như : quicksort, mergesort, ... (trong hầu hết các trường hợp nhưng mà ko phải tất cả nha - don't get me wrong).

Parsing source code...

Các thuật toán đơn giản tương tự insertionSort, selectionSort mình sẽ ko trình bày ở đây. Thế nên bubbleSort là đại diện cho các thuật toán sắp xếp chậm.

Oke có thể bạn nhìn trông hơn khác một tý nhưng mà đây là một cải tiến của BubbleSort cho trường hợp đặc biệt.

MergeSort (Sắp xếp gộp)

Thuật toán kinh điển mà ai học thuật toán cũng phải học qua, nó ko chỉ là một thuật toán sắp xếp mà nó còn liên quan đến cả một concept khác là : "Chia để trị".

• Độ phức tạp: O(n log n).
• Ưu điểm:
  • Độ phức tạp thuật toán ko đổi O(n log n) (cả worst case với best case). Nhìn chung là nhanh, thích hợp với bộ dữ liệu chưa biết trước, nó ko biết dùng thuật toán sắp xếp gì thì cứ áp thằng này vào, dù sao thì ta cũng biết chắc chắn là độ phức tạp của nó luôn là O(n log n).
  • Nó là ví dụ điển hình để biểu diễn : chia để trị, đệ quy, ...
• Nhược điểm: Rõ ràng là nó khó cài đặt hơn bubbleSort hay insertionSort, ... các thuật toán sorting có độ phức tạp O(n²)

Parsing source code...

QuickSort (Sắp xếp nhanh)

• Độ phức tạp: O(n log n)
• Ưu điểm: Nhanh trong hầu hết các trường hợp (again hầu hết)
• Nhược điểm:
  • Khó cài đặt hơn tất nhiên. (Nó giống thằng mergeSort phải chia để trị nên tiếp tục dùng đệ quy).
  • Ko may rơi vào trường hợp worst case thì đúng là tác dụng ngược.

Parsing source code...

BucketSort (Sắp xếp xô chậu)

• Độ phức tạp: O(nk) (n: số phần tử mảng sắp xếp, k: số lượng phần tử nhiều nhất trong 1 xô)
• Ưu điểm:
  • Nếu bạn đã biết trước một vài thông tin mảng cần sắp xếp (giá trị max, hoặc min). Nếu bạn chọn được số lượng xô chậu hợp lý thì nó sẽ rất nhanh. (Nhiều nếu quá 😵 ).
  • Nó cũng là chia để trị nhưng nó ko phải chỉ chia đôi mà chia thành nhiều phần rồi sắp xếp giá trị trong các phần một cách độc lập - nên nó tốt cho xử lý song song.
• Nhược điểm:
  • Nó phụ thuộc vào nhiều thứ : cách chọn số lượng xô chậu, hiểu biết về cái mảng mà bạn định sắp xếp (tốt nhất giá trị của mảng nên phân bố đều trong khoảng min-max của mảng), phụ thuộc vào thuật toán sắp xếp ngoài (bạn phải tự chọn thuật toán sắp xếp cho các xô chậu của bạn)

Parsing source code...

Dễ thấy rằng thuật toán này gồm phụ thuộc vào nhiều yếu tố khác, ví dụ nếu n phần tử của mảng ban đầu được cho vào đúng 1 chậu thì nó sẽ thành O(n²). Việc dùng 1 vòng lặp (forEach, reduce) mặc dù ko lồng nhau nhưng mà nó vẫn tạo ra constant factor, việc tìm maxValue cũng tạo ra constant factor O(n) nên nhìn chung thì nó cũng ko nhanh lắm.

🎁 Bonus: Constant factor chính là các phép tính toán trong thuật toán mà không được biểu diễn vào big O Notation. Theo big O thì O(5n) cũng được biểu diễn O(n) => 4n chính là constant factor. Điều này lý giải cho vì sao 2 thuật toán cùng có big O là O(n) mà khi benchmark thì lại kết quả ko tương đồng lắm đó là do constant factor.

Tổng kết.

Mặc dù mình còn thuật toán HeapSort nữa nhưng mà thuật toán đấy chủ yếu là phần implementation Heap (có thể mình sẽ làm ở phần cấu trúc dữ liệu) nên chỉ vài thuật toán này thôi.

[Q] Tại sao lại đẻ ra nhiều thuật toán sắp xếp vậy?

[A] Vì mỗi thuật toán thì đều có ưu và nhược điểm tùy vào từng trường hợp sử dụng. Bạn có tin bubbleSort có lúc nhanh hơn cả quickSort ko?

Xét trường hợp mà mảng đã sắp xếp rồi cho vào bubbleSort và quickSort ở phần bubbleSort cải tiến bên trên của mình nếu mảng đã sắp xếp thì độ phức tạp thuật toán là O(n) trong khi đó quickSort lại là worst case O(n²) => bubbleSort sẽ nhanh hơn.