[Java] 정렬 알고리즘(Sort Algorithm)

 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

 

 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary search)가 가능해진다. 이진 탐색은 정렬이 되어있어야 사용할 수 있기 때문이다. 즉 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다.

 

 

학습 목표

---

1. 선택 정렬(Selection Sort)
2. 삽입 정렬(Insert Sort)
3. 큌 정렬(Quick Sort)
4. 계수 정렬(Count Sort)
5. 버블 정렬(Bubble Sort)

 

1. 선택 정렬(Selection Sort)

---

 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

 

 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
    N + (N-1) + (N-2) + ... + 2
이는 (N**2 + N -2) / 2로 표현할 수 있는데, 빅오 표기법에 따라서 O(N**2)이라고 작성합니다.

 

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {
		
		int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
		
		int min_index;
		for(int i=0; i<arr.length; i++) {
			min_index = i;
			for(int j=i; j<arr.length; j++) {
				if(arr[j] < arr[min_index])
					min_index = j;
			}
			
			int temp = arr[i];
			arr[i] = arr[min_index];
			arr[min_index] = temp;
		}
		
		System.out.println(Arrays.toString(arr));
		
	}

}

 

 

2. 삽입 정렬(Insert Sort)

---

 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 삽입 정렬이 이루어진 원소는 항상 오름차순을 유지하는 특징이 있다.

선택 정렬에 비해 구현 난이도가 높은 편이지만, 조금 더 효율적으로 동작한다.

 

 삽입 정렬은 시간 복잡도는 O(N**2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있을수록 더 빠르게 동작한다.

 

 최선의 경우 O(N)의 시간 복잡도를 가진다.

 

import java.util.Arrays;

public class InsertSort {

	public static void main(String[] args) {

		int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
		
		for(int i=1; i<arr.length; i++) {
			for(int j=i; j>=1; j--) {
				if(arr[j]<arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}else
					break;
			}
			
		}
		
		System.out.println(Arrays.toString(arr));
		
	}

}

 

 

3. 퀵 정렬(Quick Sort)

---

 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.

 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.

 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있다. 너비 x 높이 = N x logN
하지만 최악의 경우 O(N**2)의 시간 복잡도를 가진다.

 

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		
		int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
			
		quickSort(arr, 0, arr.length-1);
		
		System.out.println(Arrays.toString(arr));
	}
	
	public static void quickSort(int[] arr, int start, int end) {
		
		if(start >= end)
			return;
		
		int pivot = start;
		int left = start +1;
		int right = end;
		
		while(left <= right) {
			
			while(left <= end && arr[left]<=arr[pivot])
				left += 1;
			
			while(right > start && arr[right] >= arr[pivot])
				right -= 1;
			
			if(left>right) {
				int temp = arr[right];
				arr[right] = arr[pivot];
				arr[pivot] = temp;
			}else {
				int temp = arr[right];
				arr[right] = arr[left];
				arr[left] = temp;
			}
		}
		
		quickSort(arr, start, right-1);
		quickSort(arr, right+1, end);
	}
	
}

 

 

4. 계수 정렬(Count Sort)

---

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
    계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
    데이터가 0과 999,999로 단 2개만 존재하는 경우를 생각해 보면된다.
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 떄 효과적으로 사용할 수 있다.
    성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다.

 

public class CountSort {

	public static void main(String[] args) {
		
		int arr[] = {7, 5 , 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};		
		int[] count = new int[10];
		
		for(int i=0; i<arr.length; i++) {
			count[arr[i]] += 1;
		}
		
		for(int i=0; i<count.length; i++) {
			for(int j=0; j<count[i]; j++)
				System.out.print(i + " ");
		}
	}

}

 

 

5. 버블 정렬(Bubble Sort)

---

 거품 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다.

 

그리고 이전에 다뤘던 선택 정렬과는 달리 거품 정렬은 앞에서부터 차례대로 비교하기 때문에 '안정 정렬'이기도 하다.

public class BubbleSort {
    public static void main(String[] args) {

        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for(int i = 0; i < arr.length; i++) {
            for(int j = 0 ; j < arr.length - i - 1 ; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        for(int i : arr) {
            System.out.print(i+" ");
        }

    }
}