quicksort algorithm as WIKIPEDIA says in python
<p>In Wikipedia, there is a pseudo-code of quicksort algorithm:</p>

<p>So I tried to implement in python, but it does not sort anything.</p>

<pre><code>def partition(A,lo,hi):
    pivot = A[hi]
    i=lo
    #Swap
    for j in range(lo,len(A)-1):
        if (A[j] &lt;= pivot):
            val=A[i]
            A[i]=A[j]
            A[j]=val
            i=i+1
        val=A[i]
        A[i]=A[hi]
        A[hi]=val
    return(A,i)

def quicksort(A,lo,hi):
     if (lo&lt;hi):
        [A,p]=partition(A,lo,hi)
        quicksort(A,lo,p-1)
        quicksort(A,p+1,hi)

A=[5,3,2,6,8,9,1]
A=quicksort(A, 0, len(A)-1)
print(A)
</code></pre>

<p>ORIGINAL: It does not throw an error so I do not no where I made a mistake.</p>

<p>UPDATE: It now goes into infinite recursion.</p>

<p>It doesn't throw an error or print anything because there is no main program to run anything.  You indented what should be the main program, so that is now part of the <strong>quicksort</strong> function.</p>

<p>Also, this code <em>does</em> throw an error, because you left a comment in what you posted.  I'll clean up the code and edit your posting.</p>

<hr>

<p>I corrected several code errors:</p>

<ol>
<li>Removed "enter code here" text, which caused an obvious compilation error.</li>
<li>Corrected indentation, so that the last three lines are now your main program.</li>
<li>Corrected the main-program call: <strong>quicksort</strong> takes the bounds (subscripts) of the array, but you were passing in the array elements themselves.</li>
</ol>

<p>That fixes your given problem.  You now have infinite recursion due to not handling the return values properly.  Also, your main program destroys the sorted array, since <strong>quicksort</strong> doesn't return anything.  The final print statement will give <strong>None</strong> as its result.</p>

<hr>

<p>You haven't quite implemented the given algorithm.  The most important problem is the <strong>for</strong> loop's upper limit.</p>

<ul>
<li>Python loops do <em>not</em> include the end value.  Your given loop will run <strong>j</strong> through the values <strong>lo</strong> through <strong>len(A)-2</strong>, so you'll never treat the last value of the list.</li>
<li>The upper limit given in Wikipedia is <strong>hi</strong>, not the list end.</li>
</ul>

<p>Fix those, and you'll be close to a solution.</p>

<p>Also, I strongly recommend that you stick in a couple of tracing <strong>print</strong> statements, so you can see follow how the program works.  For instance, as the first statement of each function, print the function name and the input parameters.</p>

<p>Why do you return A from the function?  The Wikipedia algorithm doesn't do that, and it's not necessary: you altered the list in place.</p>

<p>Since you already know about multiple assignment, note that there's an easier way to swap two values:</p>

<pre><code>a, b = b, a
</code></pre>

<p>Does this get you moving through the current problems, enough to get you back on the learning track you want?</p>

python algorithm quicksort wikipedia