알고리즘 스터디 - 2

박준영·2020년 3월 8일
0

알고리즘스터디

목록 보기
2/4

정렬 알고리즘(Sort)

  • 버블정렬 알고리즘 (Bubble Sort)

옆에 있는 값과 비교해 더 작은 값을 앞으로 보내자. == 가장 큰 값을 계속 뒤로 보낸다.

#include <stdio.h>

int main(void)
{
    int i, j, temp;
    int array[10] = {1, 10, 4, 6, 5, 2, 3, 9, 8, 7};

    for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 9 - i; j++)
        { // 비교할때 마다 한칸씩 줄어든다.
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d", array[i]);
    }
    return 0;
}

✍ Bubble Sort의 효율성 ✍

  • 선택정렬과 마찬가지로 1~10까지 숫자가 무작위로 정렬되어있다고 가정했을때, 몇번 정렬해야 오름차순으로 정렬할 수 있을까?

선택정렬과 마찬가지로 시간복잡도는 다항함수를 띈다. 하지만 단순히 두 숫자를 반복적으로 비교해서 작은값과 큰값의 위치를 바꿔줘야한다. 이 과정에서 매번 숫자를 비교할때마다 변수를 사용해 값을 저장하고 바꿔주는 연산이 필요하므로 선택정렬보다도 비효율적인 알고리즘이다.

0개의 댓글