[이것이 코딩테스트다] 5. 정렬 - 선택, 삽입, 퀵, 계수 정렬

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

정렬(Sorting)

- 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 정렬을 잘 터득하면 이진 탐색(Binary Search)가 가능하니 기초를 잘 잡아야 한다.

 

 

선택 정렬(Selction Sort) 

- 데이터가 무작위로 여러개 있을 때, 가장 작은 데이터와 맨 앞에 있는 데이터를 바꾸고 그 다음 작은 데이터를 앞에서 두번 째 데이터와 바꾸는 과정을 반복하는 알고리즘.

- '매번 가장 작은 것을 선택하는 알고리즘'

- 시간복잡도 : O(N²)    

public class Main {

	public static void main(String[] args) {
		// 선택 정렬 이용.  
		int[] arr = {8,4,5,3,9,6,7,2,1,0};
		
		int length = arr.length;
		
		for(int i=0; i<length;i++){
			int min = arr[i];
			int index = i;
			
			for(int j=i; j<length;j++) {
				if(min>arr[j]) {
					min = arr[j];
					index = j;
				}
			}
			 
			// Swap
			int temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
		
		System.out.print("정렬 결과 : ");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}

}

정렬 결과 : 0 1 2 3 4 5 6 7 8 9

 

삽입 정렬(Insertion Sort)

- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 알고리즘

- 정렬이 거의 되어있는 상태에서는 높은 효율을 보여준다.

- 시간복잡도 : O(N) ~ O(N²)    

public class insertion_sort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] arr = {8,4,5,3,9,6,7,2,1,0};
		
		for(int i=1; i<arr.length;i++) {
			 for (int j = i; j > 0; j--) {
	                
				 	// swap
	                if (arr[j] < arr[j - 1]) {
	                    int temp = arr[j];
	                    arr[j] = arr[j - 1];
	                    arr[j - 1] = temp;
	                }
	                // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
	                else break;
	            }
		}

		System.out.print("정렬 결과 : ");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}

}

정렬 결과 : 0 1 2 3 4 5 6 7 8 9

 

퀵 정렬(Quick Sort)

- 기준 데이터를 설정하고 그 기준으로 큰 데이터와 작은 데이터를 좌우로 나누는 알고리즘

- 정렬 알고리즘 중에 많이 사용되는 알고리즘

- 피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 기준

- 시간복잡도 : O(NlogN) ~ O(N²)

- 원리

1. 리스트의 첫 번째 데이터를 pivot(기준)으로 잡는다.
2. 이후 pivot의 바로 오른쪽 원소부터 pivot 보다 작은 데이터를 찾고, 리스트 끝에서부터는 pivot보다 큰 데이터를 찾는다.
3. pivot보다 작은 데이터의 index가 pivot보다 큰 데이터의 index보다 크지 않다면 방금 찾은 두 데이터의 위치를 교환 후 2번으로 돌아간다.
4. pivot보다 작은 데이터의 index가 pivot보다 큰 데이터의 index보다 크다면 pivot과 작은 데이터의 index의 위치를 교환한다.
5. pivot의 좌측, 우측의 리스트를 따로 퀵 정렬을 진행한다.

public class Main {

	public static void main(String[] args) {
		// 배열 정의
		int[] arr = {8,4,5,3,9,6,7,2,1,0};
		
		// 퀵 정렬 함수 호출
		quick_sort(arr, 0, arr.length-1);
		
		System.out.print("정렬 결과 : ");
		// 정렬된 배열 출력
		for(int i=0; i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
	}
	
	// 퀵 정렬 함수
	static void quick_sort(int arr[], int start, int end) {
		
		// 현재 리스트의 데이터 개수가 1일 경우 종료
		if(start>=end) {
			return;
		}
		
		// pivot은 시작점 
		int pivot = start;
		
		// pivot 앞에서 부터 체크
		int left = start+1;
		
		// 맨 뒤에서 체크
		int right = end;
		
		
		// 엇갈릴 때까지 반복
		// 엇갈리다? pivot보다 작은 데이터의 index가 pivot보다 큰 데이터의 index보다 큰 경우를 말한다.
		while(left <= right) {
			
			// pivot 보다 큰 수 찾기 (index 찾기)
			while(arr[left] <= arr[pivot] && left<=end) {
				left++;
			}
			
			// pivot 보다 작은 수 찾기(index 찾기)
			// start는 pivot이니 right>=start 할 필요가 없음
			while(arr[right] > arr[pivot] && right>start) {
				right--;
			}
				
			// 엇갈린 경우
			if(left > right) {
				int temp = arr[pivot];
				arr[pivot] = arr[right];
				arr[right] = temp;
			}
			// 엇갈리지 않은 경우
			else {
				int temp = arr[right];
				arr[right] = arr[left];
				arr[left] = temp; 
			}
		}
		
		// pivot 기준 좌쪽도 quick sort 진행
		quick_sort(arr, start, right-1);
		
		// pivot 기준 우측도 quick sort 진행
		quick_sort(arr, right+1, end);
	}

}

정렬 결과 : 0 1 2 3 4 5 6 7 8 9

 

계수 정렬(Count Sort)

- 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 알고리즘

- 특정 조건일 때만 사용이 가능하지만 사용한다면 매우 빠른 정렬 알고리즘

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하며 최대값과 최소값의 차이가 1,000,000을 넘지 않아야 효과적으로 사용 할 수 있다.

- 계수 정렬은 비교 기반의 정렬 알고리즘이 아니다.

(비교 기반의 정렬 알고리즘 : 선택 정렬, 삽입 정렬, 퀵 정렬 처럼 데이터를 비교하여 위치를 변경, 정렬하는 알고리즘)

- 시간복잡도 : O(N+K) 

(N : 데이터의 개수, K : 데이터의 최대값)

- 원리

1. 가장 작은 데이터와 가장 큰 데이터의 범위가 모두 담길 수 있는 하나의 리스트를 생성
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1 증가시킨다. (리스트 내의 데이터 전체 확인)
3. 체크된 리스트를 이용해 데이터를 출력한다.

public class Main {

	// 아래 배열의 가장 큰 값은 9라고 가정
	public static final int MAX_VALUE = 9;
	
	public static void main(String[] args) {
		// 배열 정의
		int[] arr = {0, 5, 8, 5, 7, 6, 1, 2, 3, 4, 4, 2, 7, 9, 3, 1, 0};
		
		// 제일 작은 값과 제일 큰 값의 사이의 데이터들이 모두 리스트에 담길 수 있도록 리스트 생성
		int[] cntArr = new int[MAX_VALUE+1];
		
		// 배열의 데이터 값과 동일한 인덱스의 데이터를 하나씩 증가.
		for(int i=0;i<arr.length;i++) {
			cntArr[arr[i]]++;
		}
				
		System.out.print("정렬 결과 : ");
		// 기록된 리스트를 아래와 같이 출력
		for(int i=0;i<cntArr.length;i++) {
			for(int j=0; j<cntArr[i];j++) {
				System.out.print(i+" ");
			}
		}
	}

}

정렬 결과 : 0 0 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9

 

 

다음 장에서는 정렬을 이용한 알고리즘 문제를 풀어보도록 하겠습니다.