Điều chỉnh thứ tự của mảng sao cho số lần chạy của quicksort là lớn nhất

#1

Dạ e có 1 bài tập như sau:
Hãy viết chương trình nhập vào một mảng số nguyên và đổi lại trật tự của mảng đó sao cho khi sắp xếp lại mảng bằng hàm quick sort, giá trị của biến “count” sẽ là lớn nhất."

Đầu vào (INPUT):

  • Dòng đầu tiên là số phần tử của mảng ( số n ).
  • Dòng tiếp theo chứa n số nguyên, đây là các phần tử của mảng.

Đầu ra (OUTPUT):

  • In ra biến count.

Hàm quicksort được cài đặt sẵn như sau:

#include <iostream>
using namespace std;
int count=0;
int partition(int pivot, int *a, int n) {
        int left = 0, right = n - 1;
        while (left <= right) {
                while (a[left] < pivot){
                        left++;  
                        count ++;
                }
                while (a[right] > pivot){
                        right--;
                        count++;
                }
                count += 2;

                if (left <= right)
                {
                        swap(a[left], a[right]);
                        left++;
                        right--;
                }
        }
        return left-1;
}
void quicksort(int *a, int l, int r){
    if (r > l){
        auto pivot = a[(l+r)/2];
        auto i = partition(pivot, a+l, r-l+1);
        quicksort(a, l, l+i);
        quicksort(a, l+i+1, r);
    }
}

Test case mẫu:
Input:
20
6437 192 16336 29050 3746 15591 2733 8872 19858 17308 17588 13142 29202 5510 14238 8515 26345 29236 14379 9555
Output:
160

Mọi người giúp đỡ em với ạ.

#2

At first glance, your code contains numerous bugs. The most serious bug is the lack of loop checking, which can cause an infinite loop. Other bugs are the lack of index checking, which can trigger an out-of-bounds exception.

Conclusion: You should completely rewrite your code. Maybe someone can help you. I’m not doing this because I think you should do it yourself to learn programming and become a developer.

#3

Thank you for replying.

This is an assignment given by my teacher, and the code above is not mine but provided by my teacher. The teacher assigns students to complete exercises on a website called Wecode , where a default template is provided. Students are required to code based on this template without modifying the pre-written parts. The code above is a template given by my teacher for my assignment.

I respect your opinion and will email my teacher separately to review his template.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?