정렬1 (버블정렬, 삽입정렬, 선택정렬)

1. 정렬

• 특정 값을 기준으로 데이터를 순서대로 배치하는 방법
• 구현 난이도는 쉽지만, 속도는 느린 알고리즘
  • 버블 정렬, 삽입 정렬, 선택 정렬
• 구현 난이도는 조금 더 여럽지만, 속도는 빠른 알고리즘
  • 합병 정렬, 힙 정렬, 트리 정렬
• 하이브리드 정렬
  • 팀 정렬, 블록 병합 정렬, 인트로 정렬
• 기타 정렬 알고리즘
  • 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬

2. 버블 정렬

• 인접한 데이터를 비교하여 자리 바꾸는 방식
• 알고리즘 복잡도 : O(n^2)

// int[] arr = {3, 5, 2, 7, 1, 4};
public static void bubbleSort(int[] arr) {
        for (int i = 0 ; i < arr.length ; i ++) {
            int tmp;
            for (int j = i+1 ; j < arr.length ; j++) {
                if (arr[i] > arr[j]) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

3. 삽입 정렬

• 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식
• 알고리즘 복잡도 : O(n^2)

// int[] arr = {3, 5, 2, 7, 1, 4};
public static void insertionSort(int[] arr) {
        for (int i = 1 ; i < arr.length ; i++) {
            int tmp;
            for (int j = i ; j > 0 ; j--) {
                if (arr[j-1] > arr[j]) {
                    tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }

4. 선택 정렬

• 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤 부터 정렬하는 방식
• 알고리즘 복잡도 : O(n^2)

// int[] arr = {3, 5, 2, 7, 1, 4};
private static void selectionSort(int[] arr) {
        for (int i = 0 ; i < arr.length ; i++) {
            int mini = i;
            int tmp;
            for (int j = i+1 ; j < arr.length ; j++){
                if (arr[mini] > arr[j]) {
                    mini = j;
                }
            }
            tmp = arr[mini];
            arr[mini] = arr[i];
            arr[i] = tmp;

        }
    }

(버블정렬, 삽입정렬, 선택정렬 결과 이미지)