Đ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

[Nguyen_Nguyen_Khoi (Nguyên Nguyễn Khôi)]

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 ạ.

[Joe (Schwarz)]

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.

[Nguyen_Nguyen_Khoi (Nguyên Nguyễn Khôi)]

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.

[Joe (Schwarz)]

From a “teacher”?
What happens if pointer a (i.e., address) is added with a value l that points outside the allocated range (here, int[])?

auto i = partition(pivot, a+l, r-l+1); // <--- address a + l ?

[rogp10]

No bound-checking is necessary for the two inner while loops. Verify these two loop variants:

• a[0…left-1] <= pivot
• a[right+1…n-1] >= pivot

[Nguyen_Nguyen_Khoi (Nguyên Nguyễn Khôi)]

Thanks for replying.

In your case, the solution would be incorrect and would not be accepted.

The code above is just a template; how the functions below are written is up to you. If you choose the initial indices “l” and “r” incorrectly, then naturally, your solution will be incorrect and will not be accepted.

I emailed my teacher, and he responded that there is no issue with the code above.

This is the full assignment from my teacher, I just shortened it.

If you think the code is wrong, give me a test case that proves it and I will send it to my teacher.

[Joe (Schwarz)]

@rogp10 Correct! My poor eyesight.

[Joe (Schwarz)]

@Nguyen_Nguyen_Khoi
The quicksort method has three parameters: pointer a, int r, and int l.
Since the pointer does not specify the size of an allocated range (here: the array size), this can lead to errors (bugs). The method only checks whether l is less than r, but not how large r and l can be or what their sign is. If r is less than the array size and l is positive, everything is fine. But what happens if r is significantly larger than the array size and l is less than r but also larger than the array size, or if l is negative and r is positive?

[Nguyen_Nguyen_Khoi (Nguyên Nguyễn Khôi)]

Thanks for replying.

As I said, the main function is written by you, and whether it runs correctly or not depends on how you set l and r at the beginning. I feel that you are deliberately not understanding what I am saying. If you want the code to run correctly, you cannot set r or l to be negative or set r beyond the array bounds. That would result in an incorrect solution, and your code will not be accepted.

You have the freedom to write the main function as you see fit, so write it wisely.

Assuming my code is as follows:

cpp

int main(){
    int n;
    cin >> n;
    int* a = new int[n];
    for(int i=0;i<n;++i)
          cin>>a[i];
    quicksort(a, 0, n-1);
}

Assuming that the memory will be sufficient to store the array a and the recursive calls of the quicksort function, provide me with a test case where running the code would cause an error. I will contact my teacher to make adjustments.

[Joe (Schwarz)]

If so, you need to check all the variables mentioned in the calling part. I’m talking about a good generic API (here, quicksort), which usually needs to provide users with basic error-free completeness—i.e., without requiring additional checks.

int partition(int *a, int left, int right) {
    int pivot = a[right];
    int mx = right - left;
    int start = (left - 1);
    for (int j = left; j <= mx; j++) {
        if (a[j] <= pivot) {
            start++;
            swap(a[start], a[j]);
        }
    }
    start++;
    swap(a[start], a[right]);
    return start;
}

void quicksort(int a*, int left, int right) {
    if (left < right && left >= 0 && right < sizeof(a)) {
        int begin = partition(a, left, right);
        quicksort(a, left, begin - 1);
        quicksort(a, begin + 1, right);
    }
}

[Nguyen_Nguyen_Khoi (Nguyên Nguyễn Khôi)]

Thank you for your contribution. I am a first-year university student, so I have not yet learned about APIs or API design principles. My assignment belongs to the DSA (Data Structures and Algorithms) course. I will refer to your code when I study APIs.

[Joe (Schwarz)]

A good developer should always keep two things in mind:
– Clean and optimized code
– As few errors as possible
Reason: Verbose code doesn’t always mean good code. IT is based on hardware (computers). Good code performance is many times better and significantly cheaper than hardware upgrades through tuning.
Good luck!