[Java] 선택정렬의 논리와 구현 코드 이해하기 (이중 for문 / 자리를 바꿀때 임시 변수에 저장)

이중 for문과 int temp에 임시로 arr[minIndex]를 넣는 구조를 스스로 손으로 적어가며 그 과정들을 체감했다.

선택정렬은 간단하고 직관적이 정렬 알고리즘이다.

 

1. 선택 정렬 알고리즘 흐름

선택 정렬은 주어진 배열에서 가장 작은 값을 찾아 배열의 맨 앞에 위치시키는 과정을 반복한다.

 

2. 알고리즘 논리

  1) 배열의 첫 번째 값부터 시작해서 나머지 값들 중에서 가장 작은 값을 찾는다.

  2) 찾은 값을 현재 위치와 교환한다.

  3) 다음 위치로 이동해 위 과정을 반복한다.

   4) 배열의 끝까지 가면 정렬이 완료된다. 

---

3. 선택 정렬 구현 코드

import java.util.Arrays;

public class SelectionSort {
   public static void selectionSort(int[] arr) {
       int n = arr.length;
       
       // 배열의 처음부터 끝까지 반복
       for (int i = 0; i < n-1 ; i++) {
          // 현재 위치를 최소값의 위치로 가정
          int minIndex = i;
          
          // 현재 위치 이후의 값들 중 최소값 탐색
          for (int j= i+1; j < n; j++) {
              if (arr[j] < arr[minIndex]){
                 mimIndex = j; // 더 작은 값 발견 시 인덱스 업데이트
              }
          }
          
          // 현재 위치와 최소값 위치를 교환
          int temp = arr[minIndex];
          arr[minIndex] = arr[i];
          arr[i] = temp;
     }
   }
   public static void main(String[] args) {
       int[] arr = {9, 6, 7, 3, 5};
       System.out.println("Before Sorting: " + Arrays.toString(arr));
       selctionSort(arr);
       System.out.println("After Sortion:" + Arrays.toString(arr));
   }
}

 

1) 숫자 카드 정렬 게임

 나에게 주어진 숫자 카드 5장은 9, 6 , 7 , 3, 5.

 이 카드를 작은 숫자부터 차례대로 줄을 세워야 한다.

 

 

2) 정렬하는 방법

 2.1) 첫 번째 카드를 기준으로 잡는다. (9)

 2.2) 첫 번째 카드 뒤에서 가장 작은 숫자를 찾는다.(3)

 2.3) 가장 작은 숫자랑 첫 번째 카드 자리 바꾸기! 이제는 3이 맨 앞에 온다.

 2.4) 두번째 카드로 넘어가서 다시 반복한다! 두 번째 카드 뒤에서 가장 작은 숫자를 찾는다.(5)

 2.5) 찾은 숫자랑 자리 바꾸기! (3, 5, 7, 9, 6)

 2.6) 세 번째 카드로 넘어가자. 남은 숫자들 중에서 가장 작은 숫자를 찾고 자리 바꾸기! (3, 5, 6, 9, 7)

 2.7) 마지막으로 네 번째 카드와 다섯 번째 카드로 같은 방법으로 하면 끝!

 

 

제일 작은 숫자 찾고!
그 숫자랑 자리 바꿔!
다음 카드도 똑같이!
맨 끝까지 반복해!

   3.1 실행 결과

Before Sorting: [9, 6, 7, 3, 5]
After Sortion: [3, 5, 6, 7, 9]

---

4. 선택 정렬의 논리적 사고와 자바 문법 해설

  4.1 최소값 탐색 - 카드의 뒷부분을 쭉~ 살펴보면서 가장 작은 숫자를 찾는다.

int minIndex = i;
for (int j = i + 1; j < n; j++) {
   if (arr[j] < arr[minIndex]) {
       minIndex = j;
   }
}

 - minIndex : 현재 가장 작은 값의 인덱스를 저장.

- if 조건문을 통해 배열의 나머지 값들을 비교. 

 

  4.2 값 교환 - 찾은 숫자랑 자리 바꾸기! 

int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;

- 선택 정렬에서는 값 교환이 핵심이다.

- 임시 변수 temp를 사용해 두 값을 안전하게 교환한다.

 

4.3 시간 복잡도

- 최선/최악/평균 시간 복잡도: O(n^2) (이중 반복문 때문).

- 배열의 크기가 작거나 정렬 기준이 간단한 경우 유용.