빠른 정렬

난이도 중급
자주 묻는 질문 어도비 벽돌 골드만 삭스 HSBC 퀄컴 삼성 SAP SAP 연구소 타겟 코퍼레이션
배열 분열과 정복 정렬조회수 560

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

빠른 정렬은 정렬 알고리즘입니다. 정렬되지 않은 배열이 주어지면 빠른 정렬 알고리즘을 사용하여 정렬합니다.

입력 : {8, 9, 5, 2, 3, 1, 4}

출력 : {1, 2, 3, 4, 5, 8, 9}

이론

  1. Divide and Conquer 정렬 알고리즘입니다.
  2. 배열에서 피벗 요소를 선택하고 배열을 두 부분으로 분할합니다. 한 부분은 피벗보다 작은 값을 가진 배열 요소로 구성되고 다른 부분은 피벗보다 큰 배열 요소를 포함합니다. 그런 다음 이러한 부분 사이에 피벗을 배치하고 왼쪽 및 오른쪽 하위 배열을 재귀 적으로 정렬합니다.빠른 정렬
  3. 피벗 요소는 다음과 같은 방법으로 선택할 수 있습니다.
    1. 첫 번째 배열 요소
    2. 마지막 배열 요소 (여기에서 구현 됨)
    3. 중앙값 배열 요소
    4. 모든 Array 요소.
  4. 피벗을 선택한 후 split () 함수를 적용하여 피벗 주위의 나머지 배열을 분할합니다.
    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. 최악의 경우: 의 위에2)
    3. 평균 사례 : O (nlogn)

추가 정보

  1. Quicksort는 안정적인 정렬 알고리즘이 아닙니다.
  2. Quicksort는 내부 정렬 알고리즘으로 보조 공간이 필요하지 않습니다.
  3. 실제로 데이터가 작거나 외부 저장 공간에 저장되는 경우 퀵 정렬이 병합 및 힙 정렬보다 빠릅니다.
  4. Quicksort는 배열의 경우 병합 정렬보다 더 잘 수행되며 정렬을 위해 추가 공간이 필요하지 않습니다.
  5. 또한 배열에 사용될 때 참조 위치가 좋기 때문에 캐시 친화적 인 정렬 알고리즘입니다.
  6. 또한 꼬리 재귀 적이므로 꼬리 호출 최적화가 수행됩니다.
  7. 병합 정렬은 연결 목록을 정렬 할 때 빠른 정렬보다 선호됩니다.

참고 면접 질문

균열 시스템 설계 인터뷰
Translate »