Skip to main content

Quicksort Algorithm and Data structure in PYTHON

 So, now what is Quicksort ?

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O comparisons to sort n items. In the worst case, it makes O comparisons, though this behavior is rare. Quicksort is often faster in practice than other O algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O additional space used by the stack during the recursion.


Properties of Quicksort :-

The quick sort is an in-place, divide-and-conquer, massively recursive sort algorithm. The efficiency of the algorithm is majorly impacted by which element is chosen as the pivot point. The worst-case efficiency of the quick sort is o (n²) when the list is sorted and left most element is chosen as the pivot.

ALGORITHM OF QUICKSORT :-

1.) First of all, make an element pivot and sort the list with respect to this                        pivot element.

2.) Now, let we chose the first element as pivot and name the second element as         "low" and last element as "high".

3.) Now, name low as "i" and high as "j". 

4.) Look at i and compare it with pivot, if it is greator then stop, if it is smaller than         pivot move on to right next element and again watch it is greator or smaller than      pivot and do the same procedure.

5.) When we get the greator element than pivot while moving right stop at that point.

6.) Now, look at j and see it is greator or smaller, if greator than move left, if smaller      then stop.

7.) When we get the smaller element than pivot while moving left, stop there.

8.) Now, previously we have stopped at greator and now stopped at smaller.

9.) At this point swap the greator and smaller with each other.

10.) Run this loop again and again until we get i > j. At this point stop all the loops.

11.) Now, we get i > j, at this point swap pivot element and j th element with each           other.

12.) Use recursion to run this function again and again and at last we get the sorted         list.

13.) Our list is sorted now.


DATA STRUCTURE OF QUICKSORT IN PYTHON :-







So this the algorithm and data structure of Quicksort in PYTHON programming language. If you want to learn more sorting algorithm go to my previous blogs and you can find there.

Hope you understood this topic, Please share it with you friend and help them learning python.




John Veer
Contact mail id - john.veer.utube@gmail.com
Contact for any query!
Thanks for reading !
</ >

Comments

Post a Comment

Popular posts from this blog

Doubly Linked List in PYTHON

  Here is the Python code for the Doubly Linked List :- #first of all creat a class node class Node :     def __init__ ( self , data ):         self . data = data         self . next = None         self . prev = None #now create a class of doubly linked list class DLL :     def __init__ ( self ):         self . head = None #function to insert the node at begining     def insertatbeg ( self , data ):         newnode = Node ( data )         newnode . prev = None         newnode . next = self . head         self . head = newnode #function to insert the node at the end     def insertatend ( self , data ):         newnode = Node ( data )         if self . head is None :             self . head ...
Post a Comment
Read more

Binary Search Tree and Binary Heap in PYTHON

Here is the Python code for Binary Search Tree :- Content included:- 1.) Insertion 2.) Search Operation 3.) Deletion 4.) Minimum Node 5.) Maximum Node 6.) Preorder Traversal 7.) InOrder Traversal 8.) PostOrder Traversal class BST: def __init__(self, data): self.root = data self.left = None self.right =None def insertnode(self, data): if self.root is None: self.root = data return if self.root is data: return elif self.root > data: if self.left is not None: self.left.insertnode(data) else: self.left = BST(data) elif self.root data: if self.left is not None: self.left.searchoprn(data) else: print("Data is not present.") elif self.root self.root: if self.right: selfright = self.right.deletenode(data) ...
Post a Comment
Read more

Bubble Sort Algorithm in PYTHON

What is Bubble Sort ? And why do we need this ? Bubble sort is the simplest algorithm to sort any array. Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.  In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes . ALGORITHM :- 1.) Firstly we have an unsorted list, which is to be sorted. 2.) Consider the first element of the list. Then compare it with the next element. 3.) If the second element is greator than the first element than swap them. 4.) If the second element is smaller than the first element, then we don't have to do anything. 5.) Going ahead, now after swap (may or may not), look for second...
Post a Comment
Read more