[알고리즘]정렬 알고리즘 - 버블정렬
내부 정렬(Internal sort)
-입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬
ex) 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬, 기수 정렬, 이중 피봇 퀵정렬. Tim sort
외부 정렬(External sort)
-입력의 크기가 주기억 장치의 공간보다 큰 경우에 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복
버블 정렬
-이웃하는 숫자를 비교하여 작은 수를 앞쪽(오름차순)으로 이동시키는 과정을 반복하여 정렬
-배열을 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 함
패스: 입력을 전반적으로 1번 처리하는 것
1번째 pass 결과를 살펴보면, 작은 수는 버블처럼 위로 1칸씩 올라감
가장 큰 수인 90은 맨 밑에 위치
비교를 통해 40-50은 그대로, 50과 10이 서로의 자리를 바꿈
비교를 통해 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)