C언어 알고리즘 버블정렬

in #kr7 years ago

정렬 알고리즘에는 크게 버블정렬, 삽입 정렬, 퀵정렬, 선택정렬 등이있는데 그중에서 가장 쉬운것으로 유명한 버블정렬에 대해 알아보도록 하겠습니다.
이 프로그램은 오름차순과 내림차순을 버블정렬로 나타내는 프로그램입니다.

#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
    int n,s,a[100],tmp;
    char x;
    while(1){
        cout<<"\n===============================================\n프로그램을 종료하려면 x키를 누르시오.\n다른 키를 누를경우 계속합니다.";
        //printf("\n===============================================\n프로그램을 종료하려면 x키를 누르시오.\n다른 키를 누를경우 계속합니다.");
        x=getch();
        if(x=='x'){
            cout<<"\n프로그램이 종료되었습니다."<<endl;
            //printf("\n프로그램이 종료되었습니다.\n"); 
            break;
        }
        cout<<"\n\n==============================================="<<endl;
        cout<<"입력할 숫자의 개수를 입력하시오(1~100) : ";
        cin>>n;
        while(1){
            cout<<"오름차순을 원하면 1\n내림차순을 원하면 2\n둘 중 하나를 선택하시오.";
            //printf("오름차순을 원하면 1\n내림차순을 원하면 2\n둘 중 하나를 선택하시오.");
            cin>>s; 
            //scanf("%d,&s);
            if(s==1||s==2){
                break;
            }else{
                cout<<"\n=====================\n잘못된 입력입니다.\n=====================\n"<<endl;
                //printf("\n=====================\n잘못된 입력입니다.\n=====================\n\n");
            }
        }
        cout<<"\n"<<n<<"가지 숫자를 입력하시오 : ";
        for(int i=0; i<n; i++){
            //scanf("%d",&a[i]); 
            cin>>a[i];
        }
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(s==1){
                    if(a[i]>a[j]){
                        tmp=a[j];
                        a[j]=a[i];
                        a[i]=tmp;
                    }
                }else if(s==2){
                        if(a[i]<a[j]){
                        tmp=a[i];
                        a[i]=a[j];
                        a[j]=tmp;
                    }
                }
            }
        }
        if(s==1){
            cout<<"\n오름차순 입니다."<<endl;
            //printf("\n오름차순 입니다.\n");
        }else{
            cout<<"\n내림차순 입니다."<<endl; 
            //printf("\n내림차순 입니다.");
        }
        for(int i=0; i<n; i++){
            //printf("%d번쨰 : %d",i+1,a[i]);
            cout<<i+1<<"번째: "<<a[i]<<endl;
        }
    }
}

프로그램을 제작할때 printf나 scanf같이 간단한것은 c++로 하는게 더 간단해서 c++로 했기때문에 c++구문 밑에는 주석처리로 C언어를 나타내게 하였습니다.
그렇다면 버블벙렬이라는것은 무엇일까요?
일단 이름처럼 순서대로 정렬을 하는것입니다.
영어로는 bubble sort라고 합니다.
그렇다면 이 버블정렬은 이 프로그램에서 어떤 곳에서 비교를 할까요?

for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(s==1){
                    if(a[i]>a[j]){
                        tmp=a[j];
                        a[j]=a[i];
                        a[i]=tmp;
                    }
                }else if(s==2){
                        if(a[i]<a[j]){
                        tmp=a[i];
                        a[i]=a[j];
                        a[j]=tmp;
                    }
                }
            }
        }

이 부분인데요 for문에서 i=0인데 j=i+1은 배열의 앞뒤를 비교하는것이고 그 비교한것을 tmp에 저장했다가 다시 뒤에있는것과 비교하여 for문안에 첫번째 if문에 따라서 큰수부터 작은수를 할지 작은수부터 큰 수를 할지 비교하는 것입니다.
그렇게 비교하여 작은것부터 큰것인 오름차순 정렬을 하면 큰수가 있으면 뒤에있는 메모리에 대입하고 그 뒤에있던것은 앞으로 오는 스왑 구조를 취하게됩니다.
제가 짠 코드를 보다가 이해가 안되는 부분이있으면 댓글로 설명해드리도록 하겠습니다. 가장 좋은 실력 향상방법은 혼자서 분석하다가 막히는것을 찾아가면서 공부하는것이 좋다고 생각해서 일일이 주석으로 설명을 달지 않겠습니다.
감사합니다.^^

Sort:  

아직 100라인을 넘어가지 않으므로 어떻게 짜든 상관 없습니다만,
이미 손볼 대가 많다는 것은 아시지요?

제가봐도 소스가 좀 더러워 보이네요 ㅎㅎ 그래도 버블정렬을 이용한 오름차순 내림차순 소개하려고 한것이라 이렇게 된것 같네요 앞으로는 더욱 신경쓰겠습니다!

코드를 잘 정돈하는 것은 코드가 동작하게끔 하는 것보다 더 중요할 때가 있습니다.

  • 어떤 관점에서 코드를 손질해야할까요?
  • 코드를 손질 하면서 소스동작을 유지시키려면 어떻게 해야할까요?

오랜만에 보는군요 ㅎㅎ

반갑습니다!! 저도 mauver님 블로그 찾아간지 오래됬네요^^

http://algo-visualizer.jasonpark.me/#path=sorting/bubble/basic

요기 보시면 이해하기 더 쉽게 비쥬얼 애니메이션과 함께 깔끔한 코드를 보실 수 있습니다 :)