[알고리즘] 기초 정렬 알고리즘 - 버블 정렬(Bubble Sort)

 

 

버블 정렬

배열을 검사하여 두 인접한 원소가 오름차순 순서에 맞지 않으면 이들을 서로 교환하는 것

 

거의 정렬된 화일(almost sorted file)일 경우 유리

실행시간은 입력자료의 순서에 민감

제자리 정렬

안정적 알고리즘

 

a[1]과 a[2]를 비교, 정렬 순서(오른쪽이 더 큰 순서)에 맞지 않으면 서로 교환

a[2]와 a[3]을 비교, 정렬 순서(오른쪽이 더 큰 순서)에 맞지 않으면 서로 교환

..

..

..

a[n-1]과 a[n]을 비교, 정렬 순서에 맞지 않으면 서로 교환

이 과정이 한번 끝나면 제일 큰 원소가 a[n] 자리에 오게 된다.

 

다시 이 과정을 a[n-1]에 a[n]다음으로 큰 원소가 올때까지 반복,

다시 n-2까지 반복...

다시 n-3까지 반복..

..

..

마지막으로 a[1]과 a[2]을 비교하여 순서가 맞지 않으면 서로 교환할때까지 계속

 

알고리즘의 수행중 키의 자리바꿈이 전혀 일어나지 않으면 배열이 이미 정렬된 것

 

전체 비교 횟수는 N(N-1)/2  => 전체 시간 복잡도는 O(N^2)

 

 

버블 정렬 알고리즘

BubbleSort(a[], n)  {      for ( i <- n; i >= 1; i <- i-1) do {         for ( j <- 1; j < i; j <- j+1) do {            if ( a[j] > a[j+1] ) then A[j]와 A[j+1]을 교환;         }      }  }