시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
빠른 정렬은 정렬 알고리즘입니다. 정렬되지 않은 배열이 주어지면 빠른 정렬 알고리즘을 사용하여 정렬합니다.
예
입력 : {8, 9, 5, 2, 3, 1, 4}
출력 : {1, 2, 3, 4, 5, 8, 9}
차례
이론
- Divide and Conquer 정렬 알고리즘입니다.
- 배열에서 피벗 요소를 선택하고 배열을 두 부분으로 분할합니다. 한 부분은 피벗보다 작은 값을 가진 배열 요소로 구성되고 다른 부분은 피벗보다 큰 배열 요소를 포함합니다. 그런 다음 이러한 부분 사이에 피벗을 배치하고 왼쪽 및 오른쪽 하위 배열을 재귀 적으로 정렬합니다.
- 피벗 요소는 다음과 같은 방법으로 선택할 수 있습니다.
- 첫 번째 배열 요소
- 마지막 배열 요소 (여기에서 구현 됨)
- 중앙값 배열 요소
- 모든 Array 요소.
- 피벗을 선택한 후 split () 함수를 적용하여 피벗 주위의 나머지 배열을 분할합니다.
- split ()은 피벗의 왼쪽으로 피벗보다 작은 배열 요소를 배치합니다.
- split ()은 피벗보다 큰 배열 요소를 피벗의 오른쪽으로 배치합니다.
- (피벗의) 왼쪽 및 오른쪽 하위 배열이 정렬되거나 정렬되지 않을 수 있습니다.
- 완전히 정렬 된 배열을 얻기 위해 왼쪽과 오른쪽 부분 배열을 재귀 적으로 정렬합니다.
빠른 정렬 알고리즘
우리는 주로 두 가지 기능을 적용합니다
- 스플릿() – 피벗을 선택하고 피벗을 중심으로 배열을 분할합니다. 마지막 요소를 피벗으로 선택합니다.
- 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
빠른 정렬의 복잡성 분석
시간 복잡성
-
- 최상의 경우 : O (nlogn)
- 최악의 경우: 의 위에2)
- 평균 사례 : O (nlogn)
추가 정보
- Quicksort는 안정적인 정렬 알고리즘이 아닙니다.
- Quicksort는 내부 정렬 알고리즘으로 보조 공간이 필요하지 않습니다.
- 실제로 데이터가 작거나 외부 저장 공간에 저장되는 경우 퀵 정렬이 병합 및 힙 정렬보다 빠릅니다.
- Quicksort는 배열의 경우 병합 정렬보다 더 잘 수행되며 정렬을 위해 추가 공간이 필요하지 않습니다.
- 또한 배열에 사용될 때 참조 위치가 좋기 때문에 캐시 친화적 인 정렬 알고리즘입니다.
- 또한 꼬리 재귀 적이므로 꼬리 호출 최적화가 수행됩니다.
- 병합 정렬은 연결 목록을 정렬 할 때 빠른 정렬보다 선호됩니다.
