1.버블정렬(Bubble Sort)
=>인접한 두개의 데이터를 비교해가면서 정렬을 진행하는 방식
*성능 평가 :비교의 횟수, 이동의 횟수
:정렬기준이 역순으로 저장된 상태라면 비교 횟수와 이동횟수가 일치하기 때문에 최악의 경우
: O(n2)
ex) 3 2 4 1 오름차순으로 정렬해보자
[버블정렬 1/3]
1) 3 2 4 1 ->2 3 4 1 (1번과 2번 비교)
2) 2 3 4 1 ->2 3 4 1 (2번과 3번 비교)
3) 2 3 4 1-> 2 3 1 4 (3번과 4번 비교)
[버블정렬 2/3] :위의 과정을 다시 반복
1)2 3 1 4 -> 2 3 1 4(1번과 2번 비교)
2)2 3 1 4 -> 2 1 3 4(2번과 3번 비교)
3)2 1 3 4 -> 2 1 3 4(3번과 4번 비교)
[버블정렬 3/3] :위의 과정을 다시 반복
1)2 1 3 4-> 1 2 3 4(1번과 2번 비교)
<소스>
2.선택정렬(Selection Sort)
=>정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이되게하는 알고리즘
:정렬순서상 가장 앞서는거 선택해서 가장 왼쪽으로 이동시키고,원래 그자리에 있던 데이터는 빈 자리에 가져다 놓는다.
*성능 평가 :비교의 횟수, 이동의 횟수
:버블정렬과 성능차이가 없다.
: O(n2)
정렬 결과 | 정렬대상
| 1 2 4 3
1 | 2 4 3
1 2 | 4 3
1 2 3 | 4
1 2 3 4 |
오른쪽에서 왼쪽으로 옮기기
ex) 3 4 2 1 오름차순으로 정렬해보자
[선택 정렬]
3 4 2 1 -> 1 4 2 3 (1번과 4번 교환)
1 4 2 3 -> 1 2 4 3 (2번과 3번 교환)
1 2 4 3 -> 1 2 3 4 (3번과 4번 교환 )
<소스>
3.삽입정렬(Insertion Sort)
=>개선된 선택정렬
1 2 4 7 5 3
정렬 O 정렬 X
=>위 그림의 배열은 정렬이 완료된 부분과 완료되지 않은 부분이 있다.
이렇듯 삽입 정렬은 정렬대상을 두부분으로 나눠서 ,정렬 안된부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해가면서 정렬을 진행해 나가는 알고리즘
*성능 평가 : 정렬대상의 대부분이 이미 정렬되있다면 매우 빠르게 동작한다.
하지만, 버블과 선택 정렬과 마찬가지로, 최악의 경우 모든 비교연산과 이동연산이 진행되기때문에
O(n2)
정렬이 완료된 영역의 다음에 위치한 데이터가 그다음 정렬 대상이다 .
"데이터를 한칸 씩 뒤로 밀면서 삽입할 위치를 찾는다 "
<소스>
