220807 TIL

Today I Learned... 정렬

요즘 백준 알고리즘 문제 풀기를 하고 있다.

특히 정렬!

정렬에서 머지소트 알고리즘을 외우고 이해하려 하는데 음..외우는건 했는데 이해하는건 잘 안되네.

public class merge_sort {
	private static void mergeSort(int[] arr) {
		int[] tmp=new int[arr.length];
		mergeSort(arr,tmp,0,arr.length-1);
	}
	private static void mergeSort(int[] arr, int[] tmp,int start,int end) {
		if(start<end) {
			int mid=(start+end)/2;
			mergeSort(arr,tmp,start,mid);
			mergeSort(arr,tmp,mid+1,end);
			merge(arr,tmp,start,mid,end);
		}
	}
	private static void merge(int[] arr,int[] tmp,int start,int mid,int end) {
		for(int i=start;i<=end;i++) {
			tmp[i]=arr[i];
		}
		
		int part1= start;
		int part2=mid+1;
		int index=start;
		
		while(part1<=mid&&part2<=end) {
			if(tmp[part1]<=tmp[part2]) {
				arr[index]=tmp[part1];
				part1++;
			}else {
				arr[index]=tmp[part2];
				part2++;
			}
			index++;
		}
		for(int i=0;i<=mid-part1;i++) {
			arr[index+i]=tmp[part1+i];
		}
	}
	public static void main(String[] args) throws IOException {
		
		
	}
}

머지 소트가 시간 복잡도 O(Nlogn)으로 빠른 편이라 웬만하면 머지소트를 사용한다곤 하는데

그러면 다른 정렬 알고리즘은 전혀 쓰지 않는가..하는 생각도 든다.

어떨 때 어떤 정렬 알고리즘을 쓰는지도 공부해봐야 겠다..

 

* 안정 정렬/ 불안정 정렬

- 안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬하는 특성으로

대표적으로 삽입정렬, 병합정렬, 버블정렬이 있다.

- 불안정 정렬은 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘으로

대표적으로 퀵정렬, 선택정렬, 계수정렬이 있다.

 

안정 정렬에 속도도 빠른 머지소트를 자주 쓰지 않을까? 하는 생각이 계속 든다..

 

느낀점

꾸준히 공부해야 하는데 잘 안된다. 노력하자.

BufferedReader 공부를 더 해야겠다 이것도 잘 모르겠다.