• Thuật toán sẽ được chạy như thế nào?
• Cái mới ra đời có những ưu điểm gì.
• Và những đoạn code.

Selection Sort

1. tìm vị trí chứa giá trị Min của mảng đang xét.
2. Thuật toán Selection Sort.

def pos_min_arr(pos_start,pos_end,arr):
    pos_min = pos_start
    for i in range(pos_start+1,pos_end,1):
      if arr[pos_min] > arr[i]:
            pos_min = i
    return pos_min
    
def selection_sort(arr):
    n=len(arr)
    for i in range(0,n,1): 
        pos_min =  pos_min_arr(i,n,arr)
        arr[i],arr[pos_min] = arr[pos_min],arr[i]
    print(arr)

Độ phức tạp của thuật toán O(nC2).

Interchange Sort

Ý tưởng: cũng tương tự như selection-sort, thay vì ta kiếm vị trí Min rồi mới đổi chổ hai giá trị, thì ta đổi chổ ngay khi phát hiện giá trị của vị ví đang xét mà lớn hơn giá trị tại vị trí bất kì trong đoạn đang xét. Vì vậy thuật toán này mới có tên gọi đổi chổ trực tiếp.

Xem trên YouTube ↗

def interchange_sort(arr):
    n=len(arr)
    for i in range(0,n,1): 
       for j in range(i+1,n,1):
           if arr[i]>arr[j]:
               arr[i], arr[j] = arr[j], arr[i]
    print(arr)

Độ phức tạp của thuật toán O(nC2).

Insertion Sort

Như bạn thấy selection-sort hay Interchange-sort nó sẽ tìm trên đoạn từ vị trí đang xét đến cuối mảng như vậy thì thật là củ chuối 😏😏. Nhưng vì củ chuối là bất diệt nên bạn sẽ thấy nó ở mọi nơi :))).

vậy Insertion sort ra đời để thu hẹp khoảng cách của vị trí bắt đầu và vị trí kết thúc.

Ý tưởng: nó sẽ xét phạm vi của mảng từ đầu mảng đến vị trí đang xét, sẽ tìm vị trí mà giá trị tại vị trí đó lớn hơn giá trị vị trí đang xét và chèn vào trước vị trí này. Từ đó trong phạm vi này sẽ luôn được sắp xếp. Ví dụ: có 3 giá trị 1,3,5,6,4 vị trí đang xét có giá trị là 4 thì khi 4 so sánh với 3 thì sẽ đẩy các giá trị 5, 6 lên 1 đơn vị thành 1,3,5,5,6 và sau đó thay số 5 thành 4, ta có: 1,3,4,5,6.

def insertion_sort(arr):
    for i in range(1,len(arr),1): 
        key = arr[i] 
        j= i-1
        while j >= 0 and key < arr[j] : 
            arr[j+1] = arr[j] # đẩy giá trị các vị trí từ j đến i lên một đơn vị để có chổ chèn giá trị đang xét
            j -= 1
        arr[j+1] = key

Độ phức tạp của thuật toán O(n2).

Binary Insertion Sort

Ý tưởng: là bước cải tiến của insertion-sort bằng cáchách kết hợp với thuật toán tìm kiếm nhị phân (Binary Search) để thu hẹp phạm vi tìm kiếm thay vì sử dụng phạm vi từ đầu mảng đến vị trí đang xét và thế là thuật toán Binary Insertion Sort ra đời =)))😄😄😄.

Bạn có thể tìm hiểu về Binary search tại đây. Để hiểu rỏ thu hẹp phạm vi tìm kiếm là như thế nào. Nếu vẫn không hiểu có thể thảo luận với mình bằng cách Comment 😜😜.

Xem trên YouTube ↗

def binary_insertion_sort(arr):
    n=len(arr)
    for i in range(1,n,1):
     key = arr[i]
     left = 0
     right = i - 1
     while left <= right:
         m = int((left + right) / 2);
         if key < arr[m]:
             right = m - 1
         else: left = m + 1
     for j in range(i-1,left-1,-1):
        arr[j + 1] = arr[j];
     arr[left] = key
    print(arr)

Độ phức tạp của thuật toán O(n*log(n)) + O(n2).

Bubble Sort

Ý tưởng: ở thuật toán này sẽ xuất hiện 2 vị trí đang xét i và j công dụng của 2 vị trí này sẽ như sau: 

Đầu tiên khởi tạo i=0 và j=n và so sánh từng cặp giá trị tại vị trí đang xét j và j-1 nếu giá trị tại vị trí đang xét j nhỏ hơn giá trị tại vị trí đang xét j-1 thì thực hiện đổi chổ hai giá trị này với nhau và sẽ tiếp tục cho đến khi về vị trí đang xét i+1=j thì dừng. Bằng cách này sẽ đẩy lần giá trị nhỏ nhất về vị trí đang xét i.
Hoặc bạn có thể so sánh các cặp giá trị i và i+1 nếu giá trị tại vị trí đang xét i nhỏ hơn giá trị tại vị trí đang xét i+1 thì thực hiện đổi chổ hai giá trị này với nhau và sẽ tiếp tục cho đến khi về vị trí đang xét i+1=j thì dừng. Bằng cách này sẽ đẩy lần giá trị lớn nhất về vị trí đang xét j.

def bubble_sort(arr):
    n = len(arr)
    for i in range(0,n,1): 
       for j in range(n-1,i-1,-1):
           if arr[j-1]>arr[j]:
               arr[j-1], arr[j] = arr[j], arr[j-1]
    print(arr)

Độ phức tạp của thuật toán O(n2).

Shaker Sort

def shaker_sort(arr):    
    left = 0
    right = len(arr) - 1
    while (left < right):
        for i in range(left,right,1):
            if (arr[i] > arr[i + 1]):
                arr[i], arr[i + 1]=arr[i+1], arr[i]
        right-=1
        for i in range(right,left,-1):
            if (arr[i] < arr[i - 1]):
                arr[i], arr[i - 1]=arr[i-1], arr[i]
        left+=1
    print(arr)