230516 5주 2일차 TIL. 선택정렬, 삽입정렬

삽입정렬

삽입 정렬은 i번째 값이 들어갈 위치를 찾아 삽입하는 것 같다하여 삽입 정렬이라 한다.

삽입 정렬의 i는 1부터 시작한다.

인덱스 i번째 값과 그 왼쪽에 있는 값들을 비교한다.

i와 i-1, i와 i-2 …. 이런식으로 진행된다.

진행 로직을 나타내면

길이가 3인 배열일 경우

i = 1일 때 인덱스 1과 인덱스 0 비교,

i = 2일 때 인덱스 2와 인덱스 1 비교,

i = 2일 때 인덱스 1과 인덱스 0 비교,

i = 3일 때 인덱스 3과 인덱스 2 비교,

i = 3일 때 인덱스 2과 인덱스 1 비교,

i = 3일 때 인덱스 1과 인덱스 0 비교

 

이런식으로 진행된다. 가장 오른쪽에서부터 가장 오른쪽 값과 그 왼쪽값.

그 다음은 한칸 왼쪽으로 옮겨가서 해당 값과 그 왼쪽값을 비교하는 형식이다.

코드 작성하면 이런식

import java.util.Arrays;

public class InsertionSort01 {
   public static void main(String[] args) {
       int[] arr = {7, 2, 3, 9, 28, 11};
       // i j j-1
       // 1 1 0
       // 2 2 1
       // 2 1 2
       // 3 3 2
       // 3 2 1
       // 3 1 0
       for (int i = 1; i < arr.length; i++) {
           for (int j = i; j > 0; j--) 
               System.out.printf("i:%d j:%d j-1:%d\n", i, j, j-1);
               if (arr[j] < arr[j - 1]) {
                   int temp = arr[j];
                   arr[j] = arr[j - 1];
                   arr[j - 1] = temp;
               }
           }
       }
       System.out.println(Arrays.toString(arr));
   }
}

 

여기서 개선할 점?

- 교환이 안될 때 break;

교환이 안되면 i번째 앞의 값들은 이미 위치를 찾은 것이므로 중복하여 비교할 필요 없다..

for (int i = 1; i < arr.length; i++) {
   for (int j = i; j > 0; j--) {
       System.out.printf("i:%d j:%d j-1:%d\n", i, j, j-1);
       if (arr[j] < arr[j - 1]) {
           int temp = arr[j];
           arr[j] = arr[j - 1];
           arr[j - 1] = temp;
       } else break;
   }
}
System.out.println(Arrays.toString(arr));

↑ 이렇게 튜닝(수정)할 수 있다. 교환이 안되면 break를 걸고 다음 칸으로 넘어간다.

 

 

 

 

InsertSort : OOP 적용

- .sort( ) 추가

- 내림차순 기능 추가 (오버로딩)

public class InsertionSort03 {
   public int[] sort(int[] arr, boolean isAscending) {
       for (int i = 1; i < arr.length; i++) {
           for (int j = i; j > 0; j--) {
               if ((isAscending ? arr[j - 1] - arr[j] : arr[j] - arr[j - 1]) > 0) {
                   int temp = arr[j];
                   arr[j] = arr[j - 1];
                   arr[j - 1] = temp;
               } else break;
           }
       }
       return arr;
   }
   public int[] sort(int[] arr) {
       return sort(arr, true);
   }

   public static void main(String[] args) {
       int[] arr = {7, 28, 2, 3, 9, 11};
       InsertionSort03 is = new InsertionSort03();
       arr = is.sort(arr);
       System.out.println(Arrays.toString(arr));
   }
}

- sort 추가 후 내림차순 기능 추가를 위해 오버로딩을 함.

- sort 호출 시 인자가 하나만 전달될 경우 오름차순, false가 전달될 경우 내림차순으로 정렬됨.

- asc와 desc를 결정하는 부분은 삼항연산자를 사용하여 수정.

 

 

선택 정렬

선택 정렬은 for문이 한 번 돌 때 최대값/최소값을 구해 하나씩 자리를 지정하여 정렬하는 방식

코드는 다음과 같다.

public class SelectionSOrt {
   public static void main(String[] args) {
       int[] arr = {7, 2, 3, 9, 28, 11};


       for (int j = 0; j < arr.length; j++) {
           int targetValue = arr[j];
           int targetIndex = j;
           for (int i = j + 1; i < arr.length; i++) {
               if (targetValue > arr[i]) {
                   targetValue = arr[i];
                   targetIndex = i;
               }
           }
              int temp = arr[j];
           arr[j] = arr[targetIndex];
           arr[targetIndex] = temp;
       }
       System.out.println(Arrays.toString(arr));
   }
}