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

Image Search Engine Using Python

Images provide a lot more information than audio or text. Image processing is the prime field of research for robotics as well as search engines. In this article we will explore the concept of finding similarity between digital images using python. Then we will use our program to find top 10 search results inside a dataset of images for a given picture. It won't be as good as google's search engine because of the technique we will be using to find similarity between images. But what we are going to make will be pretty cool. So lets start. Setting up the Environment Our Algorithm How the code looks Lets build the GUI Additional Techniques Setting up the Environment The code we are going to write requires a few tools which we need to install first. I will try to be as precise as i can and if you get stuck into installing some tool then you can drop a comment below and i will help you sort out the problem. So here are the tools and the steps to install ...
18 comments
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

Why Interfaces are Awesome in Go

Why Interfaces are Awesome in Go Language Go, or Golang, is known for being a simple, yet powerful programming language. One of the core concepts that makes Go stand out is interfaces . Interfaces in Go help you write flexible, reusable, and maintainable code. They allow different types to share common behaviors without worrying about the exact type behind the scenes. In this article, we'll dive into why interfaces are awesome, with easy-to-understand examples. We’ll also give some tips on how to make the best use of them in your Go programs. What is an Interface? An interface in Go defines a set of method signatures (rules), but it doesn't provide the implementation. Instead, any type that implements these methods can be said to "satisfy" the interface. This allows you to write code that can work with different types as long as they share certain behaviors. Basic Example of an Interface package main import "fmt" // Define an interface with ...
Post a Comment
Read more