Quick Sort

Quick Sort

  • Is one of the most efficient sorting algorithms.
  • Is based on the divide and conquer approach.
  • Successively divides the problem into smaller parts until the problems become so small that they can be directly solved.
Quick Sort Algorithm
QuickSort(low,high)
	1. If (low > high):
		Return.
	2. Set pivot = arr[low].
	3. Set i = low + 1.
	4. Set j = high.
	5. Repeat step 6 until i > high or arr[i]> pivot.
	// Search for an element greater than the pivot.   
       6.	Increment i by 1.
	7.	Repeat step 8 until j < low or arr[j] < pivot.
       //Search for an element smaller than pivot			
	8.	Decrement j by 1.
	9.	If i < j: 
            // If greater element is on the left of 
           //smaller element
				 	Swap arr[i] with arr[j].
     10.	If i <= j:
			  	Go to step 5. // Continue the search
     11.	  If low < j:
			  	Swap arr[low] with arr[j]. 
   //Swap pivot with last element in first part of the list
Determining the Efficiency of the Quick Sort Algorithm
  • The total time taken by this sorting algorithm depends on the position of the pivot value. 
  • If the first element is chosen as the pivot, it leads to a worst case efficiency of O(n2). 
  • The worst case occurs when the list is already sorted.
  • In this case, the total number of comparisons is:
Number of comparisons
= n + (n – 1) + (n – 2) + .. + 2 + 1 
= n(n – 1)/2
= O(n2)
  • If you select the median of all values as the pivot, the efficiency will be O(n log n).
CCC Online Test 2021 CCC Practice Test Hindi Python Programming Tutorials Best Computer Training Institute in Prayagraj (Allahabad) Best Java Training Institute in Prayagraj (Allahabad) Best Python Training Institute in Prayagraj (Allahabad) O Level Online Test in Hindi Bank SSC Railway TET UPTET Question Bank career counselling in allahabad Sarkari Naukari Notification Best Website and Software Company in Allahabad Sarkari Exam Quiz