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

Tìm phần tử lớn thứ k trong mảng với thuật toán Quickselect trong C

Trong lập trình, đôi khi mình cần tìm phần tử lớn thứ k trong một mảng. Để thực hiện điều này, mình có thể sử dụng thuật toán Quickselect, một biến thể của thuật toán QuickSort. Trong bài viết này, mình sẽ tìm hiểu cách thực hiện điều này 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 tìm phần tử lớn thứ k trong mảng với thuật toán Quickselect trong C

Cách giải quyết:

Thuật toán Quickselect hoạt động bằng cách chọn một phần tử ngẫu nhiên từ mảng và chia mảng thành hai phần: một phần lớn hơn hoặc bằng phần tử được chọn (gọi là phần chính) và một phần nhỏ hơn phần tử được chọn (gọi là phần phụ). Sau đó, mình sẽ kiểm tra vị trí của phần tử được chọn. Nếu vị trí đó bằng k, mình đã tìm thấy phần tử lớn thứ k. Nếu vị trí đó nhỏ hơn k, mình sẽ tìm phần tử lớn thứ k trong phần chính. Nếu vị trí đó lớn hơn k, mình sẽ tìm phần tử lớn thứ k trong phần phụ.

Dưới đây là một ví dụ về cách cài đặt tìm phần tử lớn thứ k trong mảng bằng thuật toán Quickselect 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 swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low < high) {
        int pi = partition(arr, low, high);
        if (pi == k)
            return arr[pi];
        else if (pi < k)
            return quickSelect(arr, pi + 1, high, k);
        else
            return quickSelect(arr, low, pi - 1, k);
    }
    return arr[low];
}

int main() {
    int n, k;
    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 từ màn hình freetuts.net:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("Nhập số k (phần tử lớn thứ k muốn tìm): ");
    scanf("%d", &k);

    int kth_largest = quickSelect(arr, 0, n - 1, n - k);
    printf("Phần tử lớn thứ %d trong mảng là %d.\n", k, kth_largest);

    return 0;
}

Giải thích code:

  • Trong hàm partition()mình chọn một phần tử làm pivot và chia mảng thành hai phần: một phần lớn hơn hoặc bằng pivot và một phần nhỏ hơn pivot.
  • Trong hàm quickSelect(), mình sử dụng partition() để tìm vị trí của pivot trong mảng và so sánh nó với k. Nếu vị trí đó bằng k, mình đã tìm thấy phần tử lớn thứ k. Nếu vị trí đó nhỏ hơn k, chúng ta tiếp tục tìm kiếm trong phần lớn hơn pivot. Nếu vị trí đó lớn hơn k, mình tiếp tục tìm kiếm trong phần nhỏ hơn pivot.
  • Trong hàm main(),mình nhập số phần tử của mảng, các phần tử của mảng và số k từ người dùng. Sau đó, mình gọi hàm quickSelect() để tìm phần tử lớn thứ k trong mảng và in ra kết quả.

Kết bài:

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à 4 2 7 1 5 3, và số k là 3. Chương trình sẽ xuất ra:

Screenshot 202024 03 19 20163803 png

Trong bài viết này, mình đã tìm hiểu cách tìm phần tử lớn thứ k trong một mảng bằng cách sử dụng thuật toán Quickselect 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 trong việc xử lý mảng và tìm kiếm 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