Page 208 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

Q5 연습문제 Q2(204쪽)와 마찬가지로 비교, 교환 과정을 자세히 출력하는 프로그램(실습
연습
문제 6-3)으로 수정하세요.

Q6 다음의 배열을 정렬한다고 가정하겠습니다.

9 1 3 4 5 6 7 8

이 배열은 두 번째 요소부터는 정렬은 되어 있지만 버전 3의 버블 정렬 알고리즘을 사용해도 빠른
시간 안에 정렬 작업을 마칠 수는 없습니다. 왜냐하면 맨 앞에 있는 요소의 값(9)은 1회의 패스를
거쳐도 한 칸만 뒤로 옮겨지기 때문입니다. 그래서 홀수 번째의 패스는 가장 작은 요소를 맨 앞으
로 옮기고 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면(패스의 스캔 방향을
교대로 바꾸면) 이런 정렬을 더 적은 횟수로 비교를 수행할 수 있습니다. 버전 3의 프로그램을 개
선하여 양방향 버블 정렬을 수행하는 프로그램을 작성하세요.

버블 정렬을 개선한 이 알고리즘은 양방향 버블 정렬(bidirection bubble sort) 또는 칵테일 정렬(cocktail
sort), 셰이커 정렬(shaker sort)이라는 이름으로 알려져 있습니다.

208 C 알고리즘