원리

• 맨 끝부터 시작한다.
• 맨 끝(n)과 바로 앞 요소(n-1)을 비교해서
  • 앞 요소가 더 크면 두 개를 바꾼다.
  • 뒤 요소가 더 크면 바꾸지 않는다.
• 앞 케이스로 넘어간다.
  • 동일하게 (n-2)와 (n-1)을 비교한다.
• 이를 반복하면 첫 번째 요소에 가장 작은 값이 고정된다
  • 즉 탐색 범위는 n-1 → 0
• 위의 경우를 다시 반복한다.
  • 단 0번째 요소는 이미 고정이므로 탐색범위는 n-1 → 1

연산이 일어나는 횟수

• (n-1) + (n-2) + (n-3) + (n-4) + … + 2 + 1 ⇒ n(n-1)/2
• 단 실제로 교환이 일어나는 횟수는 그 평균값인 n(n-1)/4이다.

알고리즘 개선

• 첫 번째 방법
  • 예를 들어 n-1 번 연산을 하는 1회차, n-2 번 연산을 하는 2회차를 지나 3회차, 4회차를 한 상황
  • 4회차 시행 시 두 원소가 바뀐 경우가 한 번도 없었다. → 이미 정렬이 완료된 상태
  • 이 경우 5회차 이상을 시행 하는 것은 시간 낭비이다.
    • 4회차가 끝나는 동시에 정렬을 종료시킨다.
• 두 번째 방법
  • 예를 들어 1회차에서 n-1번 연산을 해야하는데 1, 2, 3, 4, 5번째 …. n-4 번째 연산까지 교환이 이루어진 상황
  • n-3, n-2, n-1의 연산에 교환이 이루어지지 않았다면, 요소의 1,2,3,4번째는 이미 정렬이 완료된것으로 간주해도 된다.
    • 하나의 회차에서 정렬을 끝낼 종료점을 그만큼 앞당긴다.
      • 1 → 2에서 1→5로 앞당긴다.

셰이커 정렬

• 버블 정렬은 일단 가장 작은 원소를 맨 앞으로 빼는 방식이다.
• 셰이커 정렬의 경우, 한 번은 가장 작은 것을 앞으로 뺏다가, 다른 한번은 가장 큰 것을 뒤로 빼는 방식이다.
  • 만약 가장 큰 원소가 가장 앞에 있다면, 이 원소를 그때마다 뒤로 빼줘야 하니 그때마다 연산이 발생한다.
  • 번갈아가면서 가장 작은 걸 빼고 큰 걸 빼주면서 효율화를 이룰 수 있다.
  • 위에 설명한 두 가지 개선책과 결합하면 더 빠른 정렬 가능하다.