21로그 - 검색을 쉽게 만드는 정렬 : 선택 정렬 vs 퀵 정렬

선택 정렬

1. 배열에서 최솟값을 찾는다.
2. 최솟값과 정렬되지 않은 맨 앞의 수와 위치를 바꾼다.
3. 최솟값이 이동한 부분은 고정된다.
4. 고정된 부분 이 후부터 배열을 돌면서 1번부터 반복한다.

선택 정렬 구현(Java) 오름차순

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  
            if (arr[j] < arr[indexMin]) {           
                indexMin = j;  // 최솟 값 찾기
            }
        }
        // 최솟값과 제일 앞의 수를 바꿔 주기
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

선택 정렬 시간 복잡도

이중 for문에서 알 수 있듯이 O(N^2) 이다.

첫 번째 값을 찾기 위해 N번 확인 해야 하고, 두 번째 값을 찾기 위해 N+1번 확인하고.. 반복하면

N+ (N-1) + … + 2 + 1 = N(N+1) 이므로 O(N^2)이 된다.

퀵 정렬

배열을 두 부분으로 나누고, 나뉜 부분을 다시 퀵 정렬 하는 대표적인 *분할 정복 방법을 사용한다.

*분할 정복 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

1. 배열에서 하나의 원소를 골라 이 원소를 피벗(pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 작은 원소가, 피벗 뒤에는 피벗보다 큰 원소가 오도록 이동 시킨다.(divide)
3. 피벗 기준으로 좌우 부분에서 재귀적(recursion)으로 1번부터 반복한다.

(책에서는 정렬해야 할 원소들이 알파벳으로 이루어진 이름이라는 것이 명확하여 알파벳 순서대로 반을 나누어 정렬했지만, 숫자를 정렬한다고 생각하면 범위를 알 수 없으니 고정된 기준으로 나눌 순 없고 배열의 원소를 기준으로 잡고 나눠야 한다)

퀵 정렬 구현(Java) 오름차순

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

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

퀵 정렬 시간 복잡도

O(NlogN) - N이 1이 될 때까지 2로 나누는 횟수.

최악의 경우는 O(N^2)이 된다.

1 2 3 4 5 6

(리스트가 불균형하게 나누어 지는 경우 - 정렬하고자 하는 배열이 정렬이 되어 있는 경우)

정렬이 되어 있으면 가운데 수를 선택하면 좋다! 그니까 무조건 가운데를 피벗으로 선택하는게 이득!

---

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview (gyoogle.dev)