CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN VỚI PYTHON

Bài toán: Cho một mảng A có n phần tử hãy sắp xếp mảng theo thứ tự không giảm.

1. Sắp xếp chọn.

Thuật toán này khá đơn giản:

• Bước 1: Chọn phần tử nhỏ nhất trong tập hợp cần sắp xếp
• Bước 2: Hoán đổi vị trí của phần tử nhỏ nhất vừa tìm được trong tập hợp với phần tử ngoài cùng bên trái
• Bước 3: Loại phần tử ngoài cùng bên trái ra khỏi tập hợp cần sắp xếp
• Bước 4: Lặp lại quá trình trên.

Code python

def SelectionSort(A):
	n = len(A)
	for i in range(n):
		minIndex=i
		for j in range(i+1, n):
			if A[j]

Độ phức tạp của thuật toán là $O(n^2)$ 

2. Sắp xếp trộn. (Merge Sort)

Sắp xếp trộn sử dụng kỹ thuật chia để trị

• Bước 1: Chia đầu vào thành 2 nửa.
• Bước 2: Xắp sếp 2 nửa bằng cách đệ quy. quá trình đệ quy kết thúc khi độ dài mảng bằng 1.
• Bước 3: Trộn hai nửa đã xắp sếp lại thành một mảng không giảm.

Pseudocode

$MergeSort(A[1...n]):$
$if \text{ } n = 1:$
    $return \text{ } A$
$mid \text{ } \leftarrow \left \lfloor \frac{n}{2} \right \rfloor$
$B \text{ } \leftarrow \text{ } MergeSort(A[1...mid])$
$C \text{ } \leftarrow \text{ } MergeSort(A[nid...n])$
$A' \text{ } \leftarrow \text{ } Merge(B,C)$
$return \text{ } A'$

$Merge(B[1...p],C[1...q]):$
$D \text{ } \leftarrow$ mảng trống có kích thước $p+q$
Điều kiện B và C khác rỗng:
    $b \text{ } \leftarrow$ phần tử đầu trong $B$

    $c \text{ } \leftarrow$ phần tử đầu trong $C$

    $if\text{ } b \leq c$:
        chuyển b từ B sang D
    $else:$
        chuyển c từ C sang D
chuyển phần còn lại của B và C sang D
return D

Code python

def MergeSort(A: list) -> list:
  def Merge(B: list, C: list) -> list:
    while B and C:
      yield (B if B[0]<=C[0] else C).pop(0)
    yield from B
    yield from C
  if len(A) == 1:
    return A
  mid = len(A)//2
  B = MergeSort(A[: mid])
  C = MergeSort(A[mid: ])
  result = list(Merge(B, C))
  return result

Code có sử dụng while loops and lists và yield trong python

Độ phức tạp về thời gian của hàm Merge là $O(n)$

Như vậy ta có độ phức tạp của thuật toán là $T(n) \leq 2T(\frac{n}{2})+O(n)$ 

Áp dụng định lý master ta có $T(n)=O(n\log_2n)$ 

3. Sắp xếp đếm

Giả sử đầu vào là một mảng A[1...n] và tất cả các phần tử là số nguyên giới hạn trong khoảng từ a đến b.

Đúng với tên gọi 'sắp xếm đếm' ta đếm số phần tử trong mảng A sau đó sắp xếp chúng. 

Pseudocode

$CountSort(A[1...n]):$
$if \text{ } A = []:$
    $return \text{ } A$
$Count[min(A)...max(A)] \text{ }\leftarrow [0,...,0]$
$\text{for i from 1 to n:}$
    $Count[A[i]] \leftarrow Count[A[i]] + 1$
$\text{for i from 2 to max(A) - min(A) +1:}$
    $Count[i] \leftarrow Count[i-1] + Count[i]$
$Result[1...n] \leftarrow [0...0]$
$\text{for i from 1 to n:}$
    $Result[Count[A[i]-min(A)]] \leftarrow A[i]$
    $Count[A[i]-min(A)] \leftarrow Count[A[i]-min(A)]-1$
$\text{return Result}$

Code python

def CountSort(A: list) -> list:
	if A == []:
		return A
	A_len = len(A)
	A_min = min(A)
	A_max = max(A)
	counting_A_length = A_max - A_min + 1
	counting_A = [0]*counting_A_length
	for i in A:
		counting_A[i-A_min] += 1
	for i in range(1,counting_A_length):
		counting_A[i] += counting_A[i-1]
	result = [0]*A_len
	for i in range(A_len):
		result[counting_A[A[i]-A_min] - 1] = A[i]
		counting_A[A[i]-A_min] -= 1
	return result
A=[-2,-2,-3,-1]
print(CountSort(A))

Độ phức tạp của thuật toán là $O(n+b-a)$

4. Sắp xếp nhanh. (Quick Sort)

Sắp xếp nhanh cũng sử dụng giải thuật chia để trị

• Bước 1: Chọn phần tử đầu tiên của mảng $A$ làm pivot. Chia mảng thành 2 nửa, nửa bên trái có phần tử nhỏ hơn hoặc bằng $A(l)$, nửa bên phải ngược lại.  
• Bước 2: Tiếp tục chia nhỏ các bài toán con bằng đệ quy. Quá trình đệ quy kết thúc khi bài toán con có độ dài bằng 1.
• Bước 3: Ta được mảng đã sắp xếp.

Pseudocode

$QuickSort(A, l, r):$
$if \text{ } l \geq r:$
    $return$
$m \leftarrow partition(A, l, r)$
$QuickSort(A, l, m-1)$
$QuickSort(A, m+1, r)$

$Partition(A, l, r):$
$pivot \leftarrow A[l]$
$j=l$
$\text{for i from l+1 to r:}$
    $if \text{ } A[i] \leq A[l]:$
        $j \leftarrow j+1$
        $swap \text{ } A[j] \text{ and } A[i]$
$swap \text{ } A[l] \text{ and } A[j]$
$return \text{ } j$

Code python

def QuickSort(A, left, right):
    def partition(A, l, r):
        j = l
        x = A[l]
        for i in range(l+1,r+1):
            if A[i] <= x:
                j = j + 1
                A[i], A[j] = A[j], A[i]
        A[j], A[l] = A[l], A[j]
        return j
    if left >= right:
        return 
    m = partition(A, left, right)
    QuickSort(A, left, m-1)
    QuickSort(A, m+1, right)
A = [6,2,8,9,5]
left, right = 0, len(A) - 1
QuickSort(A, left, right)
print(A)

Độ phức tạp của thuật toán

Thời gian chạy của $Partition(A, l, r)$ là $O(n)$. Vậy thời gian chạy của $QuickSort(A, l, r)$ là $T(n)=T(m-1)+T(n-m)+O(n)$

Trường hợp tệ nhất $T(n)=O(n^2)$. Trường hợp tốt nhất $T(n)=O(n\log_2n)$

Nếu như ta luôn chọn phân tử đầu tiên của mảng A làm pivot thì rất có thể xảy ra trường hợp tồi tệ là $O(n^2)$ theo như  định luật Murphy. Do đó ta cần chọn pivot ngẫu nhiên để luôn đảm bảo xác suất xảy ra trường hợp tồi tệ là thấp và xác suất xảy ra trường hợp tốt $O(n\log_2n)$ cao.

Pseudocode $RandomizedQuickSort$

$RandomizedQuickSort(A, left, right):$
$if \text{ } left \geq right:$
    $return$
$k \leftarrow \text{random number between left and right}$
$swap \text{ } A[l] \text{ } and \text{ } A[k]$
$m \leftarrow partition(A, l, r)$
$RandomizedQuickSort(A, l, m-1)$
$RandomizedQuickSort(A, m+1, r)$

Code python

import random
def RandomizedQuickSort(A, left, right):
  def Partition(A, l, r):
    pivot = A[l]
    j = l
    for i in range(l+1, r+1):
      if A[i] <= pivot:
        j += 1
        A[j], A[i] = A[i], A[j]
    A[l], A[j] = A[j], A[l]
    return j
  if left >= right:
    return 
  k = random.randint(left, right)
  A[left], A[k] = A[k], A[left]
  m = Partition(A, left, right)
  RandomizedQuickSort(A, left, m - 1)
  RandomizedQuickSort(A, m + 1, right)
A = [5,1,8,9,2,4,7,3,6]
left , right = 0, len(A) - 1 
RandomizedQuickSort(A, left, right)
print(A)

Định lý

Giả sử rằng tất cả các phần tử của $A[1...n]$ đôi một khác nhau. Khi đó thời gian chạy trung bình của RandomizedQuickSort(A) là $O(n\log_2n)$ trong khi trường hợp xấu nhất thời gian chạy của thuật toán là $O(n^2).$

Chứng minh định lý

• Nhận xét: Thời gian chạy của thuật toán tỉ lệ thuận với số phép so sánh trong hàm partition(A)

Để thuận tiện trong việc phân tích thời gian chạy ta gọi mảng $A'[1...n]$ là mảng đã được sắp xếp.

• Với $i<j,$ ta định nghĩa biến ngẫu nhiên $\chi_{ij}$ như sau

$\chi_{ij}=\begin{cases} 1& A'[i] \text{ and } A'[j] \text{ được so sánh} \\ 0& \text{ngược lại} \\ \end{cases}$

• Với mọi $i < j,A[i]$ và $A[j]$ được so sánh chính xác một lần hoặc hoàn toàn không được so sánh
• Thời gian chạy trong trường hợp xấu nhất là $O(n^2).$ Tuy nhiên xác suất rất thấp.
• Nhận xét quan trọng: $\chi_{ij}=1$ nếu pivot được chọn đầu tiên trong $A'[i...j]$ là $A[i]$ hoặc $A[j]$
• Khi đó $Prob(\chi_{ij}=1)=\frac{2}{j-i+1}$

Gọi $X$ là số lượng phép so sánh trong quá trình chạy hàm $RandomizedQuickSort(A).$

Ta có $X= \sum_{i=1}^{n}\sum_{j=i+1}^n\chi_{ij}$

Luật số lớn mạnh nói rằng trung bình cộng của $X$ hội tụ hầu như chắc chắn về $E(X)$ 

Phát biểu này cho phép ta ước tính thời gian chạy trung bình của thuật toán là

$\begin{align*}E\left(X\right)&=E\left(\sum_{i=1}^{n}\sum_{j=i+1}^n\chi_{ij}\right)=\sum_{i=1}^{n}\sum_{j=i+1}^nE(\chi_{ij}) = \sum_{i=1}^{n}\sum_{j=i+1}^n\left(Prob(\chi_{ij}=1).1+Prob(\chi_{ij}=0).0\right)\\&=\sum_{i=1}^{n}\sum_{j=i+1}^nProb(\chi_{ij}=1)=\sum_{i=1}^{n}\sum_{j=i+1}^n\frac{2}{j-i+1}=\sum_{i=1}^n2\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n-i+1} \right).\end{align*}$

Tổng $1+\frac{1}{2}+\dots+\frac{1}{n}$ ký hiệu là $H_n$, được gọi là chuỗi điều hòa thứ n và nằm trong khoảng $[\ln n,1+\ln n]$. Vì vậy 

$E(X)<2n(H_n-1)\leq 2n\ln n=\Theta(n\ln n).$

Định lý  trên đã được chứng minh, để ý thấy rằng nếu các phần tử của mảng $A[1...n]$ không thỏa mãn điều kiện đôi một khác nhau thì các phân tích ở trên sẽ không đúng, vì vậy để xử lý các phần tử bằng nhau, chúng ta thay thế dòng 

$m \leftarrow Partition(A, l, r)$

bằng dòng 

$(m_1,m_2) \leftarrow Partition3(A, l, r)$

sao cho

• Với mọi $l \leq k \leq m_1-1,A[k]  < X$
• Với mọi $m_1 \leq k \leq m_2, A[k] = X$
• Với mọi $m_1+1 \leq k \leq r, A[k]>X$

Pseudocode $RandomizedQuickSort$

$RandomizedQuickSort(A, left, right):$
$if \text{ } l \geq r:$
    $return$
$k \leftarrow \text{ramdom number between l and r}$
$swap \text{ } A[l] \text{ }and \text{ }A[k]$
$(m_1,m_2) \leftarrow Partition3(A, left, right)$
$RandomizedQuickSort(A, left, m_1-1)$
$RandomizedQuickSort(A, m_2+1, right)$

$Partition3(A, l, r):$
$pivot \leftarrow A[l]$ 
$m_1, m_2, i \leftarrow l, r, l$
$while \text{ } i \leq m_2:$
    $if \text{ } A[i] < pivot:$
        $swap \text{ } A[i] \text{ and } A[m_1]$
        $i,m_1 \leftarrow i+1,m_1+1$
    $elif \text{ } A[i] = pivot:$
        $i \leftarrow i+1$
    $elif \text{ } A[i] > pivot:$
        $swap \text{ } A[i] \text{ and } A[m_2]$
        $m_2 \leftarrow m_2 -1$
    $return m_1,m_2$

Code python

def Partition3(A, l, r):
  pivot = A[l]
  m_1, m_2 = l, r
  i = l
  while i <= m_2:
    if A[i] < pivot:
      A[i], A[m_1] = A[m_1], A[i]
      m_1 += 1
      i += 1
    elif A[i] == pivot:
      i += 1
    else:
      A[i], A[m_2] = A[m_2], A[i]
      m_2 -= 1
  return m_1, m_2

Bài viết khá dài, cho nên mình xin dừng lại tại đây, qua tết sẽ viết bổ sung phần rút gọn code đệ quy của quick sort, và một số chú thích thêm, bài viết này tham khảo rất nhiều từ giaithuatlaptrinh.com