프롤로그
자료구조에서 정렬을 이야기하는 이유는 탐색을 설명하기 위해서이다.
자료구조의 3대 연산
(1)삽입 (2)삭제 (3)탐색
이 때 탐색의 성능은 뺄래야 뺼 수 없는 주제이다.
따라서 탐색 이전에 선행되어야 하는 정렬은 자료구조와 뗄레야 뗄 수 없는 알고리즘이다.
단순한 정렬 알고리즘을 10 - 1 에서 배우고 상대적으로 복잡한 정렬 알고리즘을 10 - 2에서 배우는데
복잡한 정렬 알고리즘이 당연히 성능이 상대적으로 좋으나, 단순한 정렬 알고리즘은 구현에서 이점이 있다. (필요한 경우에 함수의 일부에 몇 줄 적어넣어 구현하기 쉽다.)
즉, 목적에 맞게 그 때 그 때 쓰기 쉽기 때문에 단순한 정렬 알고리즘도 알아두어야 한다.
(1) 버블 정렬 알고리즘
1. 예시를 통한 알고리즘 설명
4 2 3 1이 있다고 가정하자.
이 때 이 네개 중 가장 큰 값을 맨 뒤로 보낼 것인데
그 과정은 다음과 같다.
4 2 3 1에서 4 와 2를 비교하여 더 큰 것을 뒤로 -> 2 4 3 1
2 4 3 1에서 4 와 3을 비교하여 더 큰 것을 뒤로 -> 2 3 4 1
같은 과정을 거치면 2 3 1 4가 된다.
이와 같은 과정을 맨마지막의 4를 제외하고 거치면
2 3 1 4 -> 2 3 1 4 -> 2 1 3 4 가 되고
이 때 2 1만 활용하여 마지막 과정을 거치면
2 1 3 4 -> 1 2 3 4 가 된다.
많은 양의 데이터를 정렬하기에는 적절하지 않으나 구현하기 쉽다는 장점이 있다.
2. 구현
#include <stdio.h>//버블 정렬
void BubbleSort(int array[], int n)//n은 데이터의 개수
{
int i, j;
int temp;
for (i = 0; i < n - 1; i++)//총 n - 1회 실시,처음에는 array[n - 2],array[n - 1]이 마지막 비교
{
for (j = 0; j < (n - i) - 1; j++)//처음에는 arrya[n - 1]과 array[n - 2]까지 그다음부터 1씩 줄어서 마지막에는 array[0]와 array[1]비교만 하고 끝
//횟수로 생각해도 편하다. 처음에 n - 1회 그다음부터 1회씩 줄어듬, 마지막에는 1회
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}//똑같다 ㅎㅎ
int main()
{
int i, T;
int array[100];
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d", &array[i]);
}
BubbleSort(array, T);
for (i = 0; i < T; i++)
{
printf("%d\n", array[i]);
}
return 0;
}3. 성능
정렬의 성능 평가의 두가지 기준
1. 비교의 횟수
2. 이동의 횟수
비교연산은 무조건 n(n - 1)/2 즉, 시간복잡도는 O(n^2)
워스트 케이스의 경우, 비교의 횟수와 이동의 횟수는 일치한다.
(2) 선택 정렬
데이터의 수가 적을 때, 특정 케이스일 때 선택 정렬이 확실히 성능에 우위를 점한다.
그러나 사실상 버블 정렬과 큰 성능 차이는 보이지 않는다.
1. 예시를 통한 알고리즘 설명
ex.
1 2 4 3 이라는 배열에서 최솟값 1을 선택하여 새로운 메모리 공간에 저장
남은 2 4 3 중 최솟값 2를 저장...
즉 새로운 배열에 1 2 3 4가 저장된다.
이는 별도의 메모리 공간이 요구된다는 단점이 있다.
2. 개선된 모델
1 4 2 3 중 최솟값을 선택하여 첫번째 칸으로 -> 1 4 2 3
4 2 3 중 최솟값을 두번째 칸으로 1 2 4 3//두번째 칸으로 2를 보내고 기존에 두번째 칸에 있던 데이터는 2가 있던 칸으로!
4 3 중 최솟값을 세번째 칸으로 -> 1 2 3 4
즉, 총 반복은 n - 1회하면 된다. (n번째는 필요 X)
이러면 별도의 메모리 공간이 요구되지 않는다.
3. 구현
https://www.acmicpc.net/problem/2750
이 문제를 선택정렬을 활용하여 해결한 코드
#include <stdio.h>//선택 정렬
void SelSort(int array[], int n)
{
int i, j;
int min;
int min_index;
int temp;
for (i = 0; i < n - 1; i++)
{
min = 1001;
for (j = i; j < n; j++)
{
if (min > array[j])
{
min = array[j];
min_index = j;
}
}
temp = array[i];
array[i] = min;
array[min_index] = temp;
}
}
int main()
{
int i, T;
int array[1000];
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d", &array[i]);
}
SelSort(array, T);
for (i = 0; i < T; i++)
{
printf("%d\n", array[i]);
}
return 0;
}강의에서 배운대로 구현하여 해결
#include <stdio.h>//선택 정렬
void SelSort(int array[], int n)
{
int i, j;
int min_idx;
int temp;
for (i = 0; i < n - 1; i++)
{
min_idx = i;//처음에는 array[i]와 비교
for (j = i; j < n; j++)
{
if (array[min_idx] > array[j])
{
min_idx = j;//array[i]보다 작은 값이 있으면 그 칸을 min_idx라 한다.
}
}
temp = array[i];
array[i] = array[min_idx];
array[min_idx] = temp;//array[i]와 비교한 칸들 중 가장 작은 값이 저장된 칸 swap
}
}
int main()
{
int i, T;
int array[1000];
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d", &array[i]);
}
SelSort(array, T);
for (i = 0; i < T; i++)
{
printf("%d\n", array[i]);
}
return 0;
}4. 성능 평가
일단 무조건 다 비교해서 뭐가 최솟값인지 확인해야 하므로
비교 연산은 n(n + 1)/2 즉, 시간복잡도는 O(n^2)이다.
하지만 버블정렬과 달리 이동이 없으므로 버블 정렬보다는 성능이 좋다.
(3) 삽입 정렬
1. 알고리즘
정렬이 완료된 영역으로 완료되지 않은 영역에 속하는 숫자를 던진(?)다
5가 들어간다고 가정할 때, 5를 5보다 작은 수와 큰 수 사이에 삽입한다.
즉 5보다 큰 수를 만나면 바로 그 전 칸에 삽입한다.
이를 반복한다.
잠시 선택 정렬과의 차이를 살펴보자면
선택 정렬은 최솟값을 선택해서 맨 앞에 가져다 높기
삽입 정렬은 정렬되지 않은 칸의 숫자를 하나 가져와서 정렬된 칸의 알맞은 위치에 삽입
- 삽입 정렬의 귀찮은 점 - 삽입되고 난 후 그 뒤의 배열들을 한 칸씩 오른쪽으로 밀어야 한다.
이는 삽입되어야 할 데이터를 temp로 저장하고
삽입되어야 할 위치의 칸부터 삽입되어야 할 데이터의 원래 위치 전까지를 모두 오른쪽으로 한칸씩 밀고 temp룰 삽입되어야 할 위치에 저장하면 된다.
2. 구현
https://www.acmicpc.net/problem/2750
이 문제를 삽입 정렬로 해결한 코드
#include <stdio.h>//삽입 정렬
void InsertSort(int array[], int n)
{
int i, j, k;
int temp;
for (i = 1; i < n; i++)
{
temp = array[i];
for (j = 0; j < i; j++)
{
if (temp < array[j])
{
for (k = i - 1; k >= j; k--)
{
array[k + 1] = array[k];
}
array[j] = temp;
break;
}
}
}
}
int main()
{
int i, T;
int array[1000] = { 0 };
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d", &array[i]);
}
InsertSort(array, T);
for (i = 0; i < T; i++)
{
printf("%d\n", array[i]);
}
return 0;
}강의
#include <stdio.h>//삽입 정렬
void InsertSort(int array[], int n)
{
int i, j, k;
int temp;
for (i = 1; i < n; i++)
{
temp = array[i];
for (j = i - 1; j >= 0; j--)
{
if(array[j] > temp) array[j + 1] = array[j];
else break;
}
array[j + 1] = temp;
}
}
int main()
{
int i, T;
int array[1000] = { 0 };
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d", &array[i]);
}
InsertSort(array, T);
for (i = 0; i < T; i++)
{
printf("%d\n", array[i]);
}
return 0;
}
나와의 결정적 차이는 비교연산과 이동을 동시에 한다는 것이다.
그림으로 보면 다음과 같다.
3. 성능 평가
비교연산은 최악의 경우 버블정렬, 선택정렬과 같이 n(n - 1)/2이므로 시간복잡도는 O(n^2)
최고의 경우 가장 버블정렬, 선택정렬, 삽입정렬 중 가장 성능이 좋으나 (연산횟수는 n에 비례)
최악의 경우 버블정렬과 같이 비교연산만큼 이동을 해야하므로 선택정렬보다 성능이 좋지 않다.
