[Java] 정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

👉 인접한 두 자료를 비교하며 자리를 교환하는 방식

📌 방법

• 첫번째 원소와 두번째 원소를 비교 정렬
• 두번째 원소와 세번째 원소를 비교 정렬
• n-1번째 원소와 n번째 원소를 비교 정렬
• 한번의 정렬 사이클이 끝나면 가장 큰 원소(제일 오른쪽 원소)의 정렬이 끝남
• 따라서 두번째 정렬 사이클은 n-1번만 시행

✨ 버블 정렬 코드

public static void main(String[] args) {
	int[] arr = {36, 12, 18, 15, 41, 19};
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
    	for (int j = 0; j < n -1 -i; j++) {
        	// 왼쪽 원소가 오른쪽 원소보다 클 경우 교환
            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));
}

🚧 결과

[12, 15, 18, 19, 36, 41]

2. 선택 정렬 (Selection Sort)

👉 주어진 자료 중 제일 작은 숫자를 골라서 앞으로 정렬하는 방식

📌 방법

• 자료 전체를 확인해 제일 작은 값을 찾아, 제일 앞의 원소와 교환한다. 이 과
  정이 끝나면 제일 앞의 원소는 정렬이 끝남
• 이후 정렬되지 않은 원소들을 기준으로 같은 작업을 정렬이 안된 원소가 없
  을 때까지 반복

❗버블 정렬과의 차이점

🔸 버블 정렬은 5번의 비교 중 4번의 교환이 일어남
🔸 선택 정렬은 6번의 비교 중 1번의 교환이 일어남

✨ 선택 정렬 코드

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++) {
    	int minIndex = i;
        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.toStirng(arr));
}

🚧 결과

[2, 12, 18, 21, 24, 25]

3. 계수 정렬 (Counting Sort)

👉 각 자료가 몇 개가 존재하는지 정리한 뒤 그 정보를 활용해 정렬하는 방식

📌 방법

• 먼저 자료들의 값의 범위 만큼의 공간을 가진 counts 배열을 만듦
  (자료가 0 ~ 9 사이라면, int[] counts = new int[10];)
• 자료의 각 데이터(data)를 확인하여, counts[data] 의 값을 하나 더해줌
• 이 과정이 끝나면 counts[data] 에는 data가 몇개인지가 저장
• 첫번째 원소부터 시작하여 counts 배열의 앞쪽 원소의 값을 뒤에 합해줌
• 이후 본래의 자료 데이터(data)를 순회하여, counts 배열에 따라 결과를 정리함

✨ 선택 정렬 코드

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];
    
    for (int data: arr) {
    	counts[data]++;
    }
    System.out.println("Counts: " + Arrays.toString(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];
    for (int i = n - 1; i >= 0; i--) {
    	counts[arr[i]]--;
        int position = counts[arr[i]];
        output[position] = arr[i];
    }
    
    System.out.println("결과: " + Arrays.toString(output));
}

🚧 결과

Counts: [2, 2, 1, 1, 2, 2]
누적합: [2, 4, 5, 6, 8, 10]
결과: [0, 0, 1, 1, 2, 3, 4, 4, 5, 5]