🤔 정렬 알고리즘

n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘. 종류가 굉장히 다양한데, 이에 따라 수행시간 역시 천차만별.

🗃 선택 정렬 **Selection Sort**

현재 위치에 들어갈 값을 찾아 바꾸어 정렬하는 알고리즘. 현재 위치에 저장될 값의 크기에 따라 최소 선택 정렬(Min-Selection Sort), 최대 선택 정렬(Max-Selection Sort)로 구분할 수 있다.

최소 선택 정렬은 오름 차순, 최대 선택 정렬은 내림차순으로 정렬된다.

👩‍🏫 선택 정렬의 로직

일반적인 케이스

최악의 경우(역순서)

1. 정렬 되지 않은 인덱스의 맨 앞에서 부터, 그 이후의 배열값 중 가장 작은 값을 찾는다.
2. 찾아낸 가장 작은 값을 현재 위치(인덱스)의 값과 바꿔준다.
3. 다음 인덱스에서 같은 과정을 반복한다.

• 코드(java)

  void selectionSort(int[] arr) {
      int indexMin, temp;
      for (int i = 0; i < arr.length-1; i++) {        // 1. index 선택
          indexMin = i;
          for (int j = i + 1; j < arr.length; j++) {  // 2. i+1번째 원소부터 index의 값과 비교
              if (arr[j] < arr[indexMin]) {           // 3. 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면 index를 갱신
                  indexMin = j;
              }
          }
          // 4. swap(arr[indexMin], arr[i])
          temp = arr[indexMin];
          arr[indexMin] = arr[i];
          arr[i] = temp;
    }
    System.out.println(Arrays.toString(arr));
  }

⏰ 선택 정렬의 공간 / 시간복잡도

• 하나의 배열 안에서 값을 바꾸는 식으로 동작하므로 공간복잡도는 O(1)이다.
• 기껏해야 스왑할 때 임시변수 하나의 공간정도가 필요 = in-place 정렬.
  • in-pace sorting : 제자리 정렬.
• 이 정렬 알고리즘은 n-1개, n-2개, …, 1개씩 비교를 반복한다.
  (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
• 배열이 어떻게 구성되어있던 순차적으로 전체 비교를 진행하므로 시간복잡도는 O(n²)이다.

🤔 버블 정렬과 선택 정렬

버블 정렬

선택 정렬

• 버블 정렬과 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 필요한 자료상태에 효율적이다.
• 버블 정렬과 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. = 위에서 설명한 제자리 정렬.
• 근데 둘 다 시간복잡도가 O(n²)이니 쓰지 말라고 하네요(ㅎ)

❗ 주의할 점

버블 정렬(Bubble Sort)이나 삽입 정렬(Insertion Sort)과 유사해 헷갈리기 쉽다고 하는데,

선택 정렬은 해당 순서에 원소를 넣을 위치가 이미 정해져 있고, 어떤 원소를 넣을지 순차적으로 탐색하면서 선택하는 알고리즘임을 기억하면 됩니다!