(24.09.26) 정렬 알고리즘 : Quick Sort, Merge Sort

Java에서 이미 Collecions 클래스를 통해서 이미 sort 메서드에서 내부적으로 진행하고 있는 정렬에대해서

사실상 코딩 테스트나 실무에서는 크게 중심적으로는 사용하지는 않는 알고리즘이지만,

 

어떻게 작동이 된는 것인지, 그리고 분할한 뒤에 재귀적인 반복과 통합하는 방식의 정렬로

알고리즘에 대해서 인식하고 이러한 방식을 참고해서 로직에서 참고할 수 있기 때문에,

 

따로 같이 블로그에 공부해서 스스로 코드도 작성하면서 정리

---

퀵 정렬 Quick Sort

• 데이터들을 어떤 기준이 되는 Pivot 데이터를 정해서 그 데이터 기준으로 작으면 왼쪽 크면 뒤로 미루는 분할 시켜 정렬하는 방식을 반복하면서 정렬하는 방식
  • 피봇은 대게 첫번째 또는 마지막 인덱스 값으로 선택
• 순서를 보장하지 않고 오로지 정렬만을 하는 방식
• 상대적으로 데이터 집합을 빠르게 정렬하는 알고리즘
  • 시간복잡도
    • 평균 O(n log n)
      • 보통의 랜덤으로 섞인 데이터
    • 최악 O(n²)
      • 이미 정렬된 경우
• 별도의 메모리를 사용하지 않는 정렬 : In-place Sort
  • 좋은 메모리 효율
• Java Collections 클래스와 Arrays 클래스의 sort() 메서드도 퀵 정렬을 기준으로 정렬
  • 그렇게 때문에 Array클래스에서도 사용이 가능한것
  • 굳이, 코드를 알고리즘으로 정하지 않아도, 해당 메서드를 사용할 수 있음

퀵 정렬 Quick Sort FLOW

1. 피벗(pivot) 설정
   • 배열에서 임의의 값을 피벗으로 설정
     • 일반적으로 첫 번째, 중간, 마지막 요소 중 하나를 선택 (랜덤 가능)
2. 분할(Divide)
   • 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 배치 : 파티셔닝(partitioning)
3. 재귀 호출(Conquer)
   • 분할된 두 배열에 대해 재귀적으로 다시 퀵 정렬을 수행
     • 배열을 나눌 수 없을 때 까지, 크기가 1이 될 때 까지
4. 병합(Merge / Combine)
   • 결과를 합치기
     • 어차피 크기가 1이 될때까지 분할을 진행하기 자동으로 정렬

public class QuickSort {
  public static void main(String[] args) {
    int[] arr = { 10, 80, 30, 90, 40, 50, 70 };

    quickSort(arr);

    System.out.println(Arrays.toString(arr));
  }

  public static void quickSort(int[] arr, int low, int high) {
    // 배열이 없어질 때까지
    if (low < high) {
      // 피봇 설정
      int pivot = arr[high]; // 가장 높은 것부터 피봇 설정
      int i = low; // 초기값은 low로 설정

      // 분할(파티셔닝)
      for (int j = low; j < high; j++) {

        // 피봇보다 작은 값일 경우, low 인덱스부터 하나씩 채우기, 단 바꾸기로
        if (arr[j] < pivot) { // 내림차순일 경우에는 당연히 arr[j] > pivot
          // i j 교환
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
          
          // 다음 인덱스로 설정
          i++;
        }

      }

      // 마지막 i인덱스 값으로 피봇 재설정
      int temp = arr[i];
      arr[i] = arr[high];
      arr[high] = temp;
      
      // 분할해서 전부 끝냈기 때문에
      int pivotIndex = i;

      // 재귀 호출
      quickSort(arr, low, pivotIndex - 1);
      quickSort(arr, pivotIndex + 1, high);

    }

  }

  // overloading
  public static void quickSort (int[] arr) {
    quickSort(arr, 0, arr.length-1);
  }

}

---

병합 정렬 Merge Sort

• 배열의 반을 계속 재귀적으로 나누면서 병합하며 정렬하는 방식의 정렬 알고리즘
• 단, 추가적인 정렬을 위한 공간이 발생할 수 있음
  • 공간 복잡도 O(n)
• 시간복잡도
  • O(n log n) 항상 유지 : 항상 반으로 나누면서 정렬을 진행하기 때문에

병합 정렬 Merge Sort FLOW

1. 분할(Divide)
   • 배열을 절반 분할
     • 배열의 크기가 1이 될 때까지
2. 정복(Conquer)
   • 크기가 1인 배열끼리 병합
   • 병합하면서 각 배열을 정렬(오름차순, 내림차순)
3. 결합(Combine)
   • 병합된 두 배열을 다시 병합하면서 더 큰 배열로 정렬된 상태로 결합
   • 이 과정을 모든 배열이 하나로 합쳐질 때까지 반복

public class MergeSort {
  public static void main(String[] args) {

    int[] arr = { 10, 80, 30, 90, 40, 50, 70 };

    mergeSort(arr);

    System.out.println(Arrays.toString(arr));
  }

  public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
      // 중간 인덱스
      int mid = (left + right) / 2;

      int[] temp = new int[right - left + 1]; // 임시 배열
      int i = left;
      int j = mid + 1;
      int k = 0;

      // 재귀적으로 왼쪽과 오른쪽 부분 정렬
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);

      // 병합
      while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
          temp[k++] = arr[i++];
          // 아래를 위의 코드가 한번에 작동된 것
          // temp[k] = arr[i];
          // k++;
          // i++;
        } else {
          temp[k++] = arr[j++];
        }
      }

      // 남아 있는 배열들 다시 temp에 추가하는 단계
      // 왼쪽 배열에 원소 추가
      while (i <= mid) {
        temp[k++] = arr[i++];
      }

      // 오른쪽 배열에 원소 추가
      while (j <= right) {
        temp[k++] = arr[j++];
      }

      // arr 에 적용ㅇ
      for (k = 0; k < temp.length; k++) {
        arr[left + k] = temp[k];
      }

    }
  }

  // overloading
  public static void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
  }

}

---

 

간단한 알고리즘일지라도, 필요에 따라서는 해당 알고리즘을 비교해서 

데이터의 크기나 갯수별 어떤 정렬이 더 유용한지에 대해서 인식을 하고

활용할 수 있도록 해야할 것