שנעל סאָרט


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי גאָלדמאַן סאַקס הסבק קוואַלקאַם סאַמסונג זאַפט SAP לאַבס Target Corporation
מענגע צעטיילן און קאַנגקער סאָרטינג

Quick Sort איז אַ סאָרטינג אַלגערידאַם. געגעבן אַ ונסאָרטעד מענגע, סאָרט עס מיט שנעל סאָרט אַלגערידאַם.

בייַשפּיל

איינגאבע: {8, 9, 5, 2, 3, 1, 4}

רעזולטאַט: {1, 2, 3, 4, 5, 8, 9}

טעאָריע

  1. סאָרטינג אַלגערידאַם איז אַ דיוויד און קאָנקווער.
  2. עס פּיקס אַ דרייפּונקט עלעמענט אין די מענגע, ספּליץ די מענגע אין צוויי פּאַרץ. איין טייל באשטייט פון מענגע עלעמענטן מיט אַ ווערט ווייניקער ווי די דרייפּונקט, אן אנדער טייל כּולל מענגע עלעמענטן גרעסער ווי די דרייפּונקט. דערנאָך ערייז די דרייפּונקט צווישן די פּאַרץ און רעקאָרסיוועלי סאָרץ לינקס און רעכט סובאַררייַס.שנעל סאָרט
  3. דרייפּונקט עלעמענט קענען זיין אויסגעקליבן אין די פאלגענדע וועגן:
    1. ערשטער מענגע עלעמענט
    2. לעצטע מענגע עלעמענט (ימפּלאַמענאַד דאָ)
    3. מעדיאַן מענגע עלעמענט
    4. קיין ערייז עלעמענט.
  4. נאָך סעלעקטינג דרייפּונקט, מיר נוצן די שפּאַלטן () פונקציע צו שפּאַלטן די רעשט פון די מענגע אַרום די דרייפּונקט.
    1. שפּאַלטן () לייגט מענגע עלעמענטן ווייניקער ווי דרייפּונקט צו לינקס פון די דרייפּונקט
    2. שפּאַלטן () ערטער מענגע עלעמענטן גרעסער ווי דרייפּונקט צו די רעכט פון די דרייפּונקט
    3. די לינקס און רעכט סובאַררייַס (פון די דרייפּונקט) קען זיין אָדער זענען נישט אויסגעשטעלט
  5. מיר רעקורסיוועלי סאָרט לינקס און רעכט סובאַררייַס צו באַקומען גאָר סאָרטירט מענגע.

שנעל סאָרט אַלגערידאַם

מיר דער הויפּט צולייגן צוויי פאַנגקשאַנז

  1. שפּאַלטן () - סעלעקט דרייפּונקט און שפּאַלטן די מענגע אַרום די דרייפּונקט, מיר סעלעקטירן די לעצטע עלעמענט ווי דרייפּונקט.
  2. quickSortServe () - רעקורסיוועלי סאָרט לינקס און רעכט סובאַררייַס.

C ++ קאָד פֿאַר קוויק סאָרט

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// funtion to split array around pivot
int split(int arr[],int lo,int hi)
{
    int i = lo-1;
    // select last element as pivot
    int pivot = hi;

    // All elements less than arr[pivot] are brought to left side
    // This splits array into two parts
    // array -> [left subarr] [pivot] [right subarr]
    for(int j=lo;j<pivot;j++)
    {
        if(arr[j] < arr[pivot])
        {
            i++;
            swap(arr[i],arr[j]);
        }
    }

    // Bring pivot element to it's correct postion in sorted array
    // by swapping smallest element of right subarray with pivot
    swap(arr[i+1],arr[pivot]);

    return i+1;
}

// Service function to recursively perfrom split()
// for left and right subarrays
void quickSortServe(int arr[],int lo,int hi)
{
    if(lo < hi)
    {
        int pivot = split(arr,lo,hi);
        
        // recursively perfrom split() for right and left subarrays
        quickSortServe(arr,lo,pivot-1);
        quickSortServe(arr,pivot+1,hi);
    }
}

// Function to implement quick sort algorithm
void quickSort(int arr[],int size)
{
    quickSortServe(arr,0,size-1);
}

int main()
{
    
    int arr[] = {8,9,5,2,3,1,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

רעזולטאַט

1 2 3 4 5 8 9

דזשאַוואַ קאָוד פֿאַר קוויק סאָרט

import java.io.*;

class QSort
{
    int split(int arr[],int lo,int hi)
    {
        int i = lo-1;
        // select last element as pivot
        int pivot = hi;

        // All elements less than arr[pivot] are brought to left side
        // This splits array into two parts
        // array -> [left subarr] [pivot] [right subarr]
        for(int j=lo;j<pivot;j++)
        {
            if(arr[j] < arr[pivot])
            {
                i++;
                int temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
            }
        }

        // Bring pivot element to it's correct postion in sorted array
        // by swapping smallest element of right subarray with pivot

        int temp = arr[i+1];
        arr[i+1] = arr[pivot];
        arr[pivot] = temp;

        return i+1;
    }
    
    // Service function to recursively perfrom split()
    // for left and right subarrays
    void quickSortServe(int arr[],int lo,int hi)
    {
        if(lo < hi)
        {
            int pivot = split(arr,lo,hi);
            
            // recursively perfrom split() for right and left subarrays
            quickSortServe(arr,lo,pivot-1);
            quickSortServe(arr,pivot+1,hi);
        }
    }
    
    // Function to implement quick sort algorithm
    void quickSort(int arr[],int size)
    {
        quickSortServe(arr,0,size-1);
    }
    // main function
    public static void main(String args[])
    {
        int arr[] = {8,9,5,2,3,1,4};
        int n = arr.length;

        QSort obj = new QSort();
        obj.quickSort(arr,n);

        for(int i=0;i<n;i++)
        {
            System.out.print(arr[i]+" ");
        }
    }
}

רעזולטאַט

1 2 3 4 5 8 9

קאַמפּלעקסיטי אַנאַליסיס פון קוויק סאָרט

צייט קאַמפּלעקסיטי

    1. בעסטער פאַל: O (nlogn)
    2. ערגסט פאַל: אָ (n2)
    3. דורכשניטלעך פאַל: O (nlogn)

Supplementary Information

  1. קוויקסאָרט איז נישט אַ סטאַביל סאָרטינג אַלגערידאַם.
  2. קוויקקסאָרט איז אַן אָרט-סאָרטירונג אַלגערידאַם - טוט נישט דאַרפן אַגזיליערי פּלאַץ.
  3. אין פּראַקטיס, קוויקסאָרט איז פאַסטער ווי סאָרט און העאַפּ סאָרט אין קאַסעס ווען דאַטן זענען קליין און / אָדער סטאָרד אין פונדרויסנדיק סטאָרידזש פּלאַץ.
  4. קוויקקסאָרט פּערפאָרמז בעסער ווי Merge סאָרט אין פאַל פון ערייז און ריקווייערז קיין עקסטרע פּלאַץ פֿאַר סאָרטינג צוועקן.
  5. עס איז אויך אַ קאַש-פרייַנדלעך סאָרטינג אַלגערידאַם, ווייַל עס איז אַ גוטע רעפערענץ אָרט ווען געוויינט פֿאַר ערייז.
  6. עס איז אויך רעקורסיווע עק, דעריבער אָפּטימיזאַטיאָן פון עק רופן זענען דורכגעקאָכט.
  7. צונויפגיסן סאָרט איז בילכער איבער שנעל סאָרט פֿאַר סאָרטינג לינגקט רשימות.

דערמאָנען ינטערוויעוו פֿראגן