20250915 정렬 알고리즘

정렬 알고리즘

버블 정렬

버블 정렬은 인접한 두 개의 원소를 비교한 후 교환하는 과정을 반복하여 데이터를 정렬하는 방식이다.

교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.

 

1. 첫 번째 원소부터 인접한 원소와 비교하여 자리를 교환해가면서 마지막 자리까지 이동한다.

2. 기준(오름차순)한 사이클이 끝나면 가장 큰 원소가 마지막 자리로 위치하게 된다.

 

이를 코드로 표현할 때 가장 중요한 포인트는 한 사이클을 돌면 무조건 가장 큰 원소가 마지막 자리에 위치하게 된다는 것이다.

그 말은 맨 마지막은 비교를 하지 않아도 되기 때문에 정렬을 해야되는 원소 갯수에서 한 사이클이 지나갈 때마다 비교횟수도 하나씩 줄어든다는 얘기다. 그리고 그 위치는 마지막이다.

 

무작위 수를 오름차순으로 버블 정렬로 정렬한다고 하면,

전체 사이클의 횟수는 N(원소 갯수) - 1이 된다.

그리고 사이클 내부의 비교 반복은 N - 1에서 사이클의 횟수가 증가할 때마다 하나씩 줄게 된다.

 

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		
		int[] arr = {55, 7, 78, 12, 42};
		// 정렬 전
		System.out.println(Arrays.toString(arr));
		int n = arr.length;
		
		for (int i = n - 1; i > 0; i--) {
			for (int j = 0; j < 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));
	}
}

이중 for문에서 밖의 for문은 사이클의 반복을 뜻하고 안의 for문은 비교 반복을 하는 역할이 된다.

i에 처음에 N - 1의 값을 할당하면서 N - 1만큼 반복하게 된다. j에는 처음 0이 할당되고 i의 값만큼 비교를 반복한다.

 

결론: 사이클은 N - 1의 반복이고 비교 반복은 사이클마다 1번씩 줄어든다는 얘기다.

 

// i가 0부터 시작했을 때
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;
        }
    }
}

 

선택 정렬

선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 앞의 데이터와 교환해나가는 방식이다.

시간 복잡도는 O(n^2)이다.

정렬 과정

1. 주어진 자료들 중 최소값을 찾는다.

2. 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.

3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

 

버블 정렬과 마찬가지로 한 사이클이 지나면 비교 반복 횟수가 하나씩 줄어든다. 총 사이클 횟수는 자료 갯수보다 하나 더 적다.

 

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {
		
		int[] nums = {64, 25, 10, 22, 11};
		int n = nums.length;
		
		// 정렬 전
		System.out.println(Arrays.toString(nums));
		
		for (int i = 0; i < n - 1; i++) {
			int minIdx = i;
			
			for (int j = i + 1; j < n; j++) {
				if (nums[minIdx] > nums[j]) {
					minIdx = j;
				}
			} // end inner for문
			
			// swap
			if (minIdx != i) {
				int temp = nums[i];
				nums[i] = nums[minIdx];
				nums[minIdx] = temp;
			}
		} // end outer for문
		
		// 정렬 후
		System.out.println(Arrays.toString(nums));
	}
}

최소값을 찾은 후 앞에 계속 놓기 때문에 j는 사이클 횟수인 i보다 1큰 값부터 시작하게 된다.

 

삽입 정렬

삽입 정렬은 정렬할 요소를 뒤에 있는 요소와 비교한 뒤 스왑이 일어났다면 앞에 있는 모든 요소와도 비교를 하는 방식이다.

시간 복잡도는 O(n^2)이다.

 

정렬 과정

1. 배열의 첫 번째 요소는 이미 정렬된 상태라고 가정한다.

2. 배열의 두 번째 요소(key)부터 시작하여 앞 칸의 요소가 더 크면 스왑한다.

3. 이것을 맨 앞 요소까지 반복한다.

 

import java.util.Arrays;

public class insertSort {

	public static void main(String[] args) {
		int[] arr = {23, 1, 10, 5, 2};
		int n = arr.length;
		
		for(int i = 1; i < n; i++) {
			
			int key = arr[i];
			int j = i - 1;
			
			while(j >= 0 && arr[j] > key) { // 삽입 위치 찾기
				arr[j + 1] = arr[j];
				j--;
			}
			
			arr[j + 1] = key;
		}
		
		System.out.println(Arrays.toString(arr));
	}
}

첫 번째 요소는 정렬된 요소로 가정하기 때문에 두 번째 인덱스부터 배열 길이까지 반복하게 된다.

 

key가 앞칸의 요소보다 작으면 j를 줄이면서 넣을 인덱스를 찾는다. 더이상 갈 인덱스가 없거나 key보다 앞 쪽 요소가 더 작으면 멈추게 된다. 

 

카운팅 정렬

카운팅 정렬은 요소가 몇 번씩 등장하는지 세는 방법으로 정렬하는 알고리즘이다.

시간복잡도는 O(n)이다.

 

정렬 방법

1. 원본 배열에서 요소가 몇 번 등장하는지를 counting 배열이라는 새로운 배열에 저장한다. 이 때 원본 배열의 요소가 카운팅 배열의 인덱스가 되게 한다.

2. 카운팅 배열을 가지고 누적합을 계산한다.

3. 완성된 누적합 배열을 가지고 결과 배열을 생성한다.

 

import java.util.Arrays;

public class CountingSort {

	public static void main(String[] args) {
		int[] arr = {7, 2, 3, 5, 7, 1, 4, 6, 7, 5, 0, 1};
		int n = arr.length;
		int max = 7;
		
		int[] count = new int[max + 1];
		int[] result = new int[n];
		
		for (int num: arr) {
			count[num]++;
		}
		
		for (int i = 1; i <= max; i++) {
			count[i] += count[i - 1]; 
		}
		
		for (int i = n - 1; i >= 0; i--) {
			result[count[arr[i]] - 1] = arr[i];
			count[arr[i]]--;
		}
		
		System.out.println(Arrays.toString(result));
	}
}

배열의 값들 중 가장 큰 값을 주어져있다고 가정한다.

 

가장 큰 값의 길이보다 1큰 배열을 생성하는데 인덱스에 값의 정보가 담기기 때문이다.

그리고  count배열을 누적합 배열로 바꾸어주고 원래 병을 뒤에서부터 확인하면서, count 배열을 이용해 자기 자리를 찾아 결과 배열에 넣는다.

 

비교를 하지 않고 정렬을 하기 때문에 속도가 엄청 빠르다. 하지만 범위가 너무 크면 메모리 낭비가 심해져서 비효율적이다.

값의 범위가 크지 않을 때 매우 효율적이다.

 

병합 정렬

분할 정복 알고리즘으로 정렬하는 방식이다.

시간 복잡도는 O(nlogn)이다.

 

정렬 방법

1. 원본 배열을 쪼갠다. 최소 단위가 될 때까지 쪼갠다.

2. 각 요소를 합하면서 비교하고 새 자리를 차지한다.

 

public class MergeSort {
	
	private static void divide(int[] array) {
		if (array.length < 2) {
			return;
		}
		
		int mid = array.length / 2;
		int[] left = Arrays.copyOfRange(array, 0, mid);
		int[] right = Arrays.copyOfRange(array, mid, array.length);
        
		divide(left);
		divide(right);
		
		mergeSort(array, left, right);
	}
	
	private static void mergeSort(int[] array, int[] left, int[] right) {
		
		int i = 0, j = 0, k = 0;
		
		while(i < left.length && j < right.length) {
			if (left[i] <= right[j]) {
				array[k++] = left[i++];
			} else {
				array[k++] = right[j++];
			}
		}
		
		while(i < left.length) {
			array[k++] = left[i++];
		}
		
		while(j < right.length) {
			array[k++] = right[j++];
		}
		// 정렬 후
		System.out.println(Arrays.toString(array));
	}

	public static void main(String[] args) {
		int[] array = {38, 27, 43, 3, 9, 82, 10};
        // 정렬 전
		System.out.println(Arrays.toString(array));
		divide(array);
	}
}

divide()에서 배열을 반으로 계속 쪼개기 때문에 깊이가 log n이 되고 각 단계에서 mergeSort()가 배열 전체를 한 번 스캔하면서 병합하기 때문에 비교 복사가 최대 n번 일어난다. 그래서 시간 복잡도는 nlogn이 된다.

 

divide() 는 배열을 반으로 쪼개서 left/right를 만든 뒤, 각각에 대해 재귀적으로 divide를 호출한다.

그 내부에서 더 이상 쪼갤 수 없을 때 리턴하고 다 쪼개진 뒤에 mergeSort()를 호출해 병합을 수행한다. 이 병합 완료 후 배열 상태를 출력한다. 

 

퀵 정렬

병합 정렬처럼 분할 정복 알고리즘으로 정렬하는 방식이다.

시간 복잡도는 최악은 O(n^2)이지만 평균적으로 O(nlogn)이어서 빠른 알고리즘으로 간주된다.

정렬 과정

1. 피벗 선택: 배열에서 하나의 요소를 피벗으로 선택한다. 보통 배열의 마지막 요소를 선택한다.

2. 파티션: 피벗을 기준으로 배열을 두 개의 부분으로 나눈다. 피벗보다 작은 요소들은 왼쪽에 큰 요소들은 오른쪽에 위치하도록 재배치 한다.

3. 재귀 호출: 피벗의 위치가 정해지면, 피벗을 제외한 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다.

4. 종료 조건: 배열의 크기가 1이 되면 정렬이 완료된 것으로 간주한다.

 

import java.util.Arrays;

public class QuickSort {

	private static void partition(int[] array, int lowIndex, int highIndex) {
		if (lowIndex < highIndex) {
			int pivotIndex = quickSort(array, lowIndex, highIndex);
			
			partition(array, lowIndex, pivotIndex - 1);
			partition(array, pivotIndex + 1, highIndex);
		}
	}
	
	private static int quickSort(int[] array, int lowIndex, int highIndex) {
		int pivot = array[highIndex];
		System.out.println("현재 피벗 값:" + pivot);
		
		int i = lowIndex - 1;
		for (int j = lowIndex; j < highIndex; j++) {
			if (array[j] < pivot) {
				i++;
				swap(array, i, j);
			}
		}
		
		swap(array, i + 1, highIndex);
		
		return i + 1;
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int[] array = {8, 4, 3, 1, 6, 7, 11, 9, 2, 10, 5};
		
		partition(array, 0, array.length - 1);
		System.out.println(Arrays.toString(array));
	}
}

병합 정렬은 가운데부터 반으로 계속 나누지만 퀵정렬은 pivot을 선택해서 이를 기준으로 낮은 값은 왼쪽 높은 값은 오른쪽으로 배치하고 재귀적으로 똑같이 반복한다.

 

자바 API

Arrays.sort( )

자바 API인 Arrays.sort는 O(nlogn)의 시간 복잡도를 가진다.

그 이유는 merge 혹은 tim 정렬을 사용하기 때문이다. 그래서 Arrays.sort를 활용하여 정렬하는 것이 효율성이 훨씬 좋다.

 

Collections.sort()

Arrays.sort는 배열(array) 정렬용이라면 Collections.sort는 컬렉션(List) 정렬용이다.

내부적으로 List를 배열로 변환 후 Arrays.sort를 호출한다. 사실상 동일하다고 볼 수 있다.