[Algorithm] 기본 정렬(SORT)

[종류]
Bubble Sort
Insertion Sort
Selection Sort


[Selection Sort]

실행은 i=첫번 째 배열인자 j는 i다음의 배열인자라면,

1cycle i = 1

         j = 2, 3, 4, 5

2cycle i = 2

         j = 3, 4, 5

.....

4cycle i = 4

         j = 5

이렇게 실행된다. 

오름차순 정렬이라면 i>j클시 스왑을 실행한다.

위 그림처럼 실행시간의 최단, 최장 실행시간이 없다. 모든 인자를 거치기 때문이다.

실행시간에 따른 시간복잡도는 배열이 5개라면 첫 사이클은(n-1) + 두번 째는(n-2) ...

결국 n(n-1) / 2가 실행시간이 된다.

[ Bubble Sort ]

1cycle i = 1, 2, 3, 4     // n-1까지
         j = 2, 3, 4, 5     //i+1에서 n까지

위의 선택정렬과 같이 버블정렬도 최단, 최장 실행시간이 없이 n(n-1)/2이다.




[ Insertion Sort ]

실행은 1cycle은 1-2까지 정렬,
         2cycle은 1-3까지 정렬....
위 그림처럼 인자가 6개인 배열일 때 5cycle까지 돌면 정렬된다.

삽입정렬은 정렬되어 있는 배열에 새로운 인자 삽입시 정렬을 하기위해 쓰이는데,
위 그림처럼 앞에서 부터 사이클을 도는 것보다 뒤에서 사이클 도는게 더 효율적이다.
또한 tmp라는 임시저장하는 장소로 자신이 위치할 곳을 찾은 다음, 뒤에 있는 인자들을
적절히 밀어내어 정렬은 완성시킨다.
 

선택정렬, 버블정렬과 다르게 최장,최단 실행시간이 존재하는데,
인자가 5개인 배열일 경우
최단 시간는 5-1= 4번이다. 각각의 사이클 때 한번만에 정렬되었을 경우이다.
최장 시간는 역시 n(n-1) /2 사이클동안 인자 전부 비교했을 경우이다.