Insertion Sort, Bubble Sort

Insertion Sort

처음에는 output은 비어있다.

item을 하나씩 넣으면서 적절한 자리를 골라 채운다.

 

insertion sort

한 item의 적절한 자리를 찾을 때, 그 전까지 들어간 item들은 정렬이 되어 있으므로 넣는 item의 값보다 작은 item이 나올때까지 앞의 item과 자리를 계속 바꾼다.

 

Best Case(이미 정렬되어 있는 경우) : 자리 바꿈 0번, n-1번 comparisons

Worst Case(역순 정렬되어 있는 경우) : 자리 바꿈과 comparisons 둘 다  O(n^2/2)번

Average Case : 자리 바꿈과 comparisons 둘 다  O(n^2/4)번

 

insertion sort는 대다수의 경우 그렇게 효율적이지 못하지만 거의 정렬되어 있는 array에 대해서 정렬을 할 때는 대단히 좋은 효율을 보인다.

 

 

 

Bubble Sort

k번째 iteration에서 k번째로 작은 element가 k번째에 오는 것을 목표로 하는 sort.

 

bubble sort

Best Case(이미 정렬되어 있는 경우) : 자리 바꿈 0번, 비교 O(n^2/2)번

Worst Case(역순 정렬) : 자리 바꿈과 비교 O(n^2/2)번

Average Case : 자리 바꿈과 비교 O(n^2/4)번

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업