Quicksort implementation in Python
up vote
3
down vote
favorite
I have written an implementation of Quicksort in Python. I am new to Python. Any suggestions for improvement or criticism on my use of Python?
def partition(a, lo, hi):
i, j, v = lo+1, hi, a[lo]
while(True):
while(a[i] < v):
i += 1
if (i == hi): break
while(a[j] > v):
j -= 1
if (j == lo): break
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j
def sort(a, lo, hi):
if (hi <= lo):
return
q = partition(a, lo, hi)
sort(a, lo, q-1)
sort(a, q+1, hi)
assert isSorted(a, lo, hi)
def quick_sort(a):
shuffle(a)
sort(a, 0, len(a)-1)
assert isSortedArray(a)
def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True
def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True
python beginner sorting quick-sort
asked Nov 1 '14 at 1:38
khateeb
1435
add a comment |
up vote
3
down vote
favorite
I have written an implementation of Quicksort in Python. I am new to Python. Any suggestions for improvement or criticism on my use of Python?
def partition(a, lo, hi):
i, j, v = lo+1, hi, a[lo]
while(True):
while(a[i] < v):
i += 1
if (i == hi): break
while(a[j] > v):
j -= 1
if (j == lo): break
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j
def sort(a, lo, hi):
if (hi <= lo):
return
q = partition(a, lo, hi)
sort(a, lo, q-1)
sort(a, q+1, hi)
assert isSorted(a, lo, hi)
def quick_sort(a):
shuffle(a)
sort(a, 0, len(a)-1)
assert isSortedArray(a)
def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True
def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True
python beginner sorting quick-sort
asked Nov 1 '14 at 1:38
khateeb
1435
Where areisSortedandisSortedArray?
– jonrsharpe
Nov 1 '14 at 9:01
1
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I have written an implementation of Quicksort in Python. I am new to Python. Any suggestions for improvement or criticism on my use of Python?
def partition(a, lo, hi):
i, j, v = lo+1, hi, a[lo]
while(True):
while(a[i] < v):
i += 1
if (i == hi): break
while(a[j] > v):
j -= 1
if (j == lo): break
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j
def sort(a, lo, hi):
if (hi <= lo):
return
q = partition(a, lo, hi)
sort(a, lo, q-1)
sort(a, q+1, hi)
assert isSorted(a, lo, hi)
def quick_sort(a):
shuffle(a)
sort(a, 0, len(a)-1)
assert isSortedArray(a)
def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True
def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True
python beginner sorting quick-sort
asked Nov 1 '14 at 1:38
khateeb
1435
I have written an implementation of Quicksort in Python. I am new to Python. Any suggestions for improvement or criticism on my use of Python?
def partition(a, lo, hi):
i, j, v = lo+1, hi, a[lo]
while(True):
while(a[i] < v):
i += 1
if (i == hi): break
while(a[j] > v):
j -= 1
if (j == lo): break
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j
def sort(a, lo, hi):
if (hi <= lo):
return
q = partition(a, lo, hi)
sort(a, lo, q-1)
sort(a, q+1, hi)
assert isSorted(a, lo, hi)
def quick_sort(a):
shuffle(a)
sort(a, 0, len(a)-1)
assert isSortedArray(a)
def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True
def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True
python beginner sorting quick-sort
python beginner sorting quick-sort
asked Nov 1 '14 at 1:38
khateeb
1435
asked Nov 1 '14 at 1:38
khateeb
1435
edited Nov 2 '14 at 2:19
asked Nov 1 '14 at 1:38
khateeb
1435
asked Nov 1 '14 at 1:38
khateeb
1435
asked Nov 1 '14 at 1:38
khateeb
1435
1435
Where areisSortedandisSortedArray?
– jonrsharpe
Nov 1 '14 at 9:01
1
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02
add a comment |
Where areisSortedandisSortedArray?
– jonrsharpe
Nov 1 '14 at 9:01
1
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02
Where are
isSorted and isSortedArray?– jonrsharpe
Nov 1 '14 at 9:01
Where are
isSorted and isSortedArray?– jonrsharpe
Nov 1 '14 at 9:01
1
1
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02
add a comment |
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.
You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.
I would prefer to see
while(a[i] < v):
i += 1
if (i == hi): break
… written as
while i < hi and a[i] < pivot:
i += 1
Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.
Some nice properties of inclusive-exclusive ranges are:
hi-logives you the number of elements in the range.- When creating a range for the entire array
a,hiis justlen(a). You save a "-1". - When splitting [
lo,hi) into two consecutive ranges, it becomes [lo,mid) and [mid,hi). You save a "-1". - In Python, you can conveniently write
for i in range(lo, hi)for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
answered Nov 1 '14 at 9:41
200_success
128k15149412
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fcodereview.stackexchange.com%2fquestions%2f68584%2fquicksort-implementation-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.
You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.
I would prefer to see
while(a[i] < v):
i += 1
if (i == hi): break
… written as
while i < hi and a[i] < pivot:
i += 1
Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.
Some nice properties of inclusive-exclusive ranges are:
hi-logives you the number of elements in the range.- When creating a range for the entire array
a,hiis justlen(a). You save a "-1". - When splitting [
lo,hi) into two consecutive ranges, it becomes [lo,mid) and [mid,hi). You save a "-1". - In Python, you can conveniently write
for i in range(lo, hi)for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
answered Nov 1 '14 at 9:41
200_success
128k15149412
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
add a comment |
up vote
5
down vote
accepted
When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.
You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.
I would prefer to see
while(a[i] < v):
i += 1
if (i == hi): break
… written as
while i < hi and a[i] < pivot:
i += 1
Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.
Some nice properties of inclusive-exclusive ranges are:
hi-logives you the number of elements in the range.- When creating a range for the entire array
a,hiis justlen(a). You save a "-1". - When splitting [
lo,hi) into two consecutive ranges, it becomes [lo,mid) and [mid,hi). You save a "-1". - In Python, you can conveniently write
for i in range(lo, hi)for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
answered Nov 1 '14 at 9:41
200_success
128k15149412
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.
You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.
I would prefer to see
while(a[i] < v):
i += 1
if (i == hi): break
… written as
while i < hi and a[i] < pivot:
i += 1
Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.
Some nice properties of inclusive-exclusive ranges are:
hi-logives you the number of elements in the range.- When creating a range for the entire array
a,hiis justlen(a). You save a "-1". - When splitting [
lo,hi) into two consecutive ranges, it becomes [lo,mid) and [mid,hi). You save a "-1". - In Python, you can conveniently write
for i in range(lo, hi)for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
answered Nov 1 '14 at 9:41
200_success
128k15149412
When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.
You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.
I would prefer to see
while(a[i] < v):
i += 1
if (i == hi): break
… written as
while i < hi and a[i] < pivot:
i += 1
Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.
Some nice properties of inclusive-exclusive ranges are:
hi-logives you the number of elements in the range.- When creating a range for the entire array
a,hiis justlen(a). You save a "-1". - When splitting [
lo,hi) into two consecutive ranges, it becomes [lo,mid) and [mid,hi). You save a "-1". - In Python, you can conveniently write
for i in range(lo, hi)for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
answered Nov 1 '14 at 9:41
200_success
128k15149412
edited Nov 1 '14 at 18:40
answered Nov 1 '14 at 9:41
200_success
128k15149412
answered Nov 1 '14 at 9:41
200_success
128k15149412
answered Nov 1 '14 at 9:41
200_success
128k15149412
128k15149412
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
add a comment |
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
@200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot.
– khateeb
Nov 2 '14 at 2:14
1
1
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot.
– 200_success
Nov 2 '14 at 2:26
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
Should my partition function be also inclusive-exclusive range?
– khateeb
Nov 2 '14 at 2:29
1
1
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
Yes, I would recommend consistently using inclusive-exclusive ranges everywhere.
– 200_success
Nov 2 '14 at 2:31
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2fcodereview.stackexchange.com%2fquestions%2f68584%2fquicksort-implementation-in-python%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
Where are
isSortedandisSortedArray?– jonrsharpe
Nov 1 '14 at 9:01
1
@jonrsharpe I don't think that the implementation of those functions is essential to the question.
– 200_success
Nov 1 '14 at 9:19
@jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose.
– khateeb
Nov 2 '14 at 2:02