C언어 알고리즘 버블정렬
정렬 알고리즘에는 크게 버블정렬, 삽입 정렬, 퀵정렬, 선택정렬 등이있는데 그중에서 가장 쉬운것으로 유명한 버블정렬에 대해 알아보도록 하겠습니다.
이 프로그램은 오름차순과 내림차순을 버블정렬로 나타내는 프로그램입니다.
#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문에 따라서 큰수부터 작은수를 할지 작은수부터 큰 수를 할지 비교하는 것입니다.
그렇게 비교하여 작은것부터 큰것인 오름차순 정렬을 하면 큰수가 있으면 뒤에있는 메모리에 대입하고 그 뒤에있던것은 앞으로 오는 스왑 구조를 취하게됩니다.
제가 짠 코드를 보다가 이해가 안되는 부분이있으면 댓글로 설명해드리도록 하겠습니다. 가장 좋은 실력 향상방법은 혼자서 분석하다가 막히는것을 찾아가면서 공부하는것이 좋다고 생각해서 일일이 주석으로 설명을 달지 않겠습니다.
감사합니다.^^
아직 100라인을 넘어가지 않으므로 어떻게 짜든 상관 없습니다만,
이미 손볼 대가 많다는 것은 아시지요?
제가봐도 소스가 좀 더러워 보이네요 ㅎㅎ 그래도 버블정렬을 이용한 오름차순 내림차순 소개하려고 한것이라 이렇게 된것 같네요 앞으로는 더욱 신경쓰겠습니다!
코드를 잘 정돈하는 것은 코드가 동작하게끔 하는 것보다 더 중요할 때가 있습니다.
오랜만에 보는군요 ㅎㅎ
반갑습니다!! 저도 mauver님 블로그 찾아간지 오래됬네요^^
http://algo-visualizer.jasonpark.me/#path=sorting/bubble/basic
요기 보시면 이해하기 더 쉽게 비쥬얼 애니메이션과 함께 깔끔한 코드를 보실 수 있습니다 :)