This Chapter will help you to understand Quick Sort Algorithm And Its Examples in Hindi and understand the complexity in quick sort.
Quick Sort एक तत्व को एक pivot element के रूप में चुनने और इसके चारों ओर सरणी को विभाजित करने के विचार के आधार पर विभाजन के आधार पर होता है जैसे: धुरी के बाईं ओर में वे सभी तत्व होते हैं जो pivot element से कम होते हैं। इसमें pivot से अधिक सभी तत्व शामिल हैं
यह reduces the space complexity को कम करता है और सहायक सरणी के उपयोग को हटाता है जो Merge sort में उपयोग किया जाता है। अधिकांश मामलों में एक random pivot का चयन करने से सरणी में सुधार होता है।
नीचे दिए गए कार्यान्वयन में, निम्नलिखित घटकों का उपयोग किया गया है: यहां, = सरणी जिनके तत्वों को क्रमबद्ध किया जाना है
Start: सरणी की सबसे बाईं स्थिति
End: सरणी की सबसे सही स्थिति
i: उन तत्वों के बीच की सीमा जो धुरी से कम हैं और धुरी से अधिक हैं
j: व्यूह के विभाजन और बिना विभाजन के बीच की सीमा
pivot: pivot element
यहां हम Partition() function का उपयोग करके सरणी को पुन: व्यवस्थित करके pivot element की उचित स्थिति का पता लगाते हैं। फिर हम सरणी को pivot के बाईं ओर दो हिस्सों में विभाजित करते हैं (elements less than pivot element) और धुरी के दाईं ओर (elements greater than pivot element) और उसी चरण को पुनरावर्ती रूप से लागू करते हैं।
Recursive function FOr Quick sort
Example : आपके पास एक सरणी A = [10,7,8,3,2,1] नीचे दिए गए आरेख में देखें, कि randpartition () function 7 के रूप में बेतरतीब ढंग से चुनता है और फिर इसे सरणी के पहले तत्व के साथ स्वैप करता है और फिर Partition() function कॉल होता है, जो सरणी को दो हिस्सों में विभाजित करता है। पहले आधे में 7 से कम और दूसरे आधे में 7 से बड़े तत्व हैं।
5 वीं कॉल में 7 से कम तत्वों के लिए, randpartition () function को मूल रूप से pivot element के रूप में चुनता है और फिर इसे पहले तत्व के साथ स्वैप करता है और Partition() function को कॉल करता है। 7th और 8 th Call के बाद, आगे कोई कॉल नहीं हो सकती क्योंकि दोनों कॉल में केवल एक तत्व बचा है। इसी तरह, आप 7 से अधिक तत्वों के लिए कॉल का क्रम देख सकते हैं।
use randpartition () function in quicksort() algorithm to reduce time complexity in QUICK SORT Algorithm.
time complexity in worst case is O(N^2) But for this randomized algorithm time complexity will fluctuate O(N^2) and O(N logN) Common Time complexity in Quick Sort is O(N logN).
![]() |
Quick Sort Algorithm And Its Examples in hindi |
Quick Sort एक तत्व को एक pivot element के रूप में चुनने और इसके चारों ओर सरणी को विभाजित करने के विचार के आधार पर विभाजन के आधार पर होता है जैसे: धुरी के बाईं ओर में वे सभी तत्व होते हैं जो pivot element से कम होते हैं। इसमें pivot से अधिक सभी तत्व शामिल हैं
यह reduces the space complexity को कम करता है और सहायक सरणी के उपयोग को हटाता है जो Merge sort में उपयोग किया जाता है। अधिकांश मामलों में एक random pivot का चयन करने से सरणी में सुधार होता है।
Implementation For Quick Sort
pivot element के रूप में सरणी के पहले तत्व का चयन करें सबसे पहले, हम देखेंगे कि pivot के चारों ओर सरणी का विभाजन कैसे होता है।नीचे दिए गए कार्यान्वयन में, निम्नलिखित घटकों का उपयोग किया गया है: यहां, = सरणी जिनके तत्वों को क्रमबद्ध किया जाना है
![]() |
Quick sort algorithm in hindi |
Start: सरणी की सबसे बाईं स्थिति
End: सरणी की सबसे सही स्थिति
i: उन तत्वों के बीच की सीमा जो धुरी से कम हैं और धुरी से अधिक हैं
j: व्यूह के विभाजन और बिना विभाजन के बीच की सीमा
pivot: pivot element
यहां हम Partition() function का उपयोग करके सरणी को पुन: व्यवस्थित करके pivot element की उचित स्थिति का पता लगाते हैं। फिर हम सरणी को pivot के बाईं ओर दो हिस्सों में विभाजित करते हैं (elements less than pivot element) और धुरी के दाईं ओर (elements greater than pivot element) और उसी चरण को पुनरावर्ती रूप से लागू करते हैं।
int partition ( int A[],int start ,int end) { int i = start + 1; int piv = A[start] ; //make the first element as pivot element. for(int j =start + 1; j <= end ; j++ ) { /*rearrange the array by putting elements which are less than pivot on one side and which are greater that on other. */ if ( A[ j ] < piv) { swap (A[ i ],A [ j ]); i += 1; } } swap ( A[ start ] ,A[ i-1 ] ) ; //put the pivot element in its proper place. return i-1; //return the position of the pivot }
Recursive function FOr Quick sort
void quick_sort ( int A[ ] ,int start , int end ) { if( start < end ) { //stores the position of pivot element int piv_pos = partition (A,start , end ) ; quick_sort (A,start , piv_pos -1); //sorts the left side of pivot. quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot. } }
![]() |
working of Quick sort algorithm |
Example : आपके पास एक सरणी A = [10,7,8,3,2,1] नीचे दिए गए आरेख में देखें, कि randpartition () function 7 के रूप में बेतरतीब ढंग से चुनता है और फिर इसे सरणी के पहले तत्व के साथ स्वैप करता है और फिर Partition() function कॉल होता है, जो सरणी को दो हिस्सों में विभाजित करता है। पहले आधे में 7 से कम और दूसरे आधे में 7 से बड़े तत्व हैं।
5 वीं कॉल में 7 से कम तत्वों के लिए, randpartition () function को मूल रूप से pivot element के रूप में चुनता है और फिर इसे पहले तत्व के साथ स्वैप करता है और Partition() function को कॉल करता है। 7th और 8 th Call के बाद, आगे कोई कॉल नहीं हो सकती क्योंकि दोनों कॉल में केवल एक तत्व बचा है। इसी तरह, आप 7 से अधिक तत्वों के लिए कॉल का क्रम देख सकते हैं।
int rand_partition ( int A[ ] , int start , int end ) { //chooses position of pivot randomly by using rand() function . int random = start + rand( )%(end-start +1 ) ; swap ( A[random] , A[start]) ; //swap pivot with 1st element. return partition(A,start ,end) ; //call the above partition function }
use randpartition () function in quicksort() algorithm to reduce time complexity in QUICK SORT Algorithm.
time complexity in worst case is O(N^2) But for this randomized algorithm time complexity will fluctuate O(N^2) and O(N logN) Common Time complexity in Quick Sort is O(N logN).
Quick Sort Program In C++
/* C++ implementation of QuickSort */ #includeusing namespace std; // A utility function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int partition (int arr[], int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } /* The main function that implements QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ void quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } /* Function to print an array */ void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } // Driver Code int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); cout << "Sorted array: \n"; printArray(arr, n); return 0; }
Quick Sort Program In C
/* C implementation QuickSort */ #include// A utility function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int partition (int arr[], int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j <= high- 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } /* The main function that implements QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ void quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } /* Function to print an array */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("n"); } // Driver program to test above functions int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n-1); printf("Sorted array: n"); printArray(arr, n); return 0; }
Quick Sort Program In Python
# Python program for implementation of Quicksort Sort # This function takes last element as pivot, places # the pivot element at its correct position in sorted # array, and places all smaller (smaller than pivot) # to left of pivot and all greater elements to right # of pivot def partition(arr,low,high): i = ( low-1 ) # index of smaller element pivot = arr[high] # pivot for j in range(low , high): # If current element is smaller than the pivot if arr[j] < pivot: # increment index of smaller element i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return ( i+1 ) # The main function that implements QuickSort # arr[] --> Array to be sorted, # low --> Starting index, # high --> Ending index # Function to do Quick sort def quickSort(arr,low,high): if low < high: # pi is partitioning index, arr[p] is now # at right place pi = partition(arr,low,high) # Separately sort elements before # partition and after partition quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) # Driver code to test above arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr,0,n-1) print ("Sorted array is:") for i in range(n): print ("%d" %arr[i]),
Quick Sort Program In Java
// Java program for implementation of QuickSort class QuickSort { /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; jArray to be sorted, low --> Starting index, high --> Ending index */ void sort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; i++) System.out.print(arr[i]+" "); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = {10, 7, 8, 9, 1, 5}; int n = arr.length; QuickSort ob = new QuickSort(); ob.sort(arr, 0, n-1); System.out.println("sorted array"); printArray(arr); } }