Quick select partitioning
up vote
0
down vote
favorite
I am trying to understand how QuickSelect partitioning works, and there are a few things I don't get, I will try to explain how I see it (please notice that I have renamed the variables and made my comments to try to understand it, so maybe some renaming or commenting is wrong):
- First, the value of the pivot is the value of the index the pivot is at, that makes sense.
- We now swap the pivot to the end of the Array, why?
- We have a first pointer which starts at left, because the first pointer should of course start at the start.
- In the for loop we have a second pointer, which also starts at left, why?. Shouldn't it start at the other end?
- If where we are at is less than the pivot value, swap them, so we get the lesser elements to the left.
- At the end swap the pivot back (this leads to my fist "why").
- At the end we return the first pointer, which I assume is because that is the only element left in the Array?
I have seen different kinds of implementations, and I have found that most if not all do this.
// Partitioning.
private static int quickSelectPartition(int array, int left, int right, int pivotIndex)
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++)
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue)
// Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
java algorithm big-o quicksort quickselect
add a comment |
up vote
0
down vote
favorite
I am trying to understand how QuickSelect partitioning works, and there are a few things I don't get, I will try to explain how I see it (please notice that I have renamed the variables and made my comments to try to understand it, so maybe some renaming or commenting is wrong):
- First, the value of the pivot is the value of the index the pivot is at, that makes sense.
- We now swap the pivot to the end of the Array, why?
- We have a first pointer which starts at left, because the first pointer should of course start at the start.
- In the for loop we have a second pointer, which also starts at left, why?. Shouldn't it start at the other end?
- If where we are at is less than the pivot value, swap them, so we get the lesser elements to the left.
- At the end swap the pivot back (this leads to my fist "why").
- At the end we return the first pointer, which I assume is because that is the only element left in the Array?
I have seen different kinds of implementations, and I have found that most if not all do this.
// Partitioning.
private static int quickSelectPartition(int array, int left, int right, int pivotIndex)
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++)
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue)
// Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
java algorithm big-o quicksort quickselect
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am trying to understand how QuickSelect partitioning works, and there are a few things I don't get, I will try to explain how I see it (please notice that I have renamed the variables and made my comments to try to understand it, so maybe some renaming or commenting is wrong):
- First, the value of the pivot is the value of the index the pivot is at, that makes sense.
- We now swap the pivot to the end of the Array, why?
- We have a first pointer which starts at left, because the first pointer should of course start at the start.
- In the for loop we have a second pointer, which also starts at left, why?. Shouldn't it start at the other end?
- If where we are at is less than the pivot value, swap them, so we get the lesser elements to the left.
- At the end swap the pivot back (this leads to my fist "why").
- At the end we return the first pointer, which I assume is because that is the only element left in the Array?
I have seen different kinds of implementations, and I have found that most if not all do this.
// Partitioning.
private static int quickSelectPartition(int array, int left, int right, int pivotIndex)
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++)
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue)
// Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
java algorithm big-o quicksort quickselect
I am trying to understand how QuickSelect partitioning works, and there are a few things I don't get, I will try to explain how I see it (please notice that I have renamed the variables and made my comments to try to understand it, so maybe some renaming or commenting is wrong):
- First, the value of the pivot is the value of the index the pivot is at, that makes sense.
- We now swap the pivot to the end of the Array, why?
- We have a first pointer which starts at left, because the first pointer should of course start at the start.
- In the for loop we have a second pointer, which also starts at left, why?. Shouldn't it start at the other end?
- If where we are at is less than the pivot value, swap them, so we get the lesser elements to the left.
- At the end swap the pivot back (this leads to my fist "why").
- At the end we return the first pointer, which I assume is because that is the only element left in the Array?
I have seen different kinds of implementations, and I have found that most if not all do this.
// Partitioning.
private static int quickSelectPartition(int array, int left, int right, int pivotIndex)
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++)
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue)
// Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
java algorithm big-o quicksort quickselect
java algorithm big-o quicksort quickselect
asked Nov 10 at 19:24
user7722505
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
It's all about the contracts. The contract for quickSelectPartition
, if it existed, would say something like "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".
Swapping the pivot to the end and then back to firstPointer
is how this function connects its contract to the loop invariant: "the elements at indexes left..firstPointer-1
are less than the pivot; the elements at indexes firstPointer..secondPointer-1
are greater than or equal to the pivot". When secondPointer
is left
, this invariant trivially holds; the goal of the loop is to increase secondPointer
to right
while preserving the invariant. We could keep the pivot in the middle of these arrays, but to answer all of your questions, it's more efficient not to have the pivot be constantly moving to follow secondPointer
.
There are certainly other ways to handle partitioning, so the meta-answer to your whys is that this is the way the code author decided to do it.
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
It's all about the contracts. The contract for quickSelectPartition
, if it existed, would say something like "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".
Swapping the pivot to the end and then back to firstPointer
is how this function connects its contract to the loop invariant: "the elements at indexes left..firstPointer-1
are less than the pivot; the elements at indexes firstPointer..secondPointer-1
are greater than or equal to the pivot". When secondPointer
is left
, this invariant trivially holds; the goal of the loop is to increase secondPointer
to right
while preserving the invariant. We could keep the pivot in the middle of these arrays, but to answer all of your questions, it's more efficient not to have the pivot be constantly moving to follow secondPointer
.
There are certainly other ways to handle partitioning, so the meta-answer to your whys is that this is the way the code author decided to do it.
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
add a comment |
up vote
0
down vote
accepted
It's all about the contracts. The contract for quickSelectPartition
, if it existed, would say something like "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".
Swapping the pivot to the end and then back to firstPointer
is how this function connects its contract to the loop invariant: "the elements at indexes left..firstPointer-1
are less than the pivot; the elements at indexes firstPointer..secondPointer-1
are greater than or equal to the pivot". When secondPointer
is left
, this invariant trivially holds; the goal of the loop is to increase secondPointer
to right
while preserving the invariant. We could keep the pivot in the middle of these arrays, but to answer all of your questions, it's more efficient not to have the pivot be constantly moving to follow secondPointer
.
There are certainly other ways to handle partitioning, so the meta-answer to your whys is that this is the way the code author decided to do it.
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
It's all about the contracts. The contract for quickSelectPartition
, if it existed, would say something like "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".
Swapping the pivot to the end and then back to firstPointer
is how this function connects its contract to the loop invariant: "the elements at indexes left..firstPointer-1
are less than the pivot; the elements at indexes firstPointer..secondPointer-1
are greater than or equal to the pivot". When secondPointer
is left
, this invariant trivially holds; the goal of the loop is to increase secondPointer
to right
while preserving the invariant. We could keep the pivot in the middle of these arrays, but to answer all of your questions, it's more efficient not to have the pivot be constantly moving to follow secondPointer
.
There are certainly other ways to handle partitioning, so the meta-answer to your whys is that this is the way the code author decided to do it.
It's all about the contracts. The contract for quickSelectPartition
, if it existed, would say something like "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".
Swapping the pivot to the end and then back to firstPointer
is how this function connects its contract to the loop invariant: "the elements at indexes left..firstPointer-1
are less than the pivot; the elements at indexes firstPointer..secondPointer-1
are greater than or equal to the pivot". When secondPointer
is left
, this invariant trivially holds; the goal of the loop is to increase secondPointer
to right
while preserving the invariant. We could keep the pivot in the middle of these arrays, but to answer all of your questions, it's more efficient not to have the pivot be constantly moving to follow secondPointer
.
There are certainly other ways to handle partitioning, so the meta-answer to your whys is that this is the way the code author decided to do it.
answered Nov 10 at 19:40
David Eisenstat
36.5k73372
36.5k73372
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
add a comment |
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
I see. So we move the pivot out of the way for simplicity. So essentially it is made up of four parts, left, firstP, secondP, and right. The left itself which is the start of the array. The first pointer which increments away from left, and all values between left and first pointer are less than pivot. We then have second pointer that moves towards right, and all values between first and second pointer are greater than pivot. At the end we move pivot back between the end of the first and second pointers. Is this correct?
– user7722505
Nov 10 at 19:47
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
@mth1417 Yes, that's right.
– David Eisenstat
Nov 10 at 19:50
Thank you I get it now.
– user7722505
Nov 10 at 19:51
Thank you I get it now.
– user7722505
Nov 10 at 19:51
add a comment |
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53242614%2fquick-select-partitioning%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown