Skip to main content

Quick-Sort

Quick Sort, as the name suggests, sorts any list very quickly. Quick sort is not stable search, but it is very fast and requires very less aditional space. It is based on the rule of Divide and Conquer(also called partition-exchange sort). This algorithm divides the list into three main parts :
  1. Elements less than the Pivot element
  2. Pivot element
  3. Elements greater than the pivot element
As the image suggests, a pivot is selected at first which is 4 in our case.It then compares the other members with the pivot and divides the list into three main parts as discussed above.
The next step is to call this function recursively.It will return one number if only one member is left in any of the three parts.


Complexity Analysis of Quick Sort

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n log n)
  • Space required by quick sort is very less, only O(n log n) additional space is required.
  • Quick sort is not a stable sorting technique, so it might change the occurence of two similar elements in the list while sorting.
Labels:

Comments

Post a Comment

Comment on articles for more info.

Popular posts from this blog

Understanding Python Decorators

If you have ever wondered what those @something mean above a python function or method then you are going to have your answers now. This @something line of code is actually called a decorator. I have red from various articles about them but some of them were not able to clarify the concept of a decorator and what we can achieve with them. So in this post we'll learn a lot about python decorators. Here is a list of topics we'll be covering. What is python decorator Understanding the concept Multiple decorators on same function class method decorator Where can we use decorators What is python decorator A python decorator is nothing but a function which accepts your given function as a parameter and returns a replacement function. So its like something this def decorator(your_func): def replacement(your_func_args): #do some other work return replacement @decorator your_func(your_func_args): #your_func code Now when your_func gets called then...
1 comment
Read more

Cordova viewport problem solved

Include the viewport settings in Cordova If you are facing the auto zooming problem of cordova then go read on the full article. Cordova actually ignores the viewport meta tag which causes the pixel density problem. So we need to tell cordova that viewport tag is equally important as other tags. To do this, we need to add some code to a file which is specify in the article. Corodva messes with pixels If you are using the latest cordova version or creating the cordova app for latest android versions then you may have faced the zoom malfunctioning.I also faced it when creating an app. Many of you may have already searched the web and found the answer of changing the meta tag attributes to get it working. But adding target-densitydpi=medium-dpi does not solve the problem for latest android versions. It may work for gingerbread but not for kitkat and others. So the final solution which i found was one of the stackexchange answer but rarely found. So i am gonna two things here, i ...
5 comments
Read more

Hash Tables : Handling Collision

We saw in the previous post how a simple hash table can be constructed without much effort. But, and that is a big But, that table was prone to collisions and could result in corrupted data. Of course we don't want a data structure which can corrupt our data even if it is faster. So to avoid data corruption we will study some collision resolution techniques and will see how to evenly distribute a key over the table to minimize collision. Lets continue the journey. What Problems Does Hashing Solve ? Simple Implementation of Hash Table Collision Resolution Chaining Open Addressing Designing Hash Functions How Python Dictionaries Work Hashing in Action Collision Resolution First of all, what is collision ? Collision is a phenomenon which happens when 2 or more distinct keys are mapped to the same hash table entry. But we don't wa...
Post a Comment
Read more