Quick Sort Algorithm And Its Examples in hindi

This Chapter will help you to understand Quick Sort Algorithm And Its Examples in Hindi and understand the complexity in quick sort.

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 */
#include  
using 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; j Array 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); 
    } 
}

Sorting Algorithm : - 

Bubble Sort Algorithm And sorting program in different language

bucket sort Algorithm In Hindi And Its Examples

Counting sort Algorithm in hindi and Its Example 

Heap Sort Algorithm In Hindi and its examples 

Insertion sort Algorithm And Its Examples

Merge Sort Algorithm In HIndi And Its Examples 

Selection sort algorithm And Its Examples