# Các giải thuật sắp xếp - P1: Interchange sort

**1 . Interchange sort**
Ý tưởng:
Thuật toán interchange sort (đổi chỗ trực tiếp) sẽ bắt cặp tất cả các phần tử và đổi chỗ chúng nếu như chúng nghịch thế. Do đó nó mang tên gọi "đổi chỗ trực tiếp"

Mã giả:

for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n;j++)
        if ( a[i] > a[j] ){
            swap (a[i],a[j])
            }

Best time complexity: n^2
Worst time complexity : n^2
Average time complexity : n^2
**2. Bubble sort**
Ý tưởng:
Tương tự như interchange sort, nhưng thay vì bắt cặp i,j, bubble sortbắt cặp 2 phần tử liên tiếp. Nếu chúng nghịch thế thì đổi chỗ
Mã giả:

for(int i=0;i<n-1;i++){
    swapped = false
    for(int j=0;j<n-i-1;j++){
        if ( a[j] > a[j+1]){
            swap(a[j],a[j+1]);
            swapped = true;
        }
        if (!swapped) 
            break;
    }
}

Phần tử lớn nhất sẽ "nổi bọt" lên đầu.
Best time complexity: n
Worst time complexity : n^2
Average time complexity : n^2

**3. Quick sort**
Ý tưởng:
Quick sort là thuật toán sắp xếp dạng chia để trị, dựa trên cách phân hoạch (partition). Ý tưởng chung của các phân hoạch là chọn ra phần tử chốt và chia đôi mảng ra thành 2 phần, 1 phần nhỏ hơn pivot và cùng nằm về một phía với pivot, ngược lại với các phần tử lớn hơn pivot. Cách phân hoạch ảnh hưởng tới độ phức tạp thời gian của Quick sort.

Mã giả:

function quicksort(A, lo, hi) is 
  // Ensure indices are in correct order
  if lo >= hi || lo < 0 then 
    return
    
  // Partition array and get the pivot index
  p = partition(A, lo, hi) 
      
  // Sort the two partitions
  quicksort(A, lo, p - 1) // Left side of pivot
  quicksort(A, p + 1, hi) // Right side of pivot

Phân hoạch lomuto:
Phân hoạch lomuto chọn phần tử cuối cùng là pivot, sau đó set i = lf - 1 (i sau này là vị trí của pivot), sau đó xếp chúng theo quy tắc đã nêu (chia thành 2 phần).
Mã giả

function LomutoPartition(array, lf, rt):
    pivot = array[rt]    // Select the pivot element (usually the last element)
    i = lf - 1            // Initialize the index of the smaller element

    for j = lf to rt - 1:
        if array[j] <= pivot:
            i = i + 1    // Increment the index of the smaller element
            swap array[i] and array[j]   // Swap array[i] and array[j]

    swap array[i + 1] and array[high]   // Swap the pivot element with the element at (i + 1)
    return (i + 1)    // Return the partitioning index

Vì luôn chọn phần tử cuối cùng nên đôi khi mảng sẽ không được chia đều (trường hợp phần tử cuối là lớn nhất). Lomuto partition sẽ thực hiện nhiều lần swap hơn so với Hoare, vì vậy nó sẽ chậm hơn.
Time complexity O(n)

Phân hoạch Hoare:
Phân hoạch Hoare thường chọn pivot là phần tử giữa hoặc phần tử đầu.
Set 2 con trỏ tại 2 điểm i = lf và j = rt của mảng. Bắt đầu tìm 2 giá trị a[i] và a[j] mà tại đó xảy ra a[i] > pivot và a[j] < pivot. Swap(a[i], a[j]). Tiếp tục cho đến khi i và j vượt qua nhau là hết một lần phân hoạch.
Mã giả:

function HoarePartition(array, low, high):
    pivot_index = (low + high) / 2   // Calculate the index of the middle element
    pivot = array[pivot_index]       // Select the middle element as the pivot
    i = low - 1                      // Initialize the left pointer
    j = high + 1                     // Initialize the right pointer

    while true:
        do:
            i = i + 1                // Move the left pointer towards the right
        while array[i] < pivot
        
        do:
            j = j - 1                // Move the right pointer towards the left
        while array[j] > pivot

        if i >= j:
            return j                 // Return the partitioning index
        
        swap array[i] and array[j]   // Swap array[i] and array[j]

Trường hợp tệ nhất cũng là khi mảng được phân hoạch không đều.
Time complexity O(n)

Khi mảng được phân hoạch không đều, quick sort phải sort lại cả mảng trừ đi phần tử cuối, do đó Best time complexity: nlogn
Worst time complexity : n^2
Average time complexity : nlogn

4. Cocktail shaker sort
Cocktail sort tương tự như bubble sort, nhưng cocktail sort sẽ có 2 vòng iterate đẩy phần tử lớn nhất lên đầu và đẩy phần tử bé xuống cuối
Mã giả

function CocktailSort(array):
    n = length(array)
    swapped = true
    start = 0
    end = n - 1

    while swapped:
        swapped = false

        // Forward pass: Move the largest element to the end
        for i from start to end - 1:
            if array[i] > array[i + 1]:
                swap array[i] and array[i + 1]
                swapped = true

        if not swapped:
            break  // If no swaps occurred, the array is sorted

        swapped = false
        end--  // Decrease the end pointer

        // Backward pass: Move the smallest element to the beginning
        for i from end - 1 to start step -1:
            if array[i] > array[i + 1]:
                swap array[i] and array[i + 1]
                swapped = true

        start++ // Increase the start pointer

    return array

Best time complexity: n
Worst time complexity : n^2
Average time complexity : n^2