정렬

정렬

• 탐색을 위하여 정렬이 꼭 필요함
• 탐색할 데이터가 정렬되어 있지 않다면 순차 탐색 말고 다른 알고리즘을 사용할 수 없지만, 정렬되어 있다면 이진탐색 이라는 알고리즘을 사용할 수 있음
• 특징 : 특정 값을 선택하였을 때, 왼쪽 값은 선택된 값보다 항상 작거나 같고 오른쪽 값은 항상 크거나 같음
• 정렬된 데이터의 특징을 활용하면 데이터의 탐색이 훨씬 빨라지고, 더 적은 횟수만 비교하여 원하는 값을 찾을 수 있음
• 즉, 이진 탐색이 가능한 데이터를 만들기 위하여 정렬을 수행함

버블 정렬

• 인접한 데이터를 비교하여 앞의 데이터가 뒤의 데이터보다 크면 자리를 바꾸는 정렬 알고리즘
• 교육용으로만 사용됨

package sort;

import java.util.Arrays;

public class bubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 1};
        bubble_sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void bubble_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

삽입 정렬

• 보드게임 시, 내가 쥔 카드를 순서대로 정렬하는 것과 비슷함
• 새로운 카드를 기존의 정렬된 카드 사이의 올바른 위치에 삽입
• 새로 삽입될 카드의 수 만큼 반복됨
• 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입

package sort;

import java.util.Arrays;

public class insertSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        insert_sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void insert_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int now = arr[i]; //현재값
            int beforeIdx = i - 1; //이전값의 index
            while (beforeIdx >= 0 && arr[beforeIdx] > now) { //이전 index가 0 이상이고 이전 값이 현재 값보다 크다면 while문 실행
                //while문 : index를 하나씩 뒤로 미뤄주기 위함
                arr[beforeIdx + 1] = arr[beforeIdx]; //다음 값에 현재 값 저장(한 칸씩 뒤로 밀리는 것)
                beforeIdx--; //이전 값으로 index를 이동하여 원래 탐색하려는 수로 이동
            }
            arr[beforeIdx + 1] = now; //비어있는 곳에 현재 값 저장
        }
    }
}

여기서 while문을 이해하는데 시간이 오래 걸렸다.
예를 들어, 배열이 [1,3,2]라고 치자. 그럼 값들이 다음과 같다.

1. now == arr[2], beforeIdx == 1
2. 이전값 > 현재값이므로 while문 실행
   arr[2] = arr[1] 이므로 저장된 배열은 [1, ,3]
3. 이전 값이 저장된 index로 다시 이동하기 위하여 1을 빼줌(현재 beforeIdx는 2이기 때문)
4. while문을 벗어나 비어있는 곳에 2를 채워줌

여기서의 while문은 2번에서 알 수 있듯, 값을 추가하기 위하여 현재 값보다 큰 값들의 index 값을 1씩 뒤로 미루는 역할을 한다.