Quicksort 2 - Sorting Hackerrank 퀵정렬 퀵소트 문제!

퀵소트 ! 퀵 정렬 !

병합 정렬 , Merge Sort 와 같은 divide conquer 정렬이며

O(nlogn) 이 걸리지만 병합 정렬보다 평균 속도가 20% 빠르다.

Quicksort 2 - Sorting 문제에 java로 작성된 코드를 그대로 사용하려 노력했다.

배열을 넘기기 위해 int [] ar 배열을 백터로 바꾸고 

배열을 총 3개 준비 했다. 왼쪽 배열 오른쪽 배열 pivot을 선언하고

돌아갈때마다 원래의 전체 배열의 index 0 부터 할당 해주었다. 

배열의 크기가 2보다 작을 경우는 이미 정렬된 배열이기 때문에 return을 해줬다.

left , right 로 계속해서 함수를 재귀적으로 호출한다.

마지막까지 다다르면 left pivot right 순으로 인쇄하며, 원래의 ar 배열에 index 0부터 계속 할당 해준다.

어려워 어려워... 

Quicksort 2 - Sorting 

by HackerRank

In the previous challenge, you wrote a partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number. This means you 'sorted' half the array with respect to the other half. Can you repeatedly use partition to sort an entire array?

Guideline 
In Insertion Sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays, with a strategy known as "divide and conquer".

When partition is called on an array, two parts of the array get 'sorted' with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Can you repeatedly call partition so that the entire array ends up sorted?

Print Sub-Arrays 
In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, are merged together.

• The first element in a sub-array should be used as a pivot.
• Partition the left side before partitioning the right side.
• The pivot should be placed between sub-arrays while merging them.
• Array of length  or less will be considered sorted, and there is no need to sort or to print them.

Note 
Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

For example: Partition about the first element for the array A[]={5, 8, 1, 3, 7, 9, 2} will be {1, 3, 2, 5, 8, 7, 9}

Input Format 
There will be two lines of input:

•  - the size of the array
•  - the n numbers of the array

Output Format 
Print every partitioned sub-array on a new line.

Constraints 
 
 
Each number is unique.

Sample Input

7
5 8 1 3 7 9 2

Sample Output

2 3
1 2 3
7 8 9
1 2 3 5 7 8 9

Explanation 
This is a diagram of Quicksort operating on the sample array:

Task 
The method quickSort takes in a parameter, , an unsorted array. Use the Quicksort algorithm to sort the entire array.

소스보기 !

import java.util.*;

public class Solution {

    

    static void quickSort(Vector<Integer> ar) {

        if(ar.size()<2) return;

        Vector <Integer> left = new Vector<Integer>();

        Vector <Integer> right = new Vector<Integer>();

        int pivot = ar.get(0);

        for(int i=1; i<ar.size(); ++i){

            if(pivot>=ar.get(i)) {

                left.add(ar.get(i));

            }else{

                right.add(ar.get(i));

            }

        }

        

        quickSort(left);

        quickSort(right);

        

        int index =0;

        

        for(int i=0; i<left.size(); ++i) {

            ar.set(index++,left.get(i));

            System.out.print(left.get(i)+" ");

        }

        ar.set(index++,pivot);

        System.out.print(pivot+" ");

        for(int i=0; i<right.size(); ++i) {

            ar.set(index++,right.get(i));

            System.out.print(right.get(i)+" ");

        }

        System.out.println();

    }

    

    static void printArray(int[] ar) {

        for(int n: ar){

            System.out.print(n+" ");

        }

        System.out.println("");

    }

    

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        Vector <Integer> ar = new Vector<Integer>();

        for(int i=0;i<n;i++){

            int x =in.nextInt();

            ar.add(x);

        }

        quickSort(ar);

    }

}