# Các giải thuật sắp xếp - P3: Selection sort
**1. Selection sort**
Thuật toán selection sort hoạt động theo một cách rất đơn giản. Chọn ra phần tử bé nhất trong phần mảng chưa được sắp xếp và swap nó lên đầu mảng.

Mã giả:

function selection_sort(array):

    n = len(array)
    #Iterate through the array
    for i from 0 to n-2:
        min_idx = i     #Assume i is min_idx
        
        #Find smallest element in unsorted list
        for j from i+1 to n:
            if array[j] < array[min_idx]:
                min_idx = j
        
        #swap smallest array with first element 
        if min_idx != i
            swap(array[min_idx],array[i])
        
    return array

Độ phức tạp:
Worst time complexity: n^2
Best time complexity: n^2
Average time complexity: n^2

Dễ thấy với độ phức tạp cao, selection sort làm việc không hiệu quả với các mảng có kích thước lớn

**2. Heap sort**

Heap sort dựng một cấu trúc dữ liệu heap - một binary tree mà parent node sẽ luôn lớn hơn children node.

Thuật toán của heap sort như sau:
1. Tạo ra 1 binary tree từ mảng
2. Chuyển tree thành max heap
3. Bỏ parent node và đưa vào vị trí cuối cùng của mảng.
4. Chuyển thành max heap
5. Lặp lại

Mã giả

function HeapSort(array):
    n = length(array)

    // Build a max heap bottom-up
    for i from n / 2 - 1 down to 0: //n / 2 -1 means the last parent node
        heapify(array, n, i)

    // Extract elements from the heap one by one
    for i from n - 1 down to 0:
        swap array[0] and array[i]   // Move the root (maximum element) to the end
        heapify(array, i, 0)         // Heapify the reduced heap

    return array

function heapify(array, length = n, root = i):
    largest = i       // Initialize the largest element as root
    left_child = 2 * i + 1  // Index of the left child
    right_child = 2 * i + 2 // Index of the right child

    // If left child is larger than root
    if left < n and array[left] > array[largest]:
        largest = left

    // If right child is larger than largest so far
    if right < n and array[right] > array[largest]:
        largest = right

    // If largest is not root
    if largest != i:
        swap array[i] and array[largest]
        heapify(array, n, largest)  // Recursively heapify the affected sub-tree

Độ phức tạp
Worst time complexity: nlogn
Best time complexity: nlogn
Average time complexity: nlogn

Độ phức tạp của heap sort luôn là nlogn, vì vậy nó hoạt động hiệu quả cho mảng có kích thước lớn. Tuy nhiên, mặc dù độ phức tạp tốt trên lý thuyết, trên thực tế, heap sort lại chậm hơn so với quick sort, vì việc duy trì heap tiêu tốn hơn so với phân hoạch trong quick sort.