정렬 알고리즘 비교

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

정렬 알고리즘 비교

정렬 알고리즘 시간복잡도

Sort Algorithm	T(n)
Bubble Sort	Θ(n2)
Insertion Sort	Θ(n2)
Selection Sort	Θ(n2)
Quick Sort	Worst Θ(n2) and Average Θ(nlon2n)
Merge Sort	Θ(nlon2n)
Heap Sort	Θ(nlon2n)
Counting Sort	Θ(n+k)
Radix Sort	Θ(d(n+k))

Java에서의 정렬

Sorting in Java

기본 타입 데이터의 정렬

Arrays 클래스가 Primitive 타입 데이터를 위한 정렬 메서드를 제공

int 이외의 다른 Primitive 타입 데이터(double, char 등)에 대해서도 제공

int [] data = new int[capacity];	
Arrays.sort(data);	// 데이터가 꽉 차있는 경우
Arrays.sort(data, 0, size);	//데이터가 꽉 차있지 않고 size 개의 데이터만 있는 경우

- ArrayList 정렬 : 문자열

List<String> fruits = new ArrayList<String>();
fruits.add("Pineapple");
fruits.add("Apple");
fruits.add("Orange");
fruits.add("Banana");
Collections.sort(fruits);
	for(String name : fruits) {
		System.out.println(name);
	}

Collections.sort 메서드로 정렬된다.