Bang hộiTiền mặt: 0 Xu Trò chơiHộp quà giáng sinhThứ Sáu, 15:12:19 - 13/12/2024
Chia sẻ kiến thức ngôn ngữ lập trình C, C++, C#, Java, Python, PHP, JS, SQL ...

Các điều hành viên: Admin, Mod, SMod

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

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

#1 » Gửi bài gửi bởi nghiammo1992 » 12/09/2021 12:30 » @523436

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


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ã: Chọn tất cả
#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[- 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;
}


Sửa lần cuối: nghiammo1992 23/09/2021 20:43
nghiammo1992 ✅
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)

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

#2 » Gửi bài gửi bởi nghiammo1992 » 12/09/2021 12:32 » @523437

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


Mã: Chọn tất cả
#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 (<= 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 (<= j)
        {
            while (Data[i] < key)
                i++;
            while (Data[j] > key)
                j--;

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

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

        if (< j)
            quickSort(Data, l, j);
        if (> 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;
}

nghiammo1992 ✅
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)

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

#3 » Gửi bài gửi bởi nghiammo1992 » 12/09/2021 12:34 » @523438

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ã: Chọn tất cả
#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 1ni++)
    {
        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_arrayk0); // Initialize count_array elements as zero

    
for(int i 0ni++)
        
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 1ki++)
        
count_array[i] += count_array[1];


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


    for(
int i 0ni++)
        
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(arrn);

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

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

    return 
0;
}

 
nghiammo1992 ✅
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)

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

#4 » Gửi bài gửi bởi nghiammo1992 » 12/09/2021 12:36 » @523439

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ã: Chọn tất cả
#include <iostream>


using namespace std;


// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int lint mint r)
{
    
int ijk;
    
int n1 1;
    
int n2 =  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 (0n1i++)
        
L[i] = arr[i];
    for (
0n2j++)
        
R[j] = arr[1j];

    
/* Gộp hai mảng tạm vừa rồi vào mảng arr*/
    
0// Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
    
0// Khởi tạo chỉ số bắt đầu của mảng con thứ hai
    
l// IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
    
while (n1 && 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 (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 (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 lint r)
{
    if (
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(arrlm);
        
mergeSort(arrm+1r);

        
merge(arrlmr);
    }
}


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(arr0n-1);

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

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

    return 
0;
}


 
nghiammo1992 ✅
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)



Quay về C, C++, C#, Java, Python, PHP, JS, SQL ...

 


  • Chủ đề tương tự
    Trả lời
    Xem
    Bài viết mới nhất