How to Implement Quicksort Algorithm in Python – the Pytho

  • 时间:2020-09-28 16:28:51
  • 分类:网络文摘
  • 阅读:102 次

In here, we talk about the implementation of QuickSort in Python – the well-known and standard sorting algorithm that is used today.

It is not so easy to implement except in Python, in a Pythonic way. The quicksort algorithm can be easily illustrated using the following Python recursion function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < = 1:
            return nums
        
        pivot = random.choice(nums)
        lt = [v for v in nums if v < pivot]
        eq = [v for v in nums if v == pivot]
        gt = [v for v in nums if v > pivot]
        return self.sortArray(lt) + eq + self.sortArray(gt)  
class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < = 1:
            return nums
        
        pivot = random.choice(nums)
        lt = [v for v in nums if v < pivot]
        eq = [v for v in nums if v == pivot]
        gt = [v for v in nums if v > pivot]
        return self.sortArray(lt) + eq + self.sortArray(gt)  

First, we choose a random pivot, then we partition the input array into three parts, then recursively partition left, and right parts, finally merge into a new list.

The downside of above implementation is it requires additional O(N) space, which can be eliminated using in-place swapping.

Depending on the randomness when choosing a good pivot, the performance of the quicksort may vary. The worst cases would be O(N^2), and average complexity is O(Nlog(N))

This implementation is easy to remember and easy to write on coding whiteboard. And it is code that works rather than pseudo-code.

Recursive Quicksort implementation in Javascript: Javascript Coding Exercise: The QuickSort Implementation in Javascript

--EOF (The Ultimate Computing & Technology Blog) --

推荐阅读:
统计图沾上了污渍  佳佳从甲地往乙地走  小明每天下午五点放学  这个游戏规则公平吗  两枚硬币正面都朝上的可能性是几分之几  这根绳子一共被剪成多少段  扇形和半圆有重叠部分  为wordpress新建一个登录页面  wordpress自动显示图片exif信息插件-Display Exif  为wordpress设置一个简单的后台登陆地址 
评论列表
添加评论