배열 Parallel 정렬 (Arrays.parallelSort)

Arrays.parallelSort()

• Fork/Join 프레임워크를 사용해서 배열을 병렬로 정렬하는 기능을 제공한다

배열 정렬 알고리즘

• 배열을 둘로 계속 쪼갠다
• 합치면서 정렬한다
• MergeSort와 같은 형태

코드

int size = 100000;
int[] numbers = new int[size];
Random random = new Random();

//10만개의 배열을 랜덤값으로 채운다
IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());
long start = System.nanoTime();

//일반적인 자바 정렬함수를 사용한 경우
//자바는 투 피봇 퀵소트를 사용한다 (Dual-Pivot Quicksort)
//시간복잡도는 O(N log N)이고 싱글 쓰레드를 사용한다
Arrays.sort(numbers);
System.out.println("serial sorting took " + (System.nanoTime() - start));

IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());
start = System.nanoTime();

//parallelSort를 사용한 경우
//Fork/Join 프레임 워크를 사용해서 배열을 병렬쓰레드로 정렬하는 기능을 제공한다
//배열의 크기가 10만개 이상 정도로 상당히 클때 효율적이고 배열의 크기가 1~2만 이하라면 퀵소트가 더 빠르다
//배열을 둘로 계속 쪼갠 후 합치면서 정렬 - MergeSort와 같은 구조
Arrays.parallelSort(numbers);
System.out.println("parallel sorting took " + (System.nanoTime() - start));

//시간 출력 (약 두배까지도 차이가 난다)
serial sorting took 98441413
parallel sorting took 50919674