간단한 정렬 알고리즘 정리

알고리즘 중에서도 정렬과 탐색은 가장 많이 쓰이는 알고리즘중 하나이다. 

이 포스팅에선 코드적으로 구현이 꽤 간편하면서도 햇갈리는 버블 정렬(Bubble Sort) 선택 정렬(Selection Sort)

삽입정렬(Insertion Sort)을 정리해 보려한다.

우선 버블정렬은 c언어 기본문법서도 다룰 만큼 기초적인 정렬 알고리즘이다.

(윤성우의 열혈 자료구조 그림 10-1)

위의 그림에서부터 알수 있듯이 버블정렬은 두 인접한 데이터를 비교해가면서 정렬을 진행하는 방식이다.

위의 작업은 오름차순으로 정렬을 하는 과정으로 정렬의 우선순위가 가장 낮은 큰 값이 맨 뒤로 이동한다.

위와 같이 두번째, 세번째, 네번째 값들도 차례 대로 정렬을 해준다. 

다음은 버블정렬의 구현이다.

void BubbleSort(int arr[], int n)

{

int i, j;

int tmp;

for(i=0; i<n-1; i++)

{

for(j=0; j<(n-i)-1; j++)

{

if(arr[j]>arr[j+1])

{

tmp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = tmp;

}

}

}

}

버블 정렬의 빅오는 O(n^2) 이다. 상당히 좋지 않은 알고리즘에 속한다고 볼수 있다.

그 다음은 선택 정렬이다.

(윤성우 열혈 자료구조 그림 10-5)

위의 그림을 해석해보자면 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그자리에 있던 데이터는 빈 자리에 가져다 놓는것이다. 딱히 덧붙힐 설명도 없으므로 아래 구현을 참고하길 바란다.

void SelSort(int arr[], int n)

{

int i, j;

int idx;

int tmp;

for(i=0; i<n-1; i++)

{

idx = i;

for(j=i+1; j<n; j++)

{

if(arr[j]<arr[idx])

idx = j;

}

tmp = arr[i];

arr[i] = arr[idx];

arr[idx] = tmp;

}

}

선택 정렬의 빅오는 O(n)으로 버블정렬보다는 성능이 좋지만 여러 경우들을 고려하면 사실 둘은 비슷비슷하다.

마지막으로 삽입 정렬이다.

(윤성우 열혈 자료구조 그림 10-8)

그림을 보면 이해가 쉽게 되리라 생각된다. 첫 번째부터 차레대로 데이터를 비교하며 데이터를 옮겨준다 

단지 코드를 구현해줄때는 정렬이 되야 되는 곳 이후에 있는 데이터들은 뒤로 옮겨 주는 작업도 해줘야 된다.

다음은 삽입 정렬 코드이다.

void InsertSort(int arr[], int n)

{

int i, j;

int data;

for(i=1; i<n; i++)

{

data = arr[i];

for(j=i-1; j>=0; j--)

{

if(arr[j]>data)

arr[j+1] = arr[j];

else

break;

}

arr[j+1] = data;

}

}

빅오는 O(n^2)이므로 버블정렬과 같다. 좋은 알고리즘이라고 볼수는 없겠다.