7/1 정렬 알고리즘

정렬	설명	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정 정렬 여부
선택정렬	제일 작은 것부터 선택해서 앞에서부터 정렬	O(n²)	O(n²)	O(1)	불안정
삽입정렬	현재 값을 자기 위치에 삽입해서 정렬	O(n²)	O(n²)	O(1)	안정
버블정렬	앞에서부터 인접한 두 값을 비교하고 위치를 바꿔가며 정렬	O(n²)	O(n²)	O(1)	안정
병합정렬	배열을 계속 반으로 분할한 뒤, 작은 단위부터 다시 병합하면서 정렬	O(n log n)	O(n log n)	O(n)	안정
퀵정렬	기준값인 피벗을 정하고, 피벗보다 작은 값과 큰 값으로 나누며 정렬	O(n log n)	O(n²)	O(log n)	불안정
힙정렬	데이터를 힙 구조로 만든 뒤, 가장 큰 값부터 꺼내며 정렬	O(n log n)	O(n log n)	O(1)	불안정
인트로정렬	퀵정렬을 기본으로 쓰다가 최악 상황에서는 힙정렬, 작은 구간에서는 삽입정렬 사용	O(n log n)	O(n log n)	O(log n)	불안정

※ 안정정렬 - 같은 값끼리의 기존 순서가 정렬 후에도 유지되는 정렬

C#은 인트로 정렬을 채택함

인트로 정렬 IntroSort

퀵정렬을 기본으로 사용하다가,

재귀 깊이가 너무 깊어져서 최악 상황이 예상되면 힙정렬로 전환하고,

작은 구간에서는 삽입정렬을 사용하는 하이브리드 정렬

 

Linq : 데이터 베이스 쿼리 방식의 필터링 기법

예제

var result = from monster in monsters where monster.hp >= 5 orderby monster.name ascending select monster;