퀵 정렬 알고리즘

public static List<Integer> quickSort(List<Integer> numbers) {
   if (numbers.size() < 2) {
      return numbers;
   }

   Integer pivot = numbers.get(0);
   List<Integer> lower = new ArrayList<>();
   List<Integer> higher = new ArrayList<>();

   for(int i=1; i < numbers.size(); i++) {
      if (numbers.get(i) < pivot) {
         lower.add(numbers.get(i));
      } else {
         higher.add(numbers.get(i));
      }
   }

   List<Integer> sorted = quickSort(lower);
   sorted.add(pivot);
   sorted.addAll(quickSort(higher));

   return sorted;
}

 

 

 - pivot 임시 원소 하나 선택 아무 원소를 선택 해도 상관 없음.

 - 재귀 알고리즘은 실행을 종료할 수 있는지 확인 해야 한다.

 - 삽입 정렬 알고리즘 보다 훨씬 더 효율적으로 성능을 발휘한다. 알고리즘의 복잡도는 O(n log n_이다.