버블정렬, 선택정렬, 계수정렬 알고리즘

버블정렬

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 첫번째-두번째와 두번째-세번째, 세번쨰-네번째 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
• 이해하지 쉽고 구현도 쉽지만, 시간복잡도가 O(n^2)이기 때문에 비효율적이다.
•  

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
    int[] arr = {36, 12, 18, 15, 41, 19};
    int n = arr.length;
        //첫번째 원소와 인접한 원소를 비교,
        //두번째 원소와 세번째 원소를 비교
        // ...
        // n-1번째 원소와 n번째 원소를 비교
        for (int i = 0; i < n - 1; i++) { //반복 횟수를 나타내는 몇번째 단계인지 n-1
            for (int j = 0; j < n - 1 - i; j++) { //n-1-i
                //왼쪽 원소가 오른쪽 원소보다 클 경우 교환한다.
                if(arr[j] > arr[j + 1]){
                    //교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

선택정렬

• 주어진 수 중에서 가장 작은 숫자를 골라서 제일 앞으로 보내는 방식으로 정렬하는 방법

package algorithm;

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[]arr = {25,12,18,24,2,21};
        int n = arr.length;
        //제일 작은 원소를 찾아서 앞으로 보낸다.
        for (int i = 0; i < n - 1; i++) { //i의 값이 총 정렬된 원소의 갯수
            //제일 앞에 원소를 제일 작은 숫자 설정
            int minIndex = i;
            //i + 1부터 끝 원소까지 차근차근 비교한다.
            for (int j = i + 1; j < n ; j++) {
                //제일 작은 숫자를 찾는다.
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
            }
            }
            //제일 앞의 원소와 제일 작은 원소를 교환한다.
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

계수정렬

• 정렬하고자 하는 자료의 형태가 정수의 형태일 때 적용할 수 있는 정렬
• 자료의 정수들이 각각 얼마나 등장했는지를 기록하는 counts 배열을 만든 다음, 그 정보를 바탕으로 정렬을 시행하는 방법

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {0, 1, 4, 4, 3, 0, 5, 2, 5, 1};
        int n = arr.length;

        //최대값 최소값 찾기
        int max = 5;
        int min = 0;
        int k = max - min + 1;

        //자료가 몇번 등장했는지 기록용 배열
        int[] counts = new int[k];

        //counts 배열 채우기
        for (int data : arr) {
            counts[data]++;
        }
        System.out.println(Arrays.toString(counts));

        //counts 누적합
        for (int i = 0; i < k - 1; i++) {
            //counts[i+1] = counts[i+1] + counts[i]
            counts[i + 1] += counts[i];
        }
        System.out.println(Arrays.toString(counts));

        int[] output = new int[n];
        // 뒤에서 부터 순회하여 output에 저장
        for (int i = n-1; i >= 0; i--) {
            // 현재 데이터를 인덱스로 counts배열에 데이터 값 회수
            counts[arr[i]]--;
            int position = counts[arr[i]];
            output[position] = arr[i];

        }
        System.out.println(Arrays.toString(output));
    }
}