Жылдам сұрыптау


Күрделілік дәрежесі орта
Жиі кіреді Adobe Голдман Сакс HSBC Qualcomm Samsung SAP SAP зертханалары Target Corporation
Array Бөліңіз және жеңіңіз Сұрыптау

Жылдам сұрыптау - сұрыптау алгоритмі. Массивтің сұрыпталмаған алгоритмі арқылы сұрыпталған.

мысал

Кіріс: {8, 9, 5, 2, 3, 1, 4}

Шығарылым: {1, 2, 3, 4, 5, 8, 9}

теория

  1. Бұл бөлу және жеңу сұрыптау алгоритмі.
  2. Ол жиымдағы бұрылыс элементін таңдайды, массивті екі бөлікке бөледі. Бір бөлігі мәні бұрылыс мәнінен кіші массив элементтерінен тұрады, екінші бөлігі бұрылыс мәнінен үлкен жиым элементтері бар. Содан кейін айналдырғышты осы бөліктердің арасына орналастырады және ішкі және сол жақ оң жақ редакторлы түрде сұрыптайды.Жылдам сұрыптау
  3. Жиынтық элементті келесі жолдармен таңдауға болады:
    1. бірінші жиым элементі
    2. массивтің соңғы элементі (мұнда енгізілген)
    3. жиымның орташа элементі
    4. Кез келген массив элементі.
  4. Бұрылысты таңдағаннан кейін, біз жиымның қалған бөлігін айналдыру үшін бөлу () функциясын қолданамыз.
    1. split () жиым элементтерін бұрылыс шеңберінен солға қарай орналастырады
    2. split () жиым элементтерін бұрылыс шеңберінен оңға қарай орналастырады
    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

Жылдам сұрыптауға арналған Java коды

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. Ең нашар жағдай: O (n2)
    3. Орташа жағдай: O (nlogn)

Қосымша ақпарат

  1. Quicksort тұрақты сұрыптау алгоритмі емес.
  2. Quicksort - орнында сұрыптау алгоритмі, көмекші кеңістікті қажет етпейді.
  3. Іс жүзінде киксорс біріктіру және үймелеудің сұрыптауына қарағанда жылдамырақ, егер деректер аз болса және / немесе сыртқы сақтау кеңістігінде сақталса.
  4. Quicksort массивтер жағдайында Merge sort-қа қарағанда жақсы жұмыс істейді және сұрыптау үшін қосымша орын қажет емес.
  5. Бұл сонымен қатар кэшке ыңғайлы сұрыптау алгоритмі, өйткені ол массивтер үшін қолданылған кезде анықтамалықтың жақсы жеріне ие.
  6. Бұл сондай-ақ құйрық рекурсивті, сондықтан оңтайландыру жасалады.
  7. Біріктірілген сұрыптау байланыстырылған тізімдерді сұрыптау үшін жылдам сұрыптауға қарағанда артықшылықты.

анықтамалық Сұхбат сұрақтары