버블/단순 선택/단순 삽입 정렬

정렬에서 사용하는 swap 메소드는 아래와 같이 구현하면 된다.

// a[idx1]와 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

1. 버블(Bubble) 정렬

    //length가 n 인 배열 a 을 버블정렬한다.
    static void bubbleSort(int[] a, int n) {
        //정렬을 마친 부분을 저장한다.
        int k = 0; // a[k]보다 앞쪽은 정렬은 마친 상태

        while (k < n - 1) {
            int last = n - 1; // 마지막으로 요소를 교환한 위치
            for (int j = n - 1; j > k; j--) //
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    last = j; 
                }
            k = last; 
        }
    }

    // 양방향 버블 정렬(셰이커 정렬)
    static void shakerSort(int[] a, int n) {
        int left = 0;
        int right = n - 1;
        int last = right;

        while (left < right) {
            for (int j = right; j > left; j--) {
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    last = j;
                }
            }
            left = last;

            for (int j = left; j < right; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    last = j;
                }
            }
            right = last;
        }
    }

2. 단순 선택 정렬
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.

// 1. 가장 작은 요소의 값을 선택.
// 2. 아직 정렬하지 않은 부분의 첫번째 요소를 교환한다.
static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[min] > a[j]) //최소값의 인덱스를 for 루프를 통해 찾았으면
                min = j; //해당 j(인덱스)를 min 에 저장
        swap(a, i, min); //아직 정렬되지 않은 부분과 min을 교환한다.

    }
}

3. 단순 삽입 정렬
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.

public class InsertionSort {
    //단순 삽입 정렬
    static void insertionSort(int[] a, int n) {
        for(int i = 1; i < n; i++) {
            int j;
            int tmp = a[i]; //2번째 요소부터 선택하고 임시저장
            //tmp와 배열의 값을 하나씩 비교하여 앞이 더 크면 그 값을 뒤로 복사한다.
            for (j = i; j > 0 && a[j - 1] > tmp ; j--)
                a[j] = a[j - 1];
            //a[j - 1] <= tmp 인 경우 for 문을 탈출
            a[j] = tmp; // j인덱스 자리에 tml 값을 삽입
        }
    }

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

        System.out.println("단순 삽입 정렬");
        System.out.print("요솟수:");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = stdIn.nextInt();
        }

        insertionSort(x, nx); //배열 x를 단순 삽입 정렬 합니다.

        System.out.println("오른차순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]= " + x[i]);
        }
    }
}