알고리즘 [Algorithm] - 버블 정렬 Bubble Sort (2) (C, Python)

버블정렬

이번에는 버블 정렬에 대해 알아보자. 버블정렬이란 바로 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 옆에 있는 값와 비교해서 더 작은 값을 계속해서 앞으로 보낸다면 큰 수부터 차례대로 정렬 될 것이다.

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

---

#include <stdio.h>

int main(void){
	int i,j,temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i=0;i<10;i++){
    	for(j=0;j<9-i;j++){
        	if(array[j]>array[j+1]){
        		temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
	
    for (i=0;i<10;i++){
    	printf("%d",array[i]);
    }
    return 0;
}

버블정렬은 정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘인데, 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 알고리즘이다. 버블정렬의 시간 복잡도는 O(N^2)이다.

 

파이썬

a = [1,10,5,8,7,6,4,3,2,9]

for i in range(len(a)):
  for j in range(len(a)-i-1):
    if a[j]> a[j+1]:
      tmp = a[j]
      a[j] = a[j+1]
      a[j+1] = tmp
a

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz