Understanding Quick Sort Partition Definitions

We are currently running ALDS1_6_B.

The answer codes are as follows:

I don't understand the meaning of inti=p-1 used in the partition.
Why is i doing p-1? Why is p-1 defined?

Also, I think x is used as a threshold to compare x in the for statement, and x is separated from x or higher.
Why can I group large and small by using i?
I look forward to your kind cooperation.

answer codes:

#include<stdio.h>
# include <algorithm>

using namespace std;

int partition(int A[], int p, int r){
    int x = A[r];
    inti = p-1;
    for(int j=p;j<r;j++){
        if(A[j]<=x){
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}

int main() {
    int n, partition_point;
    scanf("%d", & n);
    int A[n];
    for(inti=0;i<n;i++)scanf("%d", & A[i]);

    partition_point = partition(A,0,n-1);

    for(inti=0;i<n-1;i++){
        if(i==partition_point){
            printf("[%d]", A[i]);
        } else {
            printf("%d", A[i]);
        }
    }
    if(partition_point==n-1){
        printf("[%d]\n", A[n-1]);
    } else {
        printf("%d\n", A[n-1]);
    }
}

algorithm data-structure

2022-12-01 23:06

1 Answers

I don't know where to start... Do you know the quicksort algorithm?

You choose one element in the array you want to sort out as a tekito to determine if it is larger or smaller than that, which is called a pivot.If you gather elements smaller than the pivot to the left and elements larger than the pivot to the right, you can put them in the center.You can sort all the elements by changing the split interval and recursively repeating it.

Based on the above,

Example partition() is a quicksort replacement of elements A[p] to A[r] in the array
In this example, intx=A[r]; is the pivot, or the final element is the pivot.
forInternal swap(A[i], A[j]); collects elements smaller than the pivot to the left
Actually, by "replacing" rather than "collecting" the elements larger than the pivot, it also serves as a right-hand collection process.
for outside swap(A[i+1], A[r]); is the "center pivot" process

That's it.

i is the next insertion (=replacement) position for elements smaller than the pivot. It is not based on i.Since +1 is done just before insertion, the initial value should be p-1, and the source code may not be intuitive.

2022-12-02 02:53

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656