[C++] Các thuật toán sắp xếp cơ bản thường sử dụng

https://i.imgur.com/YjrPc4J.png



Thuật toán sắp xếp theo cơ số Radix Sort (Không hoạt động với mảng chứa số âm)

Mã nguồn PHP:

---

#include <iostream>


using namespace std;


int get_max_element(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++)
    if (arr[i] > max)
      max = arr[i];
  return max;
}

void sort_counting(int arr[], int size, int place) {
  int output[size + 1];
  int max = (arr[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((arr[i] / place) % 10) > max)
      max = arr[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[(arr[i] / place) % 10]++;

  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

  for (int i = size - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    arr[i] = output[i];
}

void sort_radix(int arr[], int size) {
  int max = get_max_element(arr, size);
  for (int place = 1; max / place > 0; place *= 10)
    sort_counting(arr, size, place);
}


int main()
{

    int arr[] {32,71,12,45,26,80,53,33,7,99,1,5,2,3,100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    sort_radix(arr, n);

    cout << "So luong phan tu trong mang: " << n << endl;

    for (int i : arr) {
        cout << i << " ";
    }

    return 0;
} 


---

Thuật toán sắp xếp nhanh Quick Sort

Mã nguồn PHP:

---

#include <iostream>


using namespace std;


void quickSort(int Data[], int l , int r)
{
    // If the first index less or equal than the last index
    if (l <= r)
    {
        // Create a Key/Pivot Element
        int key = Data[(l+r)/2];

        // Create temp Variables to loop through array
        int i = l;
        int j = r;

        while (i <= j)
        {
            while (Data[i] < key)
                i++;
            while (Data[j] > key)
                j--;

            if (i <= j)
            {
                swap(Data[i], Data[j]);
                i++;
                j--;
            }
        }

        // Recursion to the smaller partition in the array after sorted above

        if (l < j)
            quickSort(Data, l, j);
        if (r > i)
            quickSort(Data, i, r);
    }
}


int main()
{

    int arr[] {32,71,12,45,26,80,53,33,-7,99,1,5,2,-3,-100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    quickSort(arr, 0, n-1);

    cout << "So luong phan tu trong mang: " << n << endl;

    for (int i : arr) {
        cout << i << " ";
    }

    return 0;
} 


---

Thuật toán Counting Sort – Thuật toán sắp xếp đếm phân phối (thuật toán tốt hơn Quick Sort, nhưng tốn bộ nhớ hơn)

Mã nguồn PHP:

---

#include <iostream>


using namespace std;


// Function that sort the given input
void counting_sort(int input[], int n)
{

    int output[n]; // The output will have sorted input array
    int max = input[0];
    int min = input[0];

    for(int i = 1; i < n; i++)
    {
        if(input[i] > max)
            max = input[i]; // Maximum value in array
        else if(input[i] < min)
            min = input[i]; // Minimum value in array
    }

    int k = max - min + 1; // Size of count array

    int count_array[k]; // Create a count_array to store count of each individual input value
    fill_n(count_array, k, 0); // Initialize count_array elements as zero

    for(int i = 0; i < n; i++)
        count_array[input[i] - min]++; // Store count of each individual input value

    /* Change count_array so that count_array now contains actual
     position of input values in output array */
    for(int i = 1; i < k; i++)
        count_array[i] += count_array[i - 1];


    // Populate output array using count_array and input array
    for(int i = 0; i < n; i++)
    {
        output[count_array[input[i] - min] - 1] = input[i];
        count_array[input[i] - min]--;
    }


    for(int i = 0; i < n; i++)
        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values

}


int main()
{

    int arr[] {32,71,12,45,26,80,53,33,-7,99,1,5,2,-3,-100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    counting_sort(arr, n);

    cout << "So luong phan tu trong mang: " << n << endl;

    for (int i : arr) {
        cout << i << " ";
    }

    return 0;
} 


---

Thuật toán sắp xếp trộn Merge Sort (nên ưu tiên dùng thuật toán Quick Sort hơn)

Mã nguồn PHP:

---

#include <iostream>


using namespace std;


// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* Tạo các mảng tạm */
    int L[n1], R[n2];

    /* Copy dữ liệu sang các mảng tạm */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Gộp hai mảng tạm vừa rồi vào mảng arr*/
    i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
    j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
    k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy các phần tử còn lại của mảng L vào arr nếu có */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy các phần tử còn lại của mảng R vào arr nếu có */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn
        int m = l+(r-l)/2;

        // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}


int main()
{

    int arr[] {32,71,12,45,26,80,53,33,-7,99,1,5,2,-3,-100};

    int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    mergeSort(arr, 0, n-1);

    cout << "So luong phan tu trong mang: " << n << endl;

    for (int i : arr) {
        cout << i << " ";
    }

    return 0;
} 


---