버블 정렬

버블 정렬

• 정렬되지 않은 리스트를 탐색하는 것 보단 정렬한 뒤 탐색하는 것이 더 효율적
• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법
• 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중.

    - 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는
      낭비가 발생할 수도 있다.

실행

• 리스트 안에 들어있는 두개의 인접한 수를 비교하고 만약 순서에 맞지 않는다면
  교환해주는 방식으로 작동합니다.

• 그림 2를 보면 5,1,6,2,4,3의 순서로 들어있는 배열이 있다.
• 버블 정렬을 사용하여 정렬해주고 싶다면 다음과 같은 의사 코드를 만들어 볼수 있다.

• 제일 먼저 배열 안에서 5와 1을 비교하기 시작할 것이다.

  - 1이 5보다 작기 때문에 두 수는 교환될 것입니다.

• 다음에는 5와 6을 비교하는데 올바른 순서로 되어있기 때문에 그 다음 요소로
  넘어갈 것입니다.
• 다음은 6과 2를 비교하고 계속 같은 방식으로 비교하여 교환합니다.

• 한번 정렬을 하면 1, 5, 2, 4, 3, 6의 순서로 정렬된 것을 확인할 수 있다.
• 와전히 정렬되지 않은 배열이지만 6은 이미 제자리에 와있다.
• n개의 원소에 대해서 버블 정렬을 한번 수행할 떄마다 n번째의 원소가 제 자리를
  찾게 됩니다.

  그렇기 때문에 다음 정렬에서는 n - 1 개의 원소를 정렬해주면 됩니다.

정렬된 배열

• 버블 정렬은 수행 한번에 모든 원소가 정렬되는 것을 보장하지 않는다.
• 그러면 몇번의 시도를 해줘야 할까요?

  예를 들어 6,5,4,3,2,1 과 같이 거꾸로 정렬된 경우 다섯번 시도를 해야한다.
  즉, n개의 요소를 정렬해 주기 위해서는 n-1번 실행해주어야 합니다.
  최악의 상황인 경우 최대한의 횟수를 실행해줘야 하므로 경제적이지 x

생각해보기

• 버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적?

  정렬한 숫자가 적게 있거나 어느정도 정렬되있을때 효율적이고, 
  많이있으면 모든 측면에서 비효율적이다.

• 버블 정렬을 이용하여 4, 30, 49, 11, 5를 정렬해 봅시다.

  1.   4 , 30 , 49, 11, 5
  2.   4 , 30 , 11,  5, 49
  3.   4 , 30 , 5 , 11, 49
  4.   4 , 5  , 11, 30, 49