07-10-2020, 10:04 AM
Python One Line Quicksort
<div><p>In this one-liner tutorial, you’ll learn about the popular sorting algorithm <a href="https://en.wikipedia.org/wiki/Quicksort">Quicksort</a>. Surprisingly, a single line of Python code is all you need to write the Quicksort algorithm!</p>
<figure class="wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio">
<div class="wp-block-embed__wrapper">
<div class="ast-oembed-container"><iframe title="Python Quicksort One-Liner" width="1400" height="788" src="https://www.youtube.com/embed/TBzFEKswnDQ?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe></div>
</div>
</figure>
<p><strong>Problem</strong>: Given a list of numerical values (integer or float). Sort the list in a single line of Python code using the popular <a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank" rel="noreferrer noopener" title="https://en.wikipedia.org/wiki/Quicksort">Quicksort </a>algorithm!</p>
<p><strong>Example</strong>: You have list <code>[4, 2, 1, 42, 3]</code>. You want to sort the list in ascending order to obtain the new list <code>[1, 2, 3, 4, 42]</code>. </p>
<p><strong>Short answer</strong>: The following one-liner solution sorts the list recursively using the Quicksort algorithm: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else []</pre>
<p>You can try it yourself using the following interactive code shell:</p>
<p> <iframe src="https://trinket.io/embed/python/82f77b2571" marginwidth="0" marginheight="0" allowfullscreen="" width="100%" height="356" frameborder="0"></iframe> </p>
<p>Now, let’s dive into some details!</p>
<h2>A Conceptual Introduction</h2>
<p>The following introduction is based on my new book <a href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank" rel="noreferrer noopener" title="https://www.amazon.com/gp/product/B07ZY7XMX8"><strong>“Python One-Liners”</strong></a> <em>(Amazon Link)</em> that teaches you the power of the single line of code (use it wisely)!</p>
<figure class="wp-block-image size-medium is-resized"><a href="https://www.amazon.com/gp/product/B07ZY7XMX8"><img src="https://blog.finxter.com/wp-content/uploads/2020/06/3D_cover-1024x944.jpg" alt="Python One-Liners" class="wp-image-10007" width="256" height="236" srcset="https://blog.finxter.com/wp-content/uploads/2020/06/3D_cover-scaled.jpg 1024w, https://blog.finxter.com/wp-content/uplo...00x277.jpg 300w, https://blog.finxter.com/wp-content/uplo...68x708.jpg 768w" sizes="(max-width: 256px) 100vw, 256px" /></a></figure>
<p><strong>Introduction</strong>: <a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" title="The Shortest Quicksort Implementation in Python" target="_blank" rel="noreferrer noopener">Quicksort </a>is not only a popular question in many <a href="https://blog.finxter.com/python-interview-questions/" title="They Use These 15+ Python Interview Questions To Fail You … (And What You Can Do About It)" target="_blank" rel="noreferrer noopener">code interviews</a> – asked by Google, Facebook, and Amazon – but also a practical <a href="https://blog.finxter.com/python-list-sort/" title="Python List sort() – The Ultimate Guide" target="_blank" rel="noreferrer noopener">sorting </a>algorithm that is fast, concise, and readable. Because of its beauty, you won’t find many introduction to algorithm classes which don’t discuss the Quicksort algorithm.</p>
<p><strong>Overview</strong>: Quicksort sorts a list by <a href="https://blog.finxter.com/recursion/" title="Recursion: A Helpful Guide in Python" target="_blank" rel="noreferrer noopener">recursively </a>dividing the big problem (sorting the list) into smaller problems (sorting two smaller lists) and combining the solutions from the smaller problems in a way that it solves the big problem. In order to solve each smaller problem, the same strategy is used recursively: the smaller problems are divided into even smaller subproblems, solved separately, and combined. Because of this strategy, Quicksort belongs to the class of “Divide and Conquer” algorithms.</p>
<p><strong>Algorithm</strong>: The main idea of Quicksort is to select a pivot element and then placing all elements that are larger or equal than the pivot element to the right and all elements that are smaller than the pivot element to the left. Now, you have divided the big problem of sorting the list into two smaller subproblems: sorting the right and the left partition of the list. What you do now is to repeat this procedure recursively until you obtain a list with zero elements. This list is already sorted, so the recursion terminates. </p>
<p>The following Figure shows the Quicksort algorithm in action:</p>
<figure class="wp-block-image"><img src="https://blog.finxter.com/wp-content/uploads/2019/06/image-11.png" alt="" class="wp-image-3689" srcset="https://blog.finxter.com/wp-content/uploads/2019/06/image-11.png 604w, https://blog.finxter.com/wp-content/uplo...00x169.png 300w, https://blog.finxter.com/wp-content/uplo...100x56.png 100w" sizes="(max-width: 604px) 100vw, 604px" /></figure>
<p><strong><em>Figure: The Quicksort algorithm selects a pivot element, splits up the list into (i) an unsorted sublist with all elements that are smaller or equal than the pivot, and (ii) an unsorted sublist with all elements that are larger than the pivot. Next, the Quicksort algorithm is called recursively on the two unsorted sublists to sort them. As soon as the sublists contain maximally one element, they are sorted by definition – the recursion ends. At every recursion level, the three sublists (left, pivot, right) are concatenated before the resulting list is handed to the higher recursion level.</em></strong></p>
<p>This brings us to the following code:</p>
<h2>Python One-Liner Quicksort [Code]</h2>
<p><em>Create a function <code>q</code> which implements the Quicksort algorithm in a single line of Python code – and thus sorts any argument given as a list of integers.</em></p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">## The Data
unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner
q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result
print(q(unsorted))</pre>
<p><strong><em>Listing: One-liner solution for the Quicksort algorithm using recursion.</em></strong></p>
<p>What is the output of this code? Let’s see…</p>
<h2>Explanation Quicksort One-Liner</h2>
<p>We have already discussed the recursive Quicksort algorithm above. The one-liner resembles exactly the discussed algorithm. First, we create a new <a href="https://blog.finxter.com/a-simple-introduction-of-the-lambda-function-in-python/" title="Lambda Functions in Python: A Simple Introduction" target="_blank" rel="noreferrer noopener">lambda function</a> q which takes only one list argument <code>l</code>. </p>
<p>The lambda function has the following structure:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">lambda l: q(left) + pivot + q(right) if l else []</pre>
<p>The lambda function returns the empty list <code>[]</code> in the recursion base case (that is – the list to be sorted is empty and, therefore, trivially sorted). </p>
<p>In any other case, it selects the pivot element as the first element of list <code>l</code>, divides all elements into two <a href="https://blog.finxter.com/introduction-to-slicing-in-python/" title="Introduction to Slicing in Python" target="_blank" rel="noreferrer noopener">sublists </a>(left and right) based on whether they are smaller or larger than the pivot. To achieve this, we use simple <a href="https://blog.finxter.com/list-comprehension/" title="List Comprehension in Python — A Helpful Illustrated Guide" target="_blank" rel="noreferrer noopener">list comprehension</a>. </p>
<p>As the two sublists are not necessarily sorted, we recursively execute the Quicksort algorithm on them. Finally, we <a href="https://blog.finxter.com/concatenate-lists-in-python/" target="_blank" rel="noreferrer noopener" title="How to Concatenate Lists in Python? [Interactive Guide]">combine </a>all three lists and return the sorted list. Therefore, the result is:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">## The Result
print(q(unsorted))
# [2, 3, 6, 33, 33, 45, 54]</pre>
<p><strong>Related</strong>: For an interactive experience of what you’ve just learned, check out our Instagram post about the Quicksort algorithm:</p>
<blockquote class="instagram-media" data-instgrm-permalink="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" data-instgrm-version="12" style=" background:#FFF; border:0; border-radius:3px; box-shadow:0 0 1px 0 rgba(0,0,0,0.5),0 1px 10px 0 rgba(0,0,0,0.15); margin: 1px; max-width:540px; min-width:326px; padding:0; width:99.375%; width:-webkit-calc(100% - 2px); width:calc(100% - 2px);">
<div style="padding:16px;"> <a href="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" style=" background:#FFFFFF; line-height:0; padding:0 0; text-align:center; text-decoration:none; width:100%;" target="_blank" rel="noopener noreferrer"> </p>
<div style=" display: flex; flex-direction: row; align-items: center;">
<div style="background-color: #F4F4F4; border-radius: 50%; flex-grow: 0; height: 40px; margin-right: 14px; width: 40px;"></div>
<div style="display: flex; flex-direction: column; flex-grow: 1; justify-content: center;">
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; margin-bottom: 6px; width: 100px;"></div>
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; width: 60px;"></div>
</div>
</div>
<div style="padding: 19% 0;"></div>
<div style="display:block; height:50px; margin:0 auto 12px; width:50px;"><svg width="50px" height="50px" viewBox="0 0 60 60" version="1.1" xmlns="https://www.w3.org/2000/svg" xmlns:xlink="https://www.w3.org/1999/xlink"><g stroke="none" stroke-width="1" fill="none" fill-rule="evenodd"><g transform="translate(-511.000000, -20.000000)" fill="#000000"><g><path d="M556.869,30.41 C554.814,30.41 553.148,32.076 553.148,34.131 C553.148,36.186 554.814,37.852 556.869,37.852 C558.924,37.852 560.59,36.186 560.59,34.131 C560.59,32.076 558.924,30.41 556.869,30.41 M541,60.657 C535.114,60.657 530.342,55.887 530.342,50 C530.342,44.114 535.114,39.342 541,39.342 C546.887,39.342 551.658,44.114 551.658,50 C551.658,55.887 546.887,60.657 541,60.657 M541,33.886 C532.1,33.886 524.886,41.1 524.886,50 C524.886,58.899 532.1,66.113 541,66.113 C549.9,66.113 557.115,58.899 557.115,50 C557.115,41.1 549.9,33.886 541,33.886 M565.378,62.101 C565.244,65.022 564.756,66.606 564.346,67.663 C563.803,69.06 563.154,70.057 562.106,71.106 C561.058,72.155 560.06,72.803 558.662,73.347 C557.607,73.757 556.021,74.244 553.102,74.378 C549.944,74.521 548.997,74.552 541,74.552 C533.003,74.552 532.056,74.521 528.898,74.378 C525.979,74.244 524.393,73.757 523.338,73.347 C521.94,72.803 520.942,72.155 519.894,71.106 C518.846,70.057 518.197,69.06 517.654,67.663 C517.244,66.606 516.755,65.022 516.623,62.101 C516.479,58.943 516.448,57.996 516.448,50 C516.448,42.003 516.479,41.056 516.623,37.899 C516.755,34.978 517.244,33.391 517.654,32.338 C518.197,30.938 518.846,29.942 519.894,28.894 C520.942,27.846 521.94,27.196 523.338,26.654 C524.393,26.244 525.979,25.756 528.898,25.623 C532.057,25.479 533.004,25.448 541,25.448 C548.997,25.448 549.943,25.479 553.102,25.623 C556.021,25.756 557.607,26.244 558.662,26.654 C560.06,27.196 561.058,27.846 562.106,28.894 C563.154,29.942 563.803,30.938 564.346,32.338 C564.756,33.391 565.244,34.978 565.378,37.899 C565.522,41.056 565.552,42.003 565.552,50 C565.552,57.996 565.522,58.943 565.378,62.101 M570.82,37.631 C570.674,34.438 570.167,32.258 569.425,30.349 C568.659,28.377 567.633,26.702 565.965,25.035 C564.297,23.368 562.623,22.342 560.652,21.575 C558.743,20.834 556.562,20.326 553.369,20.18 C550.169,20.033 549.148,20 541,20 C532.853,20 531.831,20.033 528.631,20.18 C525.438,20.326 523.257,20.834 521.349,21.575 C519.376,22.342 517.703,23.368 516.035,25.035 C514.368,26.702 513.342,28.377 512.574,30.349 C511.834,32.258 511.326,34.438 511.181,37.631 C511.035,40.831 511,41.851 511,50 C511,58.147 511.035,59.17 511.181,62.369 C511.326,65.562 511.834,67.743 512.574,69.651 C513.342,71.625 514.368,73.296 516.035,74.965 C517.703,76.634 519.376,77.658 521.349,78.425 C523.257,79.167 525.438,79.673 528.631,79.82 C531.831,79.965 532.853,80.001 541,80.001 C549.148,80.001 550.169,79.965 553.369,79.82 C556.562,79.673 558.743,79.167 560.652,78.425 C562.623,77.658 564.297,76.634 565.965,74.965 C567.633,73.296 568.659,71.625 569.425,69.651 C570.167,67.743 570.674,65.562 570.82,62.369 C570.966,59.17 571,58.147 571,50 C571,41.851 570.966,40.831 570.82,37.631"></path></g></g></g></svg></div>
<div style="padding-top: 8px;">
<div style=" color:#3897f0; font-family:Arial,sans-serif; font-size:14px; font-style:normal; font-weight:550; line-height:18px;"> Sieh dir diesen Beitrag auf Instagram an</div>
</div>
<div style="padding: 12.5% 0;"></div>
<div style="display: flex; flex-direction: row; margin-bottom: 14px; align-items: center;">
<div>
<div style="background-color: #F4F4F4; border-radius: 50%; height: 12.5px; width: 12.5px; transform: translateX(0px) translateY(7px);"></div>
<div style="background-color: #F4F4F4; height: 12.5px; transform: rotate(-45deg) translateX(3px) translateY(1px); width: 12.5px; flex-grow: 0; margin-right: 14px; margin-left: 2px;"></div>
<div style="background-color: #F4F4F4; border-radius: 50%; height: 12.5px; width: 12.5px; transform: translateX(9px) translateY(-18px);"></div>
</div>
<div style="margin-left: 8px;">
<div style=" background-color: #F4F4F4; border-radius: 50%; flex-grow: 0; height: 20px; width: 20px;"></div>
<div style=" width: 0; height: 0; border-top: 2px solid transparent; border-left: 6px solid #f4f4f4; border-bottom: 2px solid transparent; transform: translateX(16px) translateY(-4px) rotate(30deg)"></div>
</div>
<div style="margin-left: auto;">
<div style=" width: 0px; border-top: 8px solid #F4F4F4; border-right: 8px solid transparent; transform: translateY(16px);"></div>
<div style=" background-color: #F4F4F4; flex-grow: 0; height: 12px; width: 16px; transform: translateY(-4px);"></div>
<div style=" width: 0; height: 0; border-top: 8px solid #F4F4F4; border-left: 8px solid transparent; transform: translateY(-4px) translateX(8px);"></div>
</div>
</div>
<div style="display: flex; flex-direction: column; flex-grow: 1; justify-content: center; margin-bottom: 24px;">
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; margin-bottom: 6px; width: 224px;"></div>
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; width: 144px;"></div>
</div>
<p></a></p>
<p style=" color:#c9c8cd; font-family:Arial,sans-serif; font-size:14px; line-height:17px; margin-bottom:0; margin-top:8px; overflow:hidden; padding:8px 0 7px; text-align:center; text-overflow:ellipsis; white-space:nowrap;"><a href="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" style=" color:#c9c8cd; font-family:Arial,sans-serif; font-size:14px; font-style:normal; font-weight:normal; line-height:17px; text-decoration:none;" target="_blank" rel="noopener noreferrer">Ein Beitrag geteilt von The Python Blog (@finxter.com_)</a> am <time style=" font-family:Arial,sans-serif; font-size:14px; line-height:17px;" datetime="2019-10-31T17:18:06+00:00">Okt 31, 2019 um 10:18 PDT</time></p>
</div>
</blockquote>
<p> <script async="" src="//www.instagram.com/embed.js"></script> </p>
<p><strong>Related Resources</strong>: </p>
<ul>
<li><a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" target="_blank" rel="noreferrer noopener" title="The Shortest Quicksort Implementation in Python">The Shortest Quicksort Implementation</a></li>
<li><a href="https://blog.finxter.com/python-one-line-x/" target="_blank" rel="noreferrer noopener">Python One Line X</a></li>
<li><a href="https://pythononeliners.com/" target="_blank" rel="noreferrer noopener">Pythononeliners.com</a></li>
<li><a href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank" rel="noreferrer noopener">Book <em>“Python One-Liners”</em> (Amazon Link)</a></li>
<li><a href="https://blog.finxter.com/python-one-line-for-loop-a-simple-tutorial/" target="_blank" rel="noreferrer noopener">Python One Line For Loop</a></li>
<li><a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" target="_blank" rel="noreferrer noopener">Python Quicksort One Line</a></li>
</ul>
<h2>Where to Go From Here?</h2>
<p>Enough theory, let’s get some practice!</p>
<p>To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?</p>
<p><strong>Practice projects is how you sharpen your saw in coding!</strong></p>
<p>Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?</p>
<p>Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.</p>
<p>Join my free webinar <a rel="noreferrer noopener" href="https://blog.finxter.com/webinar-freelancer/" target="_blank">“How to Build Your High-Income Skill Python”</a> and watch how I grew my coding business online and how you can, too—from the comfort of your own home.</p>
<p><a href="https://blog.finxter.com/webinar-freelancer/" target="_blank" rel="noreferrer noopener">Join the free webinar now!</a></p>
</div>
https://www.sickgaming.net/blog/2020/07/...quicksort/
<div><p>In this one-liner tutorial, you’ll learn about the popular sorting algorithm <a href="https://en.wikipedia.org/wiki/Quicksort">Quicksort</a>. Surprisingly, a single line of Python code is all you need to write the Quicksort algorithm!</p>
<figure class="wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio">
<div class="wp-block-embed__wrapper">
<div class="ast-oembed-container"><iframe title="Python Quicksort One-Liner" width="1400" height="788" src="https://www.youtube.com/embed/TBzFEKswnDQ?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe></div>
</div>
</figure>
<p><strong>Problem</strong>: Given a list of numerical values (integer or float). Sort the list in a single line of Python code using the popular <a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank" rel="noreferrer noopener" title="https://en.wikipedia.org/wiki/Quicksort">Quicksort </a>algorithm!</p>
<p><strong>Example</strong>: You have list <code>[4, 2, 1, 42, 3]</code>. You want to sort the list in ascending order to obtain the new list <code>[1, 2, 3, 4, 42]</code>. </p>
<p><strong>Short answer</strong>: The following one-liner solution sorts the list recursively using the Quicksort algorithm: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else []</pre>
<p>You can try it yourself using the following interactive code shell:</p>
<p> <iframe src="https://trinket.io/embed/python/82f77b2571" marginwidth="0" marginheight="0" allowfullscreen="" width="100%" height="356" frameborder="0"></iframe> </p>
<p>Now, let’s dive into some details!</p>
<h2>A Conceptual Introduction</h2>
<p>The following introduction is based on my new book <a href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank" rel="noreferrer noopener" title="https://www.amazon.com/gp/product/B07ZY7XMX8"><strong>“Python One-Liners”</strong></a> <em>(Amazon Link)</em> that teaches you the power of the single line of code (use it wisely)!</p>
<figure class="wp-block-image size-medium is-resized"><a href="https://www.amazon.com/gp/product/B07ZY7XMX8"><img src="https://blog.finxter.com/wp-content/uploads/2020/06/3D_cover-1024x944.jpg" alt="Python One-Liners" class="wp-image-10007" width="256" height="236" srcset="https://blog.finxter.com/wp-content/uploads/2020/06/3D_cover-scaled.jpg 1024w, https://blog.finxter.com/wp-content/uplo...00x277.jpg 300w, https://blog.finxter.com/wp-content/uplo...68x708.jpg 768w" sizes="(max-width: 256px) 100vw, 256px" /></a></figure>
<p><strong>Introduction</strong>: <a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" title="The Shortest Quicksort Implementation in Python" target="_blank" rel="noreferrer noopener">Quicksort </a>is not only a popular question in many <a href="https://blog.finxter.com/python-interview-questions/" title="They Use These 15+ Python Interview Questions To Fail You … (And What You Can Do About It)" target="_blank" rel="noreferrer noopener">code interviews</a> – asked by Google, Facebook, and Amazon – but also a practical <a href="https://blog.finxter.com/python-list-sort/" title="Python List sort() – The Ultimate Guide" target="_blank" rel="noreferrer noopener">sorting </a>algorithm that is fast, concise, and readable. Because of its beauty, you won’t find many introduction to algorithm classes which don’t discuss the Quicksort algorithm.</p>
<p><strong>Overview</strong>: Quicksort sorts a list by <a href="https://blog.finxter.com/recursion/" title="Recursion: A Helpful Guide in Python" target="_blank" rel="noreferrer noopener">recursively </a>dividing the big problem (sorting the list) into smaller problems (sorting two smaller lists) and combining the solutions from the smaller problems in a way that it solves the big problem. In order to solve each smaller problem, the same strategy is used recursively: the smaller problems are divided into even smaller subproblems, solved separately, and combined. Because of this strategy, Quicksort belongs to the class of “Divide and Conquer” algorithms.</p>
<p><strong>Algorithm</strong>: The main idea of Quicksort is to select a pivot element and then placing all elements that are larger or equal than the pivot element to the right and all elements that are smaller than the pivot element to the left. Now, you have divided the big problem of sorting the list into two smaller subproblems: sorting the right and the left partition of the list. What you do now is to repeat this procedure recursively until you obtain a list with zero elements. This list is already sorted, so the recursion terminates. </p>
<p>The following Figure shows the Quicksort algorithm in action:</p>
<figure class="wp-block-image"><img src="https://blog.finxter.com/wp-content/uploads/2019/06/image-11.png" alt="" class="wp-image-3689" srcset="https://blog.finxter.com/wp-content/uploads/2019/06/image-11.png 604w, https://blog.finxter.com/wp-content/uplo...00x169.png 300w, https://blog.finxter.com/wp-content/uplo...100x56.png 100w" sizes="(max-width: 604px) 100vw, 604px" /></figure>
<p><strong><em>Figure: The Quicksort algorithm selects a pivot element, splits up the list into (i) an unsorted sublist with all elements that are smaller or equal than the pivot, and (ii) an unsorted sublist with all elements that are larger than the pivot. Next, the Quicksort algorithm is called recursively on the two unsorted sublists to sort them. As soon as the sublists contain maximally one element, they are sorted by definition – the recursion ends. At every recursion level, the three sublists (left, pivot, right) are concatenated before the resulting list is handed to the higher recursion level.</em></strong></p>
<p>This brings us to the following code:</p>
<h2>Python One-Liner Quicksort [Code]</h2>
<p><em>Create a function <code>q</code> which implements the Quicksort algorithm in a single line of Python code – and thus sorts any argument given as a list of integers.</em></p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">## The Data
unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner
q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result
print(q(unsorted))</pre>
<p><strong><em>Listing: One-liner solution for the Quicksort algorithm using recursion.</em></strong></p>
<p>What is the output of this code? Let’s see…</p>
<h2>Explanation Quicksort One-Liner</h2>
<p>We have already discussed the recursive Quicksort algorithm above. The one-liner resembles exactly the discussed algorithm. First, we create a new <a href="https://blog.finxter.com/a-simple-introduction-of-the-lambda-function-in-python/" title="Lambda Functions in Python: A Simple Introduction" target="_blank" rel="noreferrer noopener">lambda function</a> q which takes only one list argument <code>l</code>. </p>
<p>The lambda function has the following structure:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">lambda l: q(left) + pivot + q(right) if l else []</pre>
<p>The lambda function returns the empty list <code>[]</code> in the recursion base case (that is – the list to be sorted is empty and, therefore, trivially sorted). </p>
<p>In any other case, it selects the pivot element as the first element of list <code>l</code>, divides all elements into two <a href="https://blog.finxter.com/introduction-to-slicing-in-python/" title="Introduction to Slicing in Python" target="_blank" rel="noreferrer noopener">sublists </a>(left and right) based on whether they are smaller or larger than the pivot. To achieve this, we use simple <a href="https://blog.finxter.com/list-comprehension/" title="List Comprehension in Python — A Helpful Illustrated Guide" target="_blank" rel="noreferrer noopener">list comprehension</a>. </p>
<p>As the two sublists are not necessarily sorted, we recursively execute the Quicksort algorithm on them. Finally, we <a href="https://blog.finxter.com/concatenate-lists-in-python/" target="_blank" rel="noreferrer noopener" title="How to Concatenate Lists in Python? [Interactive Guide]">combine </a>all three lists and return the sorted list. Therefore, the result is:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">## The Result
print(q(unsorted))
# [2, 3, 6, 33, 33, 45, 54]</pre>
<p><strong>Related</strong>: For an interactive experience of what you’ve just learned, check out our Instagram post about the Quicksort algorithm:</p>
<blockquote class="instagram-media" data-instgrm-permalink="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" data-instgrm-version="12" style=" background:#FFF; border:0; border-radius:3px; box-shadow:0 0 1px 0 rgba(0,0,0,0.5),0 1px 10px 0 rgba(0,0,0,0.15); margin: 1px; max-width:540px; min-width:326px; padding:0; width:99.375%; width:-webkit-calc(100% - 2px); width:calc(100% - 2px);">
<div style="padding:16px;"> <a href="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" style=" background:#FFFFFF; line-height:0; padding:0 0; text-align:center; text-decoration:none; width:100%;" target="_blank" rel="noopener noreferrer"> </p>
<div style=" display: flex; flex-direction: row; align-items: center;">
<div style="background-color: #F4F4F4; border-radius: 50%; flex-grow: 0; height: 40px; margin-right: 14px; width: 40px;"></div>
<div style="display: flex; flex-direction: column; flex-grow: 1; justify-content: center;">
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; margin-bottom: 6px; width: 100px;"></div>
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; width: 60px;"></div>
</div>
</div>
<div style="padding: 19% 0;"></div>
<div style="display:block; height:50px; margin:0 auto 12px; width:50px;"><svg width="50px" height="50px" viewBox="0 0 60 60" version="1.1" xmlns="https://www.w3.org/2000/svg" xmlns:xlink="https://www.w3.org/1999/xlink"><g stroke="none" stroke-width="1" fill="none" fill-rule="evenodd"><g transform="translate(-511.000000, -20.000000)" fill="#000000"><g><path d="M556.869,30.41 C554.814,30.41 553.148,32.076 553.148,34.131 C553.148,36.186 554.814,37.852 556.869,37.852 C558.924,37.852 560.59,36.186 560.59,34.131 C560.59,32.076 558.924,30.41 556.869,30.41 M541,60.657 C535.114,60.657 530.342,55.887 530.342,50 C530.342,44.114 535.114,39.342 541,39.342 C546.887,39.342 551.658,44.114 551.658,50 C551.658,55.887 546.887,60.657 541,60.657 M541,33.886 C532.1,33.886 524.886,41.1 524.886,50 C524.886,58.899 532.1,66.113 541,66.113 C549.9,66.113 557.115,58.899 557.115,50 C557.115,41.1 549.9,33.886 541,33.886 M565.378,62.101 C565.244,65.022 564.756,66.606 564.346,67.663 C563.803,69.06 563.154,70.057 562.106,71.106 C561.058,72.155 560.06,72.803 558.662,73.347 C557.607,73.757 556.021,74.244 553.102,74.378 C549.944,74.521 548.997,74.552 541,74.552 C533.003,74.552 532.056,74.521 528.898,74.378 C525.979,74.244 524.393,73.757 523.338,73.347 C521.94,72.803 520.942,72.155 519.894,71.106 C518.846,70.057 518.197,69.06 517.654,67.663 C517.244,66.606 516.755,65.022 516.623,62.101 C516.479,58.943 516.448,57.996 516.448,50 C516.448,42.003 516.479,41.056 516.623,37.899 C516.755,34.978 517.244,33.391 517.654,32.338 C518.197,30.938 518.846,29.942 519.894,28.894 C520.942,27.846 521.94,27.196 523.338,26.654 C524.393,26.244 525.979,25.756 528.898,25.623 C532.057,25.479 533.004,25.448 541,25.448 C548.997,25.448 549.943,25.479 553.102,25.623 C556.021,25.756 557.607,26.244 558.662,26.654 C560.06,27.196 561.058,27.846 562.106,28.894 C563.154,29.942 563.803,30.938 564.346,32.338 C564.756,33.391 565.244,34.978 565.378,37.899 C565.522,41.056 565.552,42.003 565.552,50 C565.552,57.996 565.522,58.943 565.378,62.101 M570.82,37.631 C570.674,34.438 570.167,32.258 569.425,30.349 C568.659,28.377 567.633,26.702 565.965,25.035 C564.297,23.368 562.623,22.342 560.652,21.575 C558.743,20.834 556.562,20.326 553.369,20.18 C550.169,20.033 549.148,20 541,20 C532.853,20 531.831,20.033 528.631,20.18 C525.438,20.326 523.257,20.834 521.349,21.575 C519.376,22.342 517.703,23.368 516.035,25.035 C514.368,26.702 513.342,28.377 512.574,30.349 C511.834,32.258 511.326,34.438 511.181,37.631 C511.035,40.831 511,41.851 511,50 C511,58.147 511.035,59.17 511.181,62.369 C511.326,65.562 511.834,67.743 512.574,69.651 C513.342,71.625 514.368,73.296 516.035,74.965 C517.703,76.634 519.376,77.658 521.349,78.425 C523.257,79.167 525.438,79.673 528.631,79.82 C531.831,79.965 532.853,80.001 541,80.001 C549.148,80.001 550.169,79.965 553.369,79.82 C556.562,79.673 558.743,79.167 560.652,78.425 C562.623,77.658 564.297,76.634 565.965,74.965 C567.633,73.296 568.659,71.625 569.425,69.651 C570.167,67.743 570.674,65.562 570.82,62.369 C570.966,59.17 571,58.147 571,50 C571,41.851 570.966,40.831 570.82,37.631"></path></g></g></g></svg></div>
<div style="padding-top: 8px;">
<div style=" color:#3897f0; font-family:Arial,sans-serif; font-size:14px; font-style:normal; font-weight:550; line-height:18px;"> Sieh dir diesen Beitrag auf Instagram an</div>
</div>
<div style="padding: 12.5% 0;"></div>
<div style="display: flex; flex-direction: row; margin-bottom: 14px; align-items: center;">
<div>
<div style="background-color: #F4F4F4; border-radius: 50%; height: 12.5px; width: 12.5px; transform: translateX(0px) translateY(7px);"></div>
<div style="background-color: #F4F4F4; height: 12.5px; transform: rotate(-45deg) translateX(3px) translateY(1px); width: 12.5px; flex-grow: 0; margin-right: 14px; margin-left: 2px;"></div>
<div style="background-color: #F4F4F4; border-radius: 50%; height: 12.5px; width: 12.5px; transform: translateX(9px) translateY(-18px);"></div>
</div>
<div style="margin-left: 8px;">
<div style=" background-color: #F4F4F4; border-radius: 50%; flex-grow: 0; height: 20px; width: 20px;"></div>
<div style=" width: 0; height: 0; border-top: 2px solid transparent; border-left: 6px solid #f4f4f4; border-bottom: 2px solid transparent; transform: translateX(16px) translateY(-4px) rotate(30deg)"></div>
</div>
<div style="margin-left: auto;">
<div style=" width: 0px; border-top: 8px solid #F4F4F4; border-right: 8px solid transparent; transform: translateY(16px);"></div>
<div style=" background-color: #F4F4F4; flex-grow: 0; height: 12px; width: 16px; transform: translateY(-4px);"></div>
<div style=" width: 0; height: 0; border-top: 8px solid #F4F4F4; border-left: 8px solid transparent; transform: translateY(-4px) translateX(8px);"></div>
</div>
</div>
<div style="display: flex; flex-direction: column; flex-grow: 1; justify-content: center; margin-bottom: 24px;">
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; margin-bottom: 6px; width: 224px;"></div>
<div style=" background-color: #F4F4F4; border-radius: 4px; flex-grow: 0; height: 14px; width: 144px;"></div>
</div>
<p></a></p>
<p style=" color:#c9c8cd; font-family:Arial,sans-serif; font-size:14px; line-height:17px; margin-bottom:0; margin-top:8px; overflow:hidden; padding:8px 0 7px; text-align:center; text-overflow:ellipsis; white-space:nowrap;"><a href="https://www.instagram.com/p/B4SmnmGqYAU/?utm_source=ig_embed&utm_campaign=loading" style=" color:#c9c8cd; font-family:Arial,sans-serif; font-size:14px; font-style:normal; font-weight:normal; line-height:17px; text-decoration:none;" target="_blank" rel="noopener noreferrer">Ein Beitrag geteilt von The Python Blog (@finxter.com_)</a> am <time style=" font-family:Arial,sans-serif; font-size:14px; line-height:17px;" datetime="2019-10-31T17:18:06+00:00">Okt 31, 2019 um 10:18 PDT</time></p>
</div>
</blockquote>
<p> <script async="" src="//www.instagram.com/embed.js"></script> </p>
<p><strong>Related Resources</strong>: </p>
<ul>
<li><a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" target="_blank" rel="noreferrer noopener" title="The Shortest Quicksort Implementation in Python">The Shortest Quicksort Implementation</a></li>
<li><a href="https://blog.finxter.com/python-one-line-x/" target="_blank" rel="noreferrer noopener">Python One Line X</a></li>
<li><a href="https://pythononeliners.com/" target="_blank" rel="noreferrer noopener">Pythononeliners.com</a></li>
<li><a href="https://www.amazon.com/gp/product/B07ZY7XMX8" target="_blank" rel="noreferrer noopener">Book <em>“Python One-Liners”</em> (Amazon Link)</a></li>
<li><a href="https://blog.finxter.com/python-one-line-for-loop-a-simple-tutorial/" target="_blank" rel="noreferrer noopener">Python One Line For Loop</a></li>
<li><a href="https://blog.finxter.com/the-quicksort-algorithm-in-one-line-python/" target="_blank" rel="noreferrer noopener">Python Quicksort One Line</a></li>
</ul>
<h2>Where to Go From Here?</h2>
<p>Enough theory, let’s get some practice!</p>
<p>To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?</p>
<p><strong>Practice projects is how you sharpen your saw in coding!</strong></p>
<p>Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?</p>
<p>Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.</p>
<p>Join my free webinar <a rel="noreferrer noopener" href="https://blog.finxter.com/webinar-freelancer/" target="_blank">“How to Build Your High-Income Skill Python”</a> and watch how I grew my coding business online and how you can, too—from the comfort of your own home.</p>
<p><a href="https://blog.finxter.com/webinar-freelancer/" target="_blank" rel="noreferrer noopener">Join the free webinar now!</a></p>
</div>
https://www.sickgaming.net/blog/2020/07/...quicksort/