Insertion sort
Merge sort
Binary search
Selection sort
Bubble sort
Insertion sort란 정렬된 리스트에 정렬을 유지하도록 키를 삽입하는 정렬.
Performance
Running time
Instruction의 수를 센다.
Instruction에는 더하기 빼기 같은 산술계산과 Load, store, copy 같은 데이터 이동이나 if나 함수호출 등과 같은 Control이 있다.
running time은 input의 갯수에 따라 달라진다.
for나 while loop은 loop body 보다 한번 더 실행된다. 조건 연산때문에
이미 많은 부분이 정렬되어 있을 때 사용하면 성능이 좋다.
Best case : 이미 정렬되어 있을때, 두번째 루프 안돌아도 되므로 수행시간은 an+b, 즉 linear function이다.
Worst case : 반대로 정렬되어 있을 때. quadratic function. O(n^2)
Space consumption : O(n)
Sorted in place : 내부에서 정렬이 된다.
Performance
Running time
Instruction의 수를 센다.
Instruction에는 더하기 빼기 같은 산술계산과 Load, store, copy 같은 데이터 이동이나 if나 함수호출 등과 같은 Control이 있다.
running time은 input의 갯수에 따라 달라진다.
for나 while loop은 loop body 보다 한번 더 실행된다. 조건 연산때문에
이미 많은 부분이 정렬되어 있을 때 사용하면 성능이 좋다.
Best case : 이미 정렬되어 있을때, 두번째 루프 안돌아도 되므로 수행시간은 an+b, 즉 linear function이다.
Worst case : 반대로 정렬되어 있을 때. quadratic function. O(n^2)
Space consumption : O(n)
Sorted in place : 내부에서 정렬이 된다.
Merge sort
두개의 정렬된 리스트를 하나의 정렬된 리스트로 만드는 것
이동의 수 : n1+n2
비교연산의 수 : <= n1+n2
따라서 O(n1+n2)
Divide : n개의 keys를 n/2인 두개의 리스트로 나눈다.
Conquer : 두개의 리스트를 재귀적으로 정렬한다.
combine : 두개의 리스트를 합친다.
Running time
Divide : O(1), 중간 값만 계산하면 되니까.
Conquer : 2T(n/2), 리스트 2개가 재귀적으로 정렬하는 시간
combine : O(n)
Recursion tree
각 단계의 합 : cn
트리의 높이 : 2^k = n 으로부터 k = lgn, 따라서 높이 h = lgn+1
n이 1이 될때까지 2를 나눈 횟수+1이 높이. n(1/2)^k = 1, k=lgn.
이동의 수 : n1+n2
비교연산의 수 : <= n1+n2
따라서 O(n1+n2)
Divide : n개의 keys를 n/2인 두개의 리스트로 나눈다.
Conquer : 두개의 리스트를 재귀적으로 정렬한다.
combine : 두개의 리스트를 합친다.
Running time
Divide : O(1), 중간 값만 계산하면 되니까.
Conquer : 2T(n/2), 리스트 2개가 재귀적으로 정렬하는 시간
combine : O(n)
Recursion tree
각 단계의 합 : cn
트리의 높이 : 2^k = n 으로부터 k = lgn, 따라서 높이 h = lgn+1
n이 1이 될때까지 2를 나눈 횟수+1이 높이. n(1/2)^k = 1, k=lgn.
Binary search
T(n) = T(n/2) + 1
Running time이 1부터 ln n까지
Running time이 1부터 ln n까지
Selection sort
리스트에서 가장 작은 숫자를 찾는 과정이 반복되는 정렬
자료 이동 횟수는 고정 3(n-1). 3은 최소값이 i번째 값과 바뀔 때(i는 첫번째 루프단계, 0부터 n-2까지). 총 n-1번 돈다.
같은 값이 있는 경우 상대적인 위치 변경 가능성이 있다.
자료 이동 횟수는 고정 3(n-1). 3은 최소값이 i번째 값과 바뀔 때(i는 첫번째 루프단계, 0부터 n-2까지). 총 n-1번 돈다.
같은 값이 있는 경우 상대적인 위치 변경 가능성이 있다.
Bubble sort
바로 다음 값과 연쇄적으로 비교하면서 큰값이 마지막에 위치하도록 하는 정렬.
비교횟수 : Worst, Average, Best 가 일정.
이동횟수 : 자료가 역순으로 되어 있을때 Worst, 정렬되어 있을때 Best
비교횟수 : Worst, Average, Best 가 일정.
이동횟수 : 자료가 역순으로 되어 있을때 Worst, 정렬되어 있을때 Best
'공부 > 알고리즘' 카테고리의 다른 글
| 8장 Sorting in Linear Time (0) | 2011.07.03 |
|---|---|
| 7장 Quicksort (0) | 2011.07.03 |
| Heapsort (1) | 2011.06.30 |
| 4 Recursion (0) | 2011.06.28 |
| 3장 Growth of Funtions (0) | 2011.06.24 |
