Sorting Algorithm O(n^2)
Problem Solving/Algorithm notes 2009.08.31 22:08
기본적으로 잘 알려져있는 O(n^2) 짜리 Sorting Algorithm 을 정리해보았다..
맨날 c library 에 있는 qsort 만 쓰다보니.. 다 까먹고있는중이다..
1. Bubble Sort
가장 무식하면서 내가 좋아하는 알고리즘으로..
이웃한 수끼리 비교하면서 가장 큰 수를 맨 끝으로 보내는 방식이다..
다른 n^2 sort 랑 다른점은 swap 연산이 훨씬 많다는거..
2. Selection Sort
우리가 흔히 섞여있는 카드를 정렬할 때 사용하는 방식이다..
배열을 다 검사해서 가장 작은 수를 찾아서 맨 앞에 놓고..
다시 배열을 다 검사해서 그다음 작은수를 찾아서 두번째 칸에 놓고..
가장 생각하기 쉬운방식인것 같다..
3. Insertion Sort
앞에 숫자부터 하나씩 뽑아서 이 수를 삽입할 곳을 찾은다음에 삽입..
그 앞에 숫자들은 한칸씩 밀어준다..~
이 방법은 배열이 거의 정렬되어있고 일부만 틀릴때 유용하다..
맨날 c library 에 있는 qsort 만 쓰다보니.. 다 까먹고있는중이다..
1. Bubble Sort
가장 무식하면서 내가 좋아하는 알고리즘으로..
이웃한 수끼리 비교하면서 가장 큰 수를 맨 끝으로 보내는 방식이다..
다른 n^2 sort 랑 다른점은 swap 연산이 훨씬 많다는거..
/* Bubble Sort */
void bubble_sort(int* num, int n)
{
int i, j, temp;
for (i = n-1; i >= 0; i--) {
for (j = 0; j < i; j++) {
if (num[j] > num[j+1]) {
temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
}
void bubble_sort(int* num, int n)
{
int i, j, temp;
for (i = n-1; i >= 0; i--) {
for (j = 0; j < i; j++) {
if (num[j] > num[j+1]) {
temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
}
2. Selection Sort
우리가 흔히 섞여있는 카드를 정렬할 때 사용하는 방식이다..
배열을 다 검사해서 가장 작은 수를 찾아서 맨 앞에 놓고..
다시 배열을 다 검사해서 그다음 작은수를 찾아서 두번째 칸에 놓고..
가장 생각하기 쉬운방식인것 같다..
/* Selection Sort */
void select_sort(int* num, int n)
{
int min1, min_idx;
int i, j;
for (i = 0; i < n-1; i++) {
min_idx = i;
min1 = num[i];
for (j = i+1; j < n; j++) {
if (min1 > num[j]) {
min1 = num[j];
min_idx = j;
}
}
num[min_idx] = num[i];
num[i] = min1;
}
}
void select_sort(int* num, int n)
{
int min1, min_idx;
int i, j;
for (i = 0; i < n-1; i++) {
min_idx = i;
min1 = num[i];
for (j = i+1; j < n; j++) {
if (min1 > num[j]) {
min1 = num[j];
min_idx = j;
}
}
num[min_idx] = num[i];
num[i] = min1;
}
}
3. Insertion Sort
앞에 숫자부터 하나씩 뽑아서 이 수를 삽입할 곳을 찾은다음에 삽입..
그 앞에 숫자들은 한칸씩 밀어준다..~
이 방법은 배열이 거의 정렬되어있고 일부만 틀릴때 유용하다..
/* Insertion Sort */
void insert_sort(int* num, int n)
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = num[i];
j = i;
while (num[j-1] > temp && j > 0) {
num[j] = num[j-1];
j--;
}
num[j] = temp;
}
}
void insert_sort(int* num, int n)
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = num[i];
j = i;
while (num[j-1] > temp && j > 0) {
num[j] = num[j-1];
j--;
}
num[j] = temp;
}
}
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Konig's Theorem (0) | 2010.08.01 |
|---|---|
| Modular Multiplicative Inverse (0) | 2010.06.13 |
| Primality Testing (Miller-Rabin) (0) | 2010.03.23 |
| Modular Exponentiation (Big Mod) (2) | 2010.02.19 |
| KMP (Knuth-Morris-Pratt) Algorithm (0) | 2009.11.15 |
| Sorting Algorithm O(n^2) (0) | 2009.08.31 |
| Bell Number (0) | 2009.07.12 |
| Finding Minimum Path Cover in DAG (0) | 2009.06.15 |
| Plane Equation (평면의 방정식) (0) | 2009.04.16 |
| Ellipse (타원) (0) | 2009.04.15 |
| Modular Arithmetic 1탄 - Extended Euclid (2) | 2009.02.22 |