QJ411 - Sắp xếp nhanh
Xem dưới dạng PDFĐây là bài bổ sung mã (điền chỗ trống trong code), hãy hoàn thiện mã nguồn được cho trong đề bài, sao chép vào khung code bên phải, chọn ngôn ngữ biên dịch tương ứng (C/Java) rồi nộp bài. Nếu mã nguồn cho trong đề có nhiều ngôn ngữ, chỉ cần chọn một để hoàn thiện và nộp là được. Sau khi sao chép cần xóa dấu gạch dưới ở phần điền chỗ trống trong mã nguồn và điền đáp án của bạn vào. Sau khi nộp nếu chưa đạt, ngoài việc xem xét lỗi ở phần điền chỗ trống, còn cần lưu ý xem có phải do đã thay đổi phần không phải chỗ trống khi sao chép gây ra lỗi hay không.
Đoạn code sau có thể tìm ra phần tử nhỏ thứ $k$ trong mảng $a[ ]$. Nó sử dụng thuật toán chia để trị tương tự như trong sắp xếp nhanh, độ phức tạp thời gian kỳ vọng là $O(N)$.
Hãy đọc và phân tích kỹ mã nguồn, điền nội dung còn thiếu ở phần gạch dưới.
#include <stdio.h>
#include <cmath>
#include <ctime>
int quick_select(int a[], int l, int r, int k) {
if (l >= r) {
return a[l];
}
int p = rand() % (r - l + 1) + l;
int x = a[p];
{int t = a[p]; a[p] = a[r]; a[r] = t;}
int i = l, j = r;
while(i < j) {
while(i < j && a[i] < x) i++;
if(i < j) {
a[j] = a[i];
j--;
}
while(i < j && a[j] > x) j--;
if(i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
if(i - l + 1 == k) return a[i];
if(i - l + 1 < k) return quick_select( ); //Điền vào chỗ này
else return quick_select(a, l, i - 1, k);
}
int main()
{
srand(time(0));
int a[100];
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n", quick_select(a, 0, n-1, k));
return 0;
}
Nhận xét