흔들기 정렬

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

흔들기 정렬!?

내 모든 독자들은 오늘의 문제의 이름이 매우 재미 있다는 것을 알았을 것입니다. 그러나 다양한 범위의 개념에 대한 우리의 이해를 테스트하는 것은 매우 현명한 문제입니다.

더 이상 혼동하지 않고 문제로 바로 넘어 갑시다.

예

당신은 배열이 있습니다

입력 : [1,5,1,6,4]

예상 출력 : [1,6,4,1,5]

어떻게?

흔들림도 정렬 :

배열의 요소는 다음과 같이 정렬되어야합니다. arr[0]<arr[1]>arr[2]<arr[3] 등등 흔들림 정렬에서.

접근

가장 쉬운 방법으로 갈 것입니다. 다음 예를 고려하여

배열 : [1,5,1,1,6,4]

해당 배열의 복사본을 만들어 정렬하겠습니다.

핀

파란색 : 원래 배열 빨간색 : 정렬 됨 배열 복사

어레이 길이 : 6

복사 배열의 작은 요소를 원래 배열에 배치하겠습니다.

핀

작은 요소를 복사 한 후 원래 배열

지금. 남은 부분에 더 큰 요소를 배치하겠습니다.

핀

짜잔. 배열이 흔들려 정렬되었습니다!

홀수 요소를 포함하는 배열에 대해 패스를 약간 변경합니다.

살펴 보겠습니다.

핀

두 번째 마지막 요소 대신 마지막 요소에서 시작합니다.

첫 번째 패스 후

핀

이제 더 큰 요소를

핀

A 비슷한 문제 우리는 좋은 이해를 얻기 위해 우리와 함께 확인할 수 있습니다.

이제 우리는 그것을 이해했습니다. 코드를 살펴 보자

흔들기 정렬을위한 Java 코드

class Solution 
{
    int index=0;
    public void assemble(int[] nums,int copy[],int start)
    {
        //The assemble function 
        for(int i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public void wiggleSort(int[] nums) 
    {
        int copy[]=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            copy[i]=nums[i];
        Arrays.sort(copy);
        if(nums.length%2==0)
        {
            assemble(nums,copy,nums.length-2);
            assemble(nums,copy,nums.length-1);
        }
        else
        {
            assemble(nums,copy,nums.length-1);
            assemble(nums,copy,nums.length-2);
        }
    }
}

흔들기 정렬을위한 C ++ 코드

class Solution 
{
    public:
    int index=0;
    public:
    void assemble(vector<int>& nums,vector<int>& copy,int start)
    {
        int i=0;
        for(i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public:
    void wiggleSort(vector<int>& nums) 
    {
        vector<int>copy(nums);
        sort(copy.begin(), copy.end());
        if(nums.size()%2==0)
        {
            assemble(nums,copy,nums.size()-2);
            assemble(nums,copy,nums.size()-1);
        }
        else
        {
            assemble(nums,copy,nums.size()-1);
            assemble(nums,copy,nums.size()-2);
        }
    }
};

흔들기 정렬을위한 복잡성 분석

위 문제에 대한 시간 복잡성 = O (n log n)

위의 방법으로 Wiggle 정렬을위한 공간 복잡성 = O (n)

어떻게?

• 사용 된 정렬 작업은 시간 복잡도가 O (n logn) 인 내장 병합 정렬입니다.
• 어셈블 함수에 대한 각 호출에서
  • 우리는 대체 요소를 살펴보고 그에 따라 사본에서 원래 배열로 배치합니다.
• 따라서 요소가 모두 제자리에 배치 될 때까지 배열의 모든 요소를 ​​살펴 봅니다.
• 배열로 이동하면 시간 복잡도가 O (n)
• 그러나이 경우 정렬 작업은 시간 복잡도를 O (n logn)로 가져 오는 더 많은 비용이 드는 것으로 나타났습니다.
• 요소로 복사 배열을 만들었을 때 공간 복잡성은 O (n), 즉 선형