정렬은 내부정렬과 외부 정렬이 있는데,
내부 정렬은 대상 자료를 모두 기억 장소에 읽어들여 정렬하는 것으로 Bubble,Selection,Insertion,Shell,Quick,Radix,Heap,Merge등이 있고 외부 정렬은 자료의 일부분만 기억장소에 읽어 들여 정렬하는 방법으로, 벨런스트, 캐스캐이드, 다상, 오실레이팅병합 정렬이 있다.
내부 정렬
1. Bubble Sorting
두개의 자료를 비교하여 자료를 맞바꾸는 방식으로 정렬
31, 15, 44, 13, 22가 있을 경우
31과 15를 비교하여 15,31,44,13,22로 <--1회 비교
31과 44를 비교하여 15,31,44,13,22로
44와 13을 비교하여 15,31,13,44,22로
44와 22를 비교하여 15,31,13,22,44로
15와 31을 비교하여 15,31,13,22,44로 <--2회 비교
31과 13을 비교하여 15,13,31,22,44로
31과 22를 비교하여 15,13,22,31,44로
15와 13을 비교하여 13,15,22,31,44로 <--3회 비교
...(이쯤 되면 미치기 시작한다..) 딱 봐도 멍청해 보이는 알고리즘으로 이중 For문으로 구현되며 최악의 소팅으로 O(n^2) 의 알고리즘이다.
2. Selection Sorting
자료중 가장 작은(혹은 가장 큰) 값을 선택하여 이를 앞부분으로 이동하는 방식의 정렬
31, 15, 44, 13, 22가 있을 경우
31이후의 최소값을 찾음(13) 교환 13,15,44,31,22 <--1회 비교
15이후의 최소값을 찾음(15) 교환 13,15,44,31,22 <--2회 비교
44이후의 최소값을 찾음(22) 교환 13,15,22,31,44 <--3회 비교
31이후의 최소값을 찾음(31) 교환 13,15,22,31,44 <--4회 비교
정렬 끝. 위 bubble소트보다는 낮다. 기본적으로 인간의 뇌로 하는 정렬인데 그리 좋지는 않다. 기본적으로 이중 For문으로 돌아가며 O(n^2)인 알고리즘이다.
3. Insertion Sorting
자료의 크기를 비교하여 삽입하는 방식으로 정렬. 예를 들어 정렬된 카드에 어느 한 카드를 삽입할경우를 생각해 보면 된다.
31, 15, 44, 13, 22가 있을 경우
15를 31과 비교 15<31이므로 15를 31이 삽입 15,31,44,13,22
44를 31과 비교 31<41이므로 변화 없음(41보다 31이 작으므로 중지) 15,31,44,13,22
13을 44와 비교 13<44, 13<31, 13<15이므로 15자리에 13삽입, 13,15,31,44,22
22와 44를 비교 22<44, 22<31 이므로 31자리에 22를 삽입, 13,15,22,31,44 정렬 완료
정렬끝. 배열의 이동은 기본적으로 O(N)이므로 O(N^2)가 된다.
