[알고리즘]정렬 알고리즘 - 버블정렬

내부 정렬(Internal sort)

-입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬

ex) 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬, 기수 정렬, 이중 피봇 퀵정렬. Tim sort

 

외부 정렬(External sort)

-입력의 크기가 주기억 장치의 공간보다 큰 경우에 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복

 

버블 정렬

-이웃하는 숫자를 비교하여 작은 수를 앞쪽(오름차순)으로 이동시키는 과정을 반복하여 정렬

-배열을 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 함

패스: 입력을 전반적으로 1번 처리하는 것

 

1번째 pass

1번째 pass 결과를 살펴보면, 작은 수는 버블처럼 위로 1칸씩 올라감

가장 큰 수인 90은 맨 밑에 위치

2번째 pass

비교를 통해 40-50은 그대로, 50과 10이 서로의 자리를 바꿈

3번째 pass

비교를 통해 40과 10이 서로 자리를 바꿈

>> n개의 원소가 있으면 (n-1)번의 패스가 수행

 

버블정렬의 알고리즘

BubbleSort

입력: 크기가 n인 배열 A

출력: 정렬된 배열 A

for pass=1 to n-1
	for i=1 to n-pass
    	if(A[i-1]>A[i])
    		A[i-1]<->A[i]
return A

 

버블정렬의 시간 복잡도

버블 정렬은 for루프 속에서 for루프 수행

-pass=n-1이면 1번 비교

-총 비교 횟수:(n-1)+(n-2)+...+1=n(n-1)/2

-안쪽 for루프의 if조건이 True일 때의 자리바꿈은 O(1) 시간

 

>>n(n-1)/2*O(1)=O(n^2)*O(1)=O(n^2)