2. 정렬 알고리즘

알고리즘을 공부할 때 가장 먼저 시작하는게 정렬 알고리즘이다. 이유는 정렬 알고리즘만큼 알고리즘의 효율성 차이를 보여주는 것이 드물기 때문이다. 정렬 알고리즘은 데이터를 비교해서 원하는 순서대로 나열하는데 사용되는 알고리즘이다.

 

정렬 알고리즘에는 다양한 알고리즘이 있지만 기본적인 알고리즘 3가지을 가지고 효율성을 알아보자

 

---

1. 버블 정렬

버블 정렬은 나열된 두 값을 비교해서 원하는 순서로 바꾸는 것을 의미한다.

위와 같이 나열된 숫자들이 있을 때

이렇게 두자리씩 비교해서 작은건 앞으로 큰건 뒤로 옮기면 1234로 나열할 수 있다. 이와 같이 연속된 두자리를 비교해서 순서를 바꾸는 정렬이 버블 정렬이다.

 

c 언어을 이용하여 [1, 10, 5, 4, 3, 9, 6, 8, 7, 2] 을 작은 순서대로 배열하는 버블 정렬을 만들어 보았다. 

 

#include 

int main(void){
int i, j, temp;
int array[10] = {1, 10, 5, 4, 3, 9, 6, 8, 7, 2};

for( i = 0 ; i < 10 ; i++){
  for( j = 0 ; j < 9-i ; j++){
    if(array[j] > array[j+1]){
      temp = array[j+1];
      array[j+1] = array[j];
      array[j] = temp;
    }
  }
}

for( i = 0 ; i < 10 ; i ++){
  printf("%d", array[i]);
}


return 0;
}

 

i값이 순서대로 진행되면서 j가 나열된 두 숫자를 비교해서 서로 크기 비교를 통해 작은걸 앞으로 보내준다. 이 작업이 i값이 커지면서 계속 반복되므로 결국 작은 숫자는 맨앞으로 가고 큰 숫자는 뒤쪽으로 나열되어 1부터 10까지 나열된 숫자가 저장된다.