[C언어 기출문제&풀이] Shake 정렬

프로그램 명: shake

제한시간: 1 초

bubble 정렬을 개선한 소트 방법으로 두개의 변수로 소트할 구역을 알아냅니다.

• low : 소트할 배열의 하단 위치
• high : 소트할 배열의 상단 위치

예를들어,

• low : 1 , high : 7 이면 1 번째 ~ 7 번째가 소트할 대상
• low : 3 , high : 5 이면 3 번째 ~ 5 번째가 소트할 대상 즉 1 번 에서 2 번까지 , 6 번에서 7 번까지는 이미 소트가 이루어진 것을 의미 합니다.
• low >= high 이면 이미 소트가 끝났다는 것을 의미

이 소트 방법은 각 스텝에서 두 번의 스캔이 일어납니다. 각 스캔에서 버블 정렬을 수행합니다.

• 한 번은 아래에서 위로 ... 마지막으로 자리바꿈이 이루어진 위치를 high 변수로 재 지정
• 한 번은 위에서 아래로 ... 마지막으로 자리바꿈이 이루어진 위치를 low 변수로 재 지정
• low < high 참이면 반복

예를 들면,

• step1.

       6 2 9 8 3 4 7
  
       --->
       2 6 8 3 4 7 9 ... right 6
  
            <----
       2 3 6 8 4 7 9 ... left 3
  

  

• step2. .....

입력

입력은 첫 줄은 데이터의 개수 n 이 주어진다. 다음 줄에는 n 개의 데이터가 입력으로 주어진다. 각 수는 -1000 에서 1000 사이 정수이다.

n 은 1000 이하의 양의 정수이다.

출력

최종 정렬이 이루어질 때 까지의 최종 스텝수를 출력한다.

입출력 예

입력

7 
6 2 9 8 3 4 7

출력

3

출처:elfhero 님이 추천한 문제 



풀이 : 조건대로(솔직히 정렬은 완전 교과서적 개념이잖아)



소스코드 

#include <stdio.h>

#define N 6

int main(void)
{
 static int a[]={1,3,2,4,5,6};
 int left,right,i,shift,t,j;
 
 left=0; right=N-1;
 while(left<right){
  for(i=left;i<right;i++){
   if(a[i]>a[i+1]){ 
    t=a[i]; a[i]=a[i+1]; a[i+1]=t;
    shift=i;
   }
  }
  right=shift;
  for(i=right;i>left;i--){
   if(a[i]<a[i-1]){
    t=a[i]; a[i]=a[i-1]; a[i-1]=t;
   }
  }
  left=shift;
 }
 for(i=0;i<N;i++)
  printf("%d ",a[i]);
 printf("\n");

 return 0;
}