[정렬] lower bound, sorting in linear time, radix Sort, Sorting in Java

정리
bubble, selection insertion quicksort = O(n^2)
merge, heap = O(nLogn)
오늘의 결론 스포 = O(nLogn)보다 시간복잡도가 더 낮아질 수 없다.

Comparison Sort

데이터들간의 상대적 크기관계만을 이용

Non-comparison Sort

정렬할 데이터에 대한 사전지식을 이용
ex) Bucket Sort, Radix Sort

 

Counting Sort

 n개의 정수 정렬, 모든 정수는 0~k사이의 정수
(주어진 배열) A : [2,5,3,0,2,3,0,3]
(0~k까지 개수를 담는 배열) B : [2,0,2,3,0,1] //0이 2개, 1이 0개, 2가 2개...
(B에 따라 정렬, 크기는 A와 동일) C : [0,0,2,2,3,3,3,5]

int A[n];
	int B[k] = { 0, }; //처음은 0으로 초기화 //C[0], C[1], ... C[k]
	for (int i = 0; i <= n; i++)
		B[A[i]]++;
	for (int c = 1, i = 0; i <= k; i++) {
		for (int j = 0; j < B[i]; j++) {
			A[c++] = i;
		}
	}​

Radix Sort

n개의 d자리 정수들. 가장 낮은 자리수부터 정렬

Sorting in Java

String[] names = new String[] {"hyunSik","Dex","wonWoo","youngBin"};
Array.sort(names); //abc 사전순으로 sort됨

List<String> name = new ArrayList<String>();
fits.add("hyunSik");
fits.add("Dex");
fits.add("wonWoo");
fits.add("youngBin");
Collections.sort(name);

 

https://www.inflearn.com/course/lecture?courseSlug=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C&unitId=4087 

학습 페이지