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









share|improve this question
























  • Where are isSorted and isSortedArray?
    – 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















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









share|improve this question
























  • Where are isSorted and isSortedArray?
    – 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













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









share|improve this question















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 2 '14 at 2:19

























asked Nov 1 '14 at 1:38









khateeb

1435




1435












  • Where are isSorted and isSortedArray?
    – 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






  • 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










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 - lo gives you the number of elements in the range.

  • When creating a range for the entire array a, hi is just len(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.)






share|improve this answer























  • @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











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
});


}
});














draft saved

draft discarded


















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 - lo gives you the number of elements in the range.

  • When creating a range for the entire array a, hi is just len(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.)






share|improve this answer























  • @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















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 - lo gives you the number of elements in the range.

  • When creating a range for the entire array a, hi is just len(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.)






share|improve this answer























  • @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













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 - lo gives you the number of elements in the range.

  • When creating a range for the entire array a, hi is just len(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.)






share|improve this answer














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 - lo gives you the number of elements in the range.

  • When creating a range for the entire array a, hi is just len(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.)







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 1 '14 at 18:40

























answered Nov 1 '14 at 9:41









200_success

127k15149412




127k15149412












  • @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






  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei