Quicksort in python [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

The below written code for quicksort is not sorting a list properly. There must be some logical flaw in the code. Can anybody please review the code?

def quicksort(aList, start, last):
    i = start + 1
    j = start + 1
    pivot = aList[start]
    while j <= last and pivot > aList[j]:
        if pivot > aList[j]:
            temp = aList[i]
            aList[i] = aList[j]
            aList[j] = temp
            i = i + 1
        j = j + 1

    temp = aList[start]
    aList[start] = aList[i-1]
    aList[i-1] = temp
    if i - start > 2:
        quicksort(aList, start, i-2)
    if last - i > 0:
        quicksort(aList, i, last)


aList = [2, 5, 3, 95, 68, 75, 29, 52]
quicksort(aList, 0, len(aList)-1)
print aList

Answer 1

def quicksort(aList, start, last):
  i = start + 1
  j = start + 1
  pivot = aList[start]
  while j <= last:
    if pivot > aList[j]:
      temp = aList[i]
      aList[i] = aList[j]
      aList[j] = temp
      i = i + 1
    j = j + 1

  temp = aList[start]
  aList[start] = aList[i-1]
  aList[i-1] = temp
  if i - start > 2:
    quicksort(aList, start, i-2)
  if last - i > 0:
    quicksort(aList, i, last)

try this!

yopy have given another version of quick sort.

the key of quick sort is the choose of pivot, in your code the pivot is the first element of array, to get a better average performance, you can choose pivot by random.

Answer 2

Please check this:

def quicksort(aList, start, last):
    i = start + 1
    j = last
    pivot = aList[start]
    while i <= j:
        if pivot > aList[j]:
            aList[i], aList[j] = aList[j], aList[i]
            i = i + 1
        elif pivot < aList[j]:
            j = j - 1

    aList[start], aList[i-1] = aList[i-1], aList[start]

    if i - start > 2:
        quicksort(aList, start, i-2)
    if last - i > 0:
        quicksort(aList, i, last)


aList = [2, 5, 3, 95, 68, 75, 29, 52]
quicksort(aList, 0, len(aList)-1)
print aList

Output:

[2, 3, 5, 29, 52, 68, 75, 95]