[C++] Các thuật toán sắp xếp cơ bản thường sử dụng : C, C++, C#, Java, Python, PHP, JS, SQL ...

Xem bài viết chưa trả lời | Xem chủ đề đang hoạt động

Trang chủ » Kiến thức lập trình » C, C++, C#, Java, Python, PHP, JS, SQL ...

Thời gian được tính theo giờ UTC + 7 Giờ

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

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

Bạn đang xem trang 1 / 1 trang

[ 4 bài viết ]

Xem bản in | Gửi Email giới thiệu

Chủ đề trước | Chủ đề kế tiếp

Người gửi

Nội dung

nghiammo1992

Tiêu đề bài viết: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Đã gửi: 12/09/2021 12:30

☀️2/30☀️

Ngày tham gia: 08/03/2012 10:56
Bài viết: 15
Đến từ: Hà Giang
Thiết bị: Nokia N96
Số điện thoại: 0367790762

[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ã:

#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;
}

_________________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

Sửa lần cuối: nghiammo1992 23/09/2021 20:43

Đầu trang

nghiammo1992

Tiêu đề bài viết: Re: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Đã gửi: 12/09/2021 12:32

☀️2/30☀️

Ngày tham gia: 08/03/2012 10:56
Bài viết: 15
Đến từ: Hà Giang
Thiết bị: Nokia N96
Số điện thoại: 0367790762

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

Mã:

#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;
}

_________________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

Đầu trang

nghiammo1992

Tiêu đề bài viết: Re: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Đã gửi: 12/09/2021 12:34

☀️2/30☀️

Ngày tham gia: 08/03/2012 10:56
Bài viết: 15
Đến từ: Hà Giang
Thiết bị: Nokia N96
Số điện thoại: 0367790762

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ã:

#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;
}

 

_________________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

Đầu trang

nghiammo1992

Tiêu đề bài viết: Re: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Đã gửi: 12/09/2021 12:36

☀️2/30☀️

Ngày tham gia: 08/03/2012 10:56
Bài viết: 15
Đến từ: Hà Giang
Thiết bị: Nokia N96
Số điện thoại: 0367790762

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ã:

#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;
}


 

_________________
Diễn đàn chia sẻ kiến thức máy tính:
KETNOI123.COM

Ấn hiện ra để xem chữ ký của mình:

Đầu trang

Bạn đang xem trang 1 / 1 trang

[ 4 bài viết ]

Trang chủ » Kiến thức lập trình » C, C++, C#, Java, Python, PHP, JS, SQL ...

Thời gian được tính theo giờ UTC + 7 Giờ

Chủ đề		Người gửi	Trả lời	Xem	Bài viết mới nhất
Chủ đề tương tự
	[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng	nghiammo1992	2	1027	13/09/2021 11:03 nghiammo1992
	[Java] Sắp xếp mảng các đối tượng trong Java - Sort an array of objects in Java	SQL	0	559	23/02/2024 02:20 SQL
	Độ phức tạp của thuật toán	nghiammo1992	0	636	11/09/2021 12:09 nghiammo1992
	[SQL] 100 từ khóa SQL thường hay sử dụng và phố biến nhất	iPhone	0	178	04/10/2024 19:34 iPhone
	Các hàm làm tròn số trong PHP	nghiammo1992	0	3317	16/09/2015 22:40 nghiammo1992
	[SQL] Các loại JOIN trong SQL	nghiammo1992	0	746	11/02/2022 02:05 nghiammo1992
	[Java] Các kiểu dữ liệu trong Java - Data Types in Java	CSS	0	420	08/07/2024 01:43 CSS
	[Java] Các cấu trúc dữ liệu phổ biến trong Java - Data Structures in Java	Nginx	0	523	28/07/2024 01:50 Nginx
	[MySQL] Lệnh tìm kiếm và thay thế nội dung trong MySQL	nghiammo1992	0	1318	21/10/2013 00:56 nghiammo1992
	[MySQL] Xử lý nội dung trùng lặp trong Database	nghiammo1992	0	1057	04/02/2014 18:07 nghiammo1992

Ai đang trực tuyến?

Đang xem chuyên mục này: Không có thành viên nào đang trực tuyến và 3 khách

Bạn không thể tạo chủ đề mới trong chuyên mục này.
Bạn không thể trả lời bài viết trong chuyên mục này.
Bạn không thể sửa những bài viết của mình trong chuyên mục này.
Bạn không thể xoá những bài viết của mình trong chuyên mục này.

Chuyển đến:

CHIASE123.COM - Diễn đàn chia sẻ kiến thức

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

Ai đang trực tuyến?