[시리즈] 프로그래밍 기초 공부
· 내가 되새기기 위해써보는 C# 기초-1


글의 목표

기초 알고리즘을

비교정렬과 비비교정렬

10가지 정리하기


일반적으로 정렬은


2가지 범주로 나뉜다.


비교 정렬(Comparison Sorting)

비교를 통해 요소간의 상대적 순서를 결정함. 시간 복잡도는 O(n log n)이 시간 하한임


o(nlong)이하로는 왜 불가능한가?

비교 정렬은 데이터의 가능한 모든 순열에 대한 올바른 순서를 찾는것


결정 트리모델을 이용하여 비교횟수의 최솟값 계산시, log2(n!)이 되는데


이를 스탈링 근사를 이용할 경우 log2(n!)≈nlog2n으로 근사된다. 따라서 최소 시간 복잡도는 O(n log n)인것



비-비교 정렬(Non-Comparison Sorting)

비교를 통한 요소간의 상대적 순서를 결정하지 않고, 비교 기반 정렬의 시간 하한을 돌파하고 선형시간으로 실행할 수 있으므로,


시간 하한을 돌파한다-> 비교 기반 정렬 알고리즘의 시간 복잡도 하한선인 O(n log n)을 넘어선다는 이야기임.

비교 연산과 다르게 '비교'를 하지 않고, 분류, 카운팅등의 연산을 사용함 따라서 이때문에 비교 연산과는 다른 접근법을 지님.

즉 비-비교 정렬알고리즘은 비교 정렬의 이론적인 시간 복잡도 하한을 돌파하여 더 빠른 정렬을 가능하게함



그럼 자주쓰이는 알고리즘 10가지는 뭐가 있을까?



22add535abc236a14e81d2b628f175654734d7


들어가기 앞서 시퀀스(Sequence) 정렬된 부분의 연속된 요소, 정렬된 부분(arranged part)를 뜻함.


보통 이 시퀀스 개념을 아느냐 모르느냐로 정렬의 이해도가 쉬워짐. 보통 수식부터 이해하라고 하지만

나는 이 시퀀스를 어떻게 정렬하느냐로 접근하는 문제라고 이해하는게 나은거 같음. 

수학적 이해도도 물론 중요하지만, 역시 시퀀스라는 개념적 이해가 초보자에게 필요하다 생각함.


디시 특성상 코드 올리기가 마땅치 않으므로 어차피 검색하면 나오는 기초 알고리즘이니까

개인적으로 생각하는 개념의 핵심적 이해만 써봄.



2fa8d224e9d775b561adc2f8479f3338879176818d4e7c8c3ae9eca2e9


1. 버블 정렬(Bubble Sort)


버블 정렬은 간단한 정렬 알고리즘임, 정렬한 순서를 반복적으로 살펴보고, 한번에 2개의 요소를 비교하고 순서가 잘못된 경우 교체.

더이상 교체가 필요하지 않을때까지, 배열의 방문 작업을 반복함. 즉 배열이 정렬될때까지 반복됨.

이 알고리즘의 이름은 작은 요소가 스왑을 통해서 배열의 맨위로 천천히 'bubble(거품)'처럼 떠오른다에서 유래됨


(보통 맨 위라고 하기보다는 배열의 끝으로 라고 하긴 하는데, 버블이라는 표현이 생긴 이유가 저때문이라 굳이 배열의 맨위라고 적음)


24aec868e2db3e8650bbd58b3685766f7aa3

(선택정렬 애니메이션)


2.선택 정렬(Selection Sort)


선택 정렬은 간단하고 직관적인 정렬

먼저 정렬되지 않은 시퀀스에서 가장 작은(또는 큰) 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장,

나머지 정렬되지 않은 요소에서 가장 작은(큰)요소를 계속 찾아서 정렬된 시퀀스 끝에 배치함. 모든 요소가 정렬될때까지 진행

(일반적으로 가장 이해하기 쉬워서 보통은 선택 정렬을 먼저 공부하는 것을 다들 많이 추천함. )



22a5c568e2db3e8650bbd58b3680776a6ea259

(삽입 정렬)


3.삽입 정렬(Insertion Sort)


정렬된 시퀀스를 구성하고 정렬되지 않은 데이터의 경우 정렬된 시퀀스에서 뒤에서 앞으로 스캔하여 적절한 위치를 찾아 삽입하는 방식으로 작동.


정렬된 시퀀스->현재까지 정렬이 완료된 요소들의 집합. 알고리즘이 진행됨에 따라서 점점 확장됨.



22aec968e2db3e8650bbd58b3683736b13cfb4


4. 쉘 정렬(Shell Sort)


쉘 정렬은 1959년 Shell에 의해 발명된 최초의 O(n2)를 깨는 정렬 알고리즘임.

단순 삽입 정렬의 개선버전임.

삽입 정렬과 다른점은 더 멀리 떨어져 있는 요소를 우선적으로 비교함.



22a4c868e2db3e8650bbd58b3689756ddb9c


5.병합정렬 (Merge Sort)


병합 정렬은 분할-정복 기법을 사용하는 알고리즘(divide and conquer)을 사용한 효율적 알고리즘.

이미 정렬된 시퀀스를 병합하여, 더 완전히 정렬된 시퀀스를 얻음. 즉 각 시퀀스가 먼저 정렬된 다음, 시퀀스 세그먼트(부분)이 서로 정렬됨.

즉 병합정렬은 배열을 절반으로 나누어, 재귀적으로 정렬한 후, 정렬된 부분 배열을 병합하는 방식으로 씀.

정렬된 두 테이블이 하나의 정렬된 테이블로 병합(Merge)되는 것을 병합과정이라고 함




다시 작업하러가야되서 여기까지