JAVA에서 정렬하는 방법

선택정렬 O(n²)

가장 기본적인 정렬 방법. 각 요소들을 하나씩 비교해 비교하는 요소와 가장 작은 요소의 자리를 바꾼다.

int[] arr = {4, 5, 1, 2, 3};
int minIndex = 0; // 가장 작은 요소의 index. 첫번째 요소의 index로 초기화
for(int i = 0; i < arr.length; i++){
  for(int j = i+1; j < arr.length; j++){
    if(arr[minIndex] > arr[j]){
      minIndex = j; // minIndex가 가리키는 요소가 비교하는 요소보다 크면 minIndex를 갱신
    }
  }
  int temp = arr[i]; // 지금 비교하는 요소의 값을 보관
  arr[i] = arr[minIndex]; // 가장 작은 요소의 값을 비교하는 요소의 위치로 이동
  arr[minIndex] = temp; // 가장 작은 요소의 위치엔 비교하는 요소를 할당
}

배열이 n개일 때 n번 반복문을 돌면서 n - 1만큼 반복문을 돌면서 비교를 해야하기 때문에 시간복잡도는 O(n²)

삽입정렬 O(n²)

각 요소를 비교하여 정렬한다는 점은 선택정렬하고 동일. 그러나 비교하는 요소의 전 요소들은 정렬되어 있다고 전제. 비교하는 요소와 비교하는 요소의 앞 요소를 비교해 점점 앞으로 이동시킨다.

int[] arr = {7, 5, 9, 0, 3};
        /*
        5 7 9 0 3
        5 7 9 0 3 (9는 비교하는 수보다 크므로 유지)
        0 5 7 9 3
        0 3 5 7 9
         */
for(int i = 1; i < arr.length; i++){
  for (int j = i; j >= 1; j--){
    if(arr[j] < arr[j-1]){
      int temp = arr[j-1];
      arr[j-1] = arr[j];
      arr[j] = temp;
     }else break; // 비교하는 요소가 비교당하는 요소보다 크면 그 자리에 유지.
  }
}

중접 for문을 사용하므로 시간복잡도는 O(n²)이다. 그러나 배열이 어느 정도 정렬되어 있다면 아주 일부의 반복만 수행하면 되기에 O(n)의 시간복잡도를 보일 수도 있다.

퀵 정렬 O(nlogn)

pivot이라는 기준점을 두어서 기준점 왼쪽에는 기준점보다 작은 수들을, 오른쪽에는 기준점보다 큰 수들로 점차 정렬해가는 방식. 아래 코드는 첫번째 index를 기준점으로 두는 호어 분할 방식의 예.

    public static void main(String[] args) {
        int[] arr = {4, 1, 2, 5, 9, 6, 7};

        sort(arr, 0, arr.length - 1);

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

    private static void sort(int[] arr, int start, int end){
        int pivotIndex = start;
        int leftIndex = start + 1;
        int rightIndex = end;

        if(start >= end){
            return;
        }

        // 왼쪽 index가 오른쪽 index보다 커지면 while문 탈출
        while (leftIndex <= rightIndex) {
            int pivotValue = arr[pivotIndex];

            while (leftIndex <= end && pivotValue > arr[leftIndex]){
                leftIndex++;
            }

            while (rightIndex > start && pivotValue < arr[rightIndex]){
                rightIndex--;
            }

            if(leftIndex <= rightIndex){ // 작은 수와 큰 수를 교체
                int temp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = temp;
            }else{ // 피벗과 작은 수를 교체
                int temp = arr[rightIndex];
                arr[rightIndex] = arr[pivotIndex];
                arr[pivotIndex] = temp;
            }
            sort(arr, start, rightIndex - 1);
            sort(arr, rightIndex + 1, end);
        }
    }