알고리즘) Selection/Insertion/Bubble Sort (선택/삽입/버블 정렬)

Selection Sort (선택 정렬)

0번째 자리와 '1번째-N-1번째 중에서 가장 작은 값'을 교환,
1번째 자리와 '2번째-N-1번째 중에서 가장 작은 값'을 교환,
...

• 평균/최악 시간 복잡도 : O(n2)

import java.lang.Math;
import java.util.Scanner;;

public class Test {

    public static void printArray(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.printf("%2d ", arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.print("before Sort: ");
        printArray(arr);

        selectionSort(arr, n);

        System.out.print("after Sort: ");
        printArray(arr);
    }

    public static void selectionSort(int[] arr, int size) {
        for(int i=0; i<size; i++) {
            int minIndex = i;
            for(int k=i+1; k<size; k++) {
                if(arr[k] < arr[minIndex])
                    minIndex = k;
            }
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;

            printArray(arr);
        }

    }

}

---

Insertion Sort (삽입 정렬)

왼쪽을 정렬된 영역으로, 앞에서부터 차례대로 원소를 정렬된 영역의 적절한 위치에 끼워넣는다.

• 시간 복잡도 : O(n2)

public static void insertionSort(int[] arr, int size) {
        for(int i=0; i<size; i++) {
            int tmp = arr[i];
            int j = i-1;
            for(; j>=0; j--) {
                if(arr[j] < tmp)
                    break;
                arr[j+1] = arr[j];
                //printArray(arr);
            }
            arr[j+1] = tmp;
            printArray(arr);
        }

    }

두번째는 주석해제시 (과정 추가출력)

---

Bubble Sort (버블 정렬)

앞에서부터 차례대로 인접한 두 원소를 비교, 교환한다.
한 과정을 마치면 맨뒤의 원소에 가장 큰 값이 위치한다.
범위를 줄여가며 이러한 과정을 반복한다.

• 시간 복잡도 : O(n2)

public static void bubbleSort(int[] arr, int size) {
        for(int i=size-1; i>=0; i--) {
            for(int k=0; k<i; k++) {
                if(arr[k] > arr[k+1]) {
                    int tmp = arr[k];
                    arr[k] = arr[k+1];
                    arr[k+1] = tmp;

                    printArray(arr);
                }
            }
        }

    }

---

참고할만한 자료

정렬 알고리즘 정리1