Quicksort 1 - Partition Hackerrank 퀵소트 퀵정렬 알고리즘

퀵소트, 퀵정렬

정렬되지 않은 배열의 값을 임의로 pivot 변수로 정한 후

pivot 보다 작은건 왼쪽 큰건 오른쪽으로 분리 시킨다. 

재귀적으로 정렬을 반복하다 보면 O(nlogn) 수행시간안에 정렬이 완료된다. 

Divide and conquer 분할 정복 알고리즘중에 하나!

아래 문제는 처음 1회의 퀵소트 정렬을 마친 배열을 출력하라고 한다.

Quicksort 1 - Partition 

by HackerRank

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of . In these next few challenges, we're covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).

Step 1: Divide 
Choose some pivot element, , and partition your unsorted array, , into three smaller arrays: , , and , where each element in , each element in , and each element in .

Challenge 
Given  and , partition  into , , and  using the Divide instructions above. Then print each element in  followed by each element in , followed by each element in  on a single line. Your output should be space-separated.

Note: There is no need to sort the elements in-place; you can create two lists and stitch them together at the end.

Input Format

The first line contains  (the size of ). 
The second line contains  space-separated integers describing  (the unsorted array). The first integer (corresponding to ) is your pivot element, .

Constraints

• All elements will be unique.
• Multiple answer can exists for the given test case. Print any one of them.

Output Format

On a single line, print the partitioned numbers (i.e.: the elements in , then the elements in , and then the elements in ). Each integer should be separated by a single space.

Sample Input

5
4 5 3 7 2

Sample Output

3 2 4 5 7

Explanation

 
Pivot: . 
; ; 

, so it's added to . 
; ; 

, so it's added to . 
; ; 

, so it's added to . 
; ; 

, so it's added to . 
; ; 

We then print the elements of , followed by , followed by , we get: 3 2 4 5 7.

This example is only one correct answer based on the implementation shown, but it is not the only correct answer (e.g.: another valid solution would be 2 3 4 5 7).

소스 보기 !

import java.util.*;

public class Solution {

    

    static void partition(int[] ar) {

        int p = ar[0],e = ar.length;

        int left[] = new int[e];

        int right[] = new int[e];

        int rs=0,ls=0,os=0;

        for(int i=1; i<e; i++){

            if(p<ar[i]) right[rs++] = ar[i];

            else left[ls++] = ar[i];

        }

        for(int i=0; i<ls; i++) ar[os++] = left[i];

        ar[os++] = p;

        for(int i=0; i<rs; i++) ar[os++] = right[i];

        printArray(ar);

    }

    

    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();

        int[] ar = new int[n];

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

            ar[i]=in.nextInt();

        }

        partition(ar);

    }

}