[Lucky Algorithm] Quicksort 1 - Partition(36/77)

Quicksort 1 - Partition (Hacker Rank)

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.

import java.util.*;
public class Solution {

    static void partition(int[] ar) {
        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();
        int p = ar[0];

        for(int i = 1; i < ar.length; i++){
            if(ar[i] > p){
                right.add(ar[i]);
            }else{
                left.add(ar[i]);
            }
        }
        left.add(p);
        left.addAll(right);
        printArray(left);
    }   

    static void printArray(List<Integer> 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);
    }    
}

행운의 77문제 프로젝트

  행운의 77문제 프로젝트는 한 달동안 알고리즘 문제 77개를 푸는 프로젝트입니다.