[Thuật toán] Thuật toán sắp xếp (Phần 3)

Hôm nay mình xin giới thiệu tiếp về thuật toán sắp xếp: Gnome sort, Quick sort, Heap sort….

Các bạn có thể xem lại các phần trước ở đây: [bsbutton text=”Phần 1″ link=”https://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep/” target=”This page” style=”default” theme=”default” size=”normal”] [bsbutton text=”Phần 2″ link=”https://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep-phan-2/” target=”This page” style=”default” theme=”default” size=”normal”]

VII./ Gnome sort

Gnome sort là một trong nhữngthuật toán sắp xếp đơn giản nhất, thuộc nhóm các thuật toán có độ phức tạp là O(n2) như sắp xếp nổi bọt, sắp xếp chèn,…. tuy nhiên điểm khác biệt là của Gnome sort là chúng ta chỉ cần sử dụng 1 vòng lặp thay vì 2 vòng lặp so với các thuật toán khác trong cùng nhóm.

  • Ý tưởng

Ý tưởng của Gnome thật đơn giản, bắt đầu đi từ vị trí thứ 2 của dãy giá trị cần sắp xếp tăng dần, so sánh giá trị phần tử ở vị trí hiện tại với phần tử phía trước nó. Nếu nhỏ hơn thì hoán vị rồi lùi lại một vị trí (giới hạn biên là vị trí xuất phát), nếu lớn hơn thì tiến lên một vị trí. Cứ như vậy cho tới khi tiến tới vị trí cuối cùng của dãy giá trị.
  • Thuật toán

Bước 1:

Gán i = 1; // duyệt từ vị trí thứ 2

Gán j = 2; // theo dõi các vị trí kế tiếp, sau khi kết thúc vòng lặp hiện tại thì nhảy tới vị trí này để tiếp tục lặp

Bước 2:

Nếu (Array[i] < Array[i-1]) thì {Swap(Array[i], Array[i-1]); –i}

Nếu (i==0) thì i = j++

Ngược lại i = j++;

Bước 3:

Nếu i < n thì lặp lại bước 2

Ngược lại: dừng

  • Cài đặt code /C++

  • Đánh giá giải thuật

Trường hợp Độ phức tạp
Xấu nhất O(n2)
Tốt nhất O(n)

Độ phức tạp trung bình = O(n2)

  • Video Demo

VIII./ Sắp xếp nhanh (Quick sort)

  • Ý tưởng

Giải thuật Quick sort sắp xếp các dãy a[0], a[1],…., a[n] dựa trên việc phân hoạch dãy ban đầu thành 3 đoạn:

Đoạn 1: gồm các phần tử có giá trị bé hơn x

Đoạn 2: gồm các phần tử có giá trị bằng x

Đoạn 3: gồm các phần tử có giá trị lớn hơn x

x: giá trị của phần tử chính giữa dãy ban đầu.

Do vậy, đoạn thứ 2 đã có sắp xếp.

Để sắp xếp đoạn 1 và đoạn 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch ban đầu vừa trình bày.

  • Giải thuật

Bước 1: Nếu left >= right // dãy có ít hơn 2 phần tử

=> Kết thúc

Bước 2:

x = a(right – left) /2

Phân hoạch dãy ban đầu aleft …. aright thành các đoạn: aleft….aj, aj+1….ai-1, ai….. aright

Bước 3: Sắp xếp đoạn 1: aleft….aj

Bước 4: Sắp xếp đoạn 3: ai….. aright

  • Cài đặt code C/C++

  • Đánh giá thuật toán

Trường hợp Độ phức tạp
Tốt nhất O(nlog(n))
Xấu nhất O(n2)

Độ phức tạp trung bình  = O(nlog(n))

  • Video Demo

IX./ Sắp xếp vun đống (Heap sort)

Heap sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng được.

Để làm được điều này Heap sort thao tác dựa trên cây.

  • Ý tưởng

Ở cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đó phần tử ở nút gốc là phần tử lớn nhất.

Nếu loại bỏ gốc ra khỏi cây, thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toàn.

Bước kế tiếp có thể sử dụng lại kết quả so sánh của bước hiện tại.

  • Giải thuật

Giai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heap

Giai đoạn 2: Sắp xếp dãy số dựa trên heap:

Bước 1 :Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy:

r = n-1; Swap (a1 , ar );

Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1;

Hiệu chỉnh phần còn lại của dãy từ a1 , a2 … ar thành một heap

Bước 3:

Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2

Ngược lại : Dừng

Heap:  Là một dãy các phần tử al, al+1 ,… , ar thoả các quan hệ với mọi i ∈ [l, r]:

ai >= a2i+1

ai >= a2i+2 ((a; a2i+1), (ai ; a2i+2) là các cặp phần tử liên đới

  •  Cài đặt code C/C++

  • Đánh giá thuật toán

Trường hợp Độ phức tạp
Tốt nhất  O(1)
Xấu nhất O(n*logn)

Độ phức tạp trung bình  = O(n*logn)

  • Video Demo

(Còn tiếp ….)

Share
  • -Phần sắp xếp vun đống(Heap Sort) ngay cái hàm Create_heap có cái dòng là left = 2/n -1 sửa lại là left = n/2 – 1 chạy mới đúng, vs cái hàm Heap_sort ngay cái câu lệnh if (right > 0) có dấu ; làm người đọc hoang mang quá :)) mong BQT sữa lại ^^

    • Roc

      mi ak Quang

Share