그 외 공부/Algorithm
# 10_Sorting
ssangeun
2017. 11. 5. 22:52
* Bubble sort는 앞에서부터 채워지고, Selection sort는 뒤에서부터 채워집니다. Insertion sort는 어떠한 패턴보다는 자신의 자리를 찾습니다.
# The source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 |
#include<stdio.h>
void printAll(int * toBeDisplayed, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d, ", toBeDisplayed[i]);
}
printf("\n");
return;
}
void swap(int * arr, int i, int j)
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
return;
}
void performBubbleSort(int * toBeSorted, int sz)
{
int i, j;
for (i = 0; i < sz; i++)
{
for (j = 0; j < sz - i - 1; j++)
{
if (toBeSorted[j] > toBeSorted[j + 1])
{
swap(toBeSorted,j, j + 1);
}
}
printAll(toBeSorted, 10);
}
}
void main(void)
{
int data[10] = { 31, 24, 56, 1, 4, 10, 6, 76, 87, 30 };
printf("----------------------------------------\n");
printf("Before being sorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
performBubbleSort(data, 10);
printf("After being BubbleSorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
}
|
cs |
# The result
# The source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 |
#include<stdio.h>
void printAll(int * toBeDisplayed, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d, ", toBeDisplayed[i]);
}
printf("\n");
return;
}
void swap(int * arr, int i, int j)
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
return;
}
int findSmallest(int * arr, int start_idx, int sz)
{
int smallest_idx = start_idx;
int smallest = arr[start_idx];
int i;
for (i = start_idx; i < sz; i++)
{
if (arr[i] < smallest)
{
smallest = arr[i];
smallest_idx = i;
}
}
return smallest_idx;
}
void performSelectionSort(int * toBeSorted, int sz)
{
int i, j;
for (i = 0; i < sz; i++)
{
//가장 작은것을 찾는다.
j = findSmallest(toBeSorted, i, sz);
swap(toBeSorted, i, j);
printAll(toBeSorted, 10);
}
}
void main(void)
{
int data[10] = { 31, 24, 56, 1, 4, 10, 6, 76, 87, 30 };
printf("----------------------------------------\n");
printf("Before being sorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
performSelectionSort(data, 10);
printf("After being SelectionSorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
} |
cs |
# The result
#The source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 |
#include<stdio.h>
void printAll(int * toBeDisplayed, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d, ", toBeDisplayed[i]);
}
printf("\n");
return;
}
void swap(int * arr, int i, int j)
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
return;
}
void performInsertionSort(int * toBeSorted, int sz)
{
int i, j;
for (i = 1; i < sz; i++)
{
j = i;
while ((j - 1 >= 0) && (toBeSorted[j - 1] > toBeSorted[j]))
{
swap(toBeSorted, j - 1, j);
j--;
}
printAll(toBeSorted, sz);
}
}
void main(void)
{
int data[10] = { 31, 24, 56, 1, 4, 10, 6, 76, 87, 30 };
printf("----------------------------------------\n");
printf("Before being sorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
performInsertionSort(data, 10);
printf("After being InsertionSorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
}
|
cs |
# The result
# The source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 |
#include<stdio.h>
void printAll(int * toBeDisplayed, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d, ", toBeDisplayed[i]);
}
printf("\n");
return;
}
void swap(int * arr, int i, int j)
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
return;
}
void performQuickSort(int * toBeSorted, int pivot_idx, int left_idx, int right_idx, int sz)
{
int left = left_idx; int right = right_idx;
printf("pivot : %d, left : %d, right : %d \n", pivot_idx, left, right);
printAll(toBeSorted, sz);
while (left < right)
{
while (toBeSorted[pivot_idx] > toBeSorted[left] && left <= right_idx)
{
left++;
}
while (toBeSorted[pivot_idx] < toBeSorted[right] && right >= left_idx)
{
right--;
}
if (right > left)
{
swap(toBeSorted, left, right);
}
else
{
swap(toBeSorted, pivot_idx, right);
performQuickSort(toBeSorted, pivot_idx, left_idx, right - 1, sz);
performQuickSort(toBeSorted, right + 1, right + 2, right_idx, sz);
printAll(toBeSorted, sz);
}
}
}
void main(void)
{
int data[10] = { 31, 24, 56, 1, 4, 10, 6, 76, 87, 30 };
printf("----------------------------------------\n");
printf("Before being sorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
//performQuickSort(data, pivot, left, right, sz);
performQuickSort(data, 0, 1, 9, 10);
printf("After being QuickSorted \n");
printAll(data, 10);
printf("----------------------------------------\n");
}
|
cs |
# The result
