SIMPLE
STRING
ARRAY
SORTING
POINTER
CALCULATION
NUMBER
OTHER
C
BÀI TẬP C
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Sắp xếp một mảng số nguyên sử dụng thuật toán heap sort trong C

Thuật toán heap sort là một trong những thuật toán sắp xếp hiệu quả và phổ biến. Nó hoạt động dựa trên cấu trúc dữ liệu heap và có độ phức tạp thời gian trung bình là O(n log n). Trong bài viết này, mình sẽ tìm hiểu cách sử dụng thuật toán heap sort để sắp xếp một mảng số nguyên trong ngôn ngữ lập trình C.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Bài tập sắp xếp một mảng số nguyên sử dụng thuật toán heap sort trong C

Cách giải quyết:

Thuật toán heap sort hoạt động bằng cách xây dựng một heap từ mảng và sau đó sắp xếp mảng dựa trên thuộc tính heap (có thể là một heap tăng dần hoặc giảm dần). Dưới đây là một phần mã minh họa:

Dưới đây là một ví dụ về cách cài đặt thuật toán heap sort trong ngôn ngữ lập trình C:

Bài viết này được đăng tại [free tuts .net]

#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int n;
    printf("Nhập số phần tử của mảng từ màn hình freetuts.net: ");
    scanf("%d", &n);

    int arr[n];
    printf("Nhập các phần tử của mảng :\n");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    heapSort(arr, n);

    printf("Mảng sau khi sắp xếp là:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Giải thích code:

  • Trong hàm heapify(), mình kiểm tra xem phần tử i có lớn hơn các con của nó không, nếu không, chúng ta đổi chỗ phần tử i với con lớn nhất và tiếp tục kiểm tra với con lớn nhất đó.
  • Trong hàm heapSort(), mình xây dựng một heap từ mảng và sau đó sắp xếp mảng bằng cách lấy phần tử lớn nhất từ heap và đưa nó vào cuối mảng.
  • Trong hàm main(), mình nhập số phần tử của mảng và các phần tử của mảng từ người dùng. Sau đó, chúng ta gọi hàm heapSort() để sắp xếp mảng và in ra kết quả.

Kết quả:

Giả sử bạn nhập số phần tử của mảng là 6 và các phần tử của mảng là 12 11 13 5 6 7. Chương trình sẽ xuất ra:

Screenshot 202024 03 19 20164425 png

Trong bài viết này, mình đã tìm hiểu cách sử dụng thuật toán heap sort để sắp xếp một mảng số nguyên trong ngôn ngữ lập trình C. Điều này là một trong những kỹ thuật quan trọng để xử lý sắp xếp dữ liệu trong lập trình.

Cùng chuyên mục:

Các hàm xử lý mảng đa chiều (array.h) trong C/C++

Các hàm xử lý mảng đa chiều (array.h) trong C/C++

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý chuỗi (string.h) trong C/C++

Các hàm xử lý chuỗi (string.h) trong C/C++

Thread Pools và Parallel Algorithms trong C++

Thread Pools và Parallel Algorithms trong C++

Tạo và quản lý các Multithreading trong C++

Tạo và quản lý các Multithreading trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Try, Catch, và Throw của Exception Handling trong C++

Try, Catch, và Throw của Exception Handling trong C++

Cách sử dụng Lambda Expressions trong C++

Cách sử dụng Lambda Expressions trong C++

Sử dụng weak_ptr trong C++

Sử dụng weak_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng unique_ptr trong C++

Sử dụng unique_ptr trong C++

Tổng quan về Smart Pointers trong C++

Tổng quan về Smart Pointers trong C++

Sử dụng Iterators trong STL của C++

Sử dụng Iterators trong STL của C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng trong List trong C++

[Iterator] Sử dụng trong List trong C++

[STL] Sử dụng Vector trong C++

[STL] Sử dụng Vector trong C++

Tổng quan về Iterators trong C++

Tổng quan về Iterators trong C++

Top