정렬 - 선택, 버블, 삽입

<버블정렬>

-안정적인 정렬 알고리즘

-배열이 부분적으로 정렬될 경우 효율적

-큰 데이터를 정렬하는데 대해서는 비효율적

-요즘 뜨고 있는 정렬;; 

왜? 배달봇이나 드론의 경우 앞에 장애물이 있을 경우, 빠른 판단이 필요하기 때문에 새롭게 뜨고 있음

-한바퀴 돌때 , 가장 큰 수가 제자리를 찾는다

 두번째, 그 다음 큰 수가 제자리를 찾는다

(코드는 리뷰에)

 

<선택정렬>

-한번에 하나씩 최소값을 찾아서 교환하는 방식

-큰 데이터를 정렬하는데 비효율적

-한바퀴 돌떄 가장 작은 값이 제자리를 찾는다

그다음에는 두번째로 작은 값이  제자리를 찾는다

 

public class Selection {
    public static void main(String[] args) {
        int[] arr = {8, 7, 6, 5, 4, 5, 1, 4};  // 정렬할 배열
        
        // 선택 정렬 알고리즘
        for (int i = 0; i < arr.length - 1; i++) {
            // 현재 위치에서 가장 작은 값을 찾기 위한 변수
            int minIndex = i;
          
          for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; 
                }
            }    
            // 가장 작은 값과 현재 위치의 값을 교환
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

 

<삽입정렬>

- 배열을 왼쪽부터 오른쪽으로 탐색하면서 이미 정렬된 부분에 적절한 위치에 삽입하는 방식의 알고리즘

-배열이 거의 정렬된 상태에서는 효율

 

public class Insertion {
    public static void main(String[] args) {
        int[] arr = {8, 7, 6, 5, 4, 5, 1, 4};  // 정렬할 배열
        
        // 삽입 정렬 알고리즘
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];  // 현재 비교할 값
            int j = i - 1;
            
            // 정렬된 부분에서 key보다 큰 값들을 한 칸씩 뒤로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];  // 값 이동
                j = j - 1;  // 이전 위치로 이동
            }
            
            // key 값을 적절한 위치에 삽입
            arr[j + 1] = key;
        }
    }
}