What is the purpose of these lines of swap code in quicksort application?

committedandroider

I am trying to understand an implementation or an application of quicksort to find the kth smallest element Here is the code that I am trying to understand

public int quicksort(int a[], int start, int end, int k) {
    if(start < end) {
        int pivot = partition(a, start, end);
        if(pivot == k -1) {
            return pivot;
        } else if(pivot > k - 1){
            return quicksort(a, start, pivot, k);
        } else {
            return quicksort(a, pivot + 1, end, k);
        }
    } else if(start == end) {
        return k==1?start:-1;
    } else {
        return -1;
    }
}
public int partition(int a[], int start, int end) {
    int pivot = start;
    int i = pivot + 1;
    int j = end;
    while(a[i] < a[pivot] && i < end) {
        i ++;
    } 
    while(a[j] > a[pivot] && j >= 0) {
        j --;
    } 
    if(i < j) {
        swap(a, start, end);
    }
    swap(a,j, pivot);
    return pivot;
}
private void swap(int a[], int swap1, int swap2) {
    int temp = a[swap1];
    a[swap1] = a[swap2];
    a[swap2] = temp;
}

I understand for trying to find the kth smallest element, you want to use quicksort because elements to the left of pivot will be less than the pivot and elements to the right of the pivot will be greater than. So that way if you're trying to find the 4th smallest element, and the pivot is at index 3, you can just return it because you know it is the 4th smallest since there are 3 elements smaller than it.

I am having trouble understanding the two swaps in the partition method.

At the conclusion of the first while loop, index i will be at a position at which all elements less than the pivot will be to the left of i. Index j will be at a position at which all elements greater than the pivot will be to the right of j.

What is the purpose of this swap code inside partition? Can anyone give an example of why this of code is necessary? How will these ever meet?

if(i < j) {
        swap(a, i, j);
}

And also for this swap line(also inside partition), why did the author swap pivot and j, and not pivot and i? Is it arbitrary?

        swap(a,j, pivot);
Nishant Lakhara

You can use the partition algorithm present at : Quick sort partition algorithm

The algorithm you are using returns incorrect pivot

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

What is the purpose of each of these code lines?

What is the purpose of multiple swap files

What's the purpose of const swap() function?

What is the purpose of this code

What is the purpose this code "SomeString" & ""=""

What is the purpose of this code in below?

What is the purpose of this JavaScript code?

What is the purpose of .enumerated() and .map() in this code?

what is the purpose of Specific line in the Code

What is the purpose of authorization code in OAuth

What is the purpose of "Sections" in Octave code?

what is the the purpose of using ? and : in the following code

What is the purpose of 'turn' in this line of code?

What is the purpose of the nested promise in this code?

Swap method for quicksort in java

What are these lines of batch code for?

What is with the %'s in these lines of code

What is the purpose of having multiple spring "application context"

What is the purpose of using both Application Service and Manager?

What is the purpose of this code? Is it just duplicating a Date?

What is the purpose of the function (toEnum . fromEnum) in Haskell code?

What is the purpose of the Linux home partition code 8302?

What is the purpose of adding content:' ' in the following code?

What is the purpose of code optimization at intermediate phase in compiler?

What is the purpose of ADD BX,2 in this code?

What is the purpose of sll and add in the translated MIPS code?

What is the purpose of yearmonth() and as_tsibble() in this code?

What purpose is the lookup table serving in this code?

What is the purpose of the y parameter in this Haskell code