반응형

이 거품 정렬 일명 버블소팅이라하는

이 알고리즘을 설명하고자 한다.

이 거품 정렬은 일반적으로 꽤 알려져 있는 편인데

꽤 형편없을 정도로 무식하고 느리다..ㅋ


그럼 이 정렬의 알고리즘이 어떻게 되는지 한번 살펴보자


1. i = 0;

2. i가 n-1이 되면 끝낸다.

3. j = 1;

4. j가 n-i가 되면 7로 간다.

5. a[j-1] > a[j]이면 두 값을 교환한다.

6. j를 하나 증가시키고 4로 돌아간다.

7. i를 하나 증가시키고 2로 돌아간다.


이 알고리즘을 가만히 보면 일일이 하나씩 비교 하면서

정렬을 한다는 것을 알수 있는데


쉽게 예를 들면 'SORTING' 이라는 단어를 알파벳 순서에 맞게

정렬하는 모습을 살펴보자.


S O R T I N G

O S R T I N G

O R S T I N G

O R S I T N G

O R S I N T G

O R S I N G T


이것은 단지 T라는 최대값을 맨 뒤로 간것 뿐이다

이것이 바로 정렬하는데 있어서 한단계일 뿐인것이다.

이와 같은 짓을 계속해서 결국

G I N O R S T

이와 같은 정렬을 이룰 것이다.


이해가 가는가?? ㅎㅎㅎ

이해가 간다면 당신도 이제 프로그래머~!!캬~!


자 그렇다면 이제 C 로 한번 구현해 보자~!


참고로 아주 원론적으로 하나도 개선 안된 위의 알고리즘에만 기초해서

만든 소스임...ㅋ


#include<stdio.h>
#include<string.h>

void bubble_sort(char *a, int n)
{
 int i, j;
 char t;
 for(i = 0; i<n-1; i++)
 {
  for(j = 1; j<n-i ;  j++)
  {
   if (a[j-1] > a[j]);
   {
    t = a[j-1];
    a[j-1] = a[j];
    a[j] = t;
   }
  }
 }
}


void main()
{
 char str[8] = {'s','o','r','t','i','n','g','\0'};
 puts(str);
 bubble_sort(str, 7);
 puts(str);
}


주석달기가 귀찮아서 혹 이해안가면 질문을 하시길 그때

알려 드리겠음.^^

반응형

'자료구조 & 알고리즘' 카테고리의 다른 글

이진탐색트리의 완결판!!!!  (1) 2007.03.14
초보를 위한 프로그래밍 입문서  (0) 2007.03.14
dekker 알고리즘  (0) 2007.03.14
Posted by Real_G