이 포스팅의 코드 및 정보들은 강의를 들으며 정리한 내용을 토대로 작성한 것입니다.

Array Parallel Sort

정렬할 때 Fork/Join Framework를 사용해서 배열을 병렬적으로 정렬할 수 있다.

알고리즘의 효율이 바뀐 것은 아니지만, Parallel Sort라는 메서드가 추가됐고, 여러 스레드를 분산해서 처리하기 때문에 조금 더 빠르게 정렬할 수 있다.

sort()와 parallelSort() 비교하기

시간 복잡도는?

이 알고리즘이 worst case에는 O(N2)의 시간복잡도가 소요된다.

보통은 parallel sort의 속도가 더 빠르지만, CPU나 리소스, 정렬하는 배열의 크기에 따라서 달라질 수 있다.

어쩌다가 한 두번쯤은 sort()가 더 빠를 때도 있다.

정리

• Arrays.parallelSort()
  • Fork/Join Framework를 사용해서 배열을 병렬로 정렬하는 기능을 제공한다.
• 병렬 정렬 알고리즘
  • 배열을 둘로 계속 쪼갠다
  • 합치면서 정렬한다
• sort()와 parallelSort() 비교

int size = 1500;
int[] numbers = new int[size];
Random random = new Random();
IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());

long start = System.nanoTime();
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();
Arrays.parallelSort(numbers);
System.out.println("parallel sorting took " + (System.nanoTime() - start));

• 알고리즘의 효율성은 sort()나 parallelSort()나 둘 다
  • 시간 복잡도 : O(N logN)
    • 최악의 상황 : O(N2)
  • 공간 복잡도 : O(N)

Reference

더 자바, Java 8 - 백기선 강사님 강의를 토대로 정리했습니다.