C 알고리즘 배열 정렬 - sonkoni/Koni-Wiki GitHub Wiki
거품 정렬은 요소갯수가 늘어날수록 비교 부하가 심하다(n² 으로 증가) 그래서 퀵정렬을 많이 쓴다.
- 처음부터 끝까지 요소를 순회하며 모든 요소를 비교
- 현재 값과 다음값을 비교하여 큰 값을 다음으로 보냄(오름차순)
#include <stdio.h>
void bubble_sort(int arr[], int count) {
int temp;
for (int i = 0; i < count; i++) {
for (int j = 0; j < count - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main(int argc, char *argv[]) {
int numArr[] = {8, 4, 2, 5, 3, 7, 10, 1, 6, 9};
bubble_sort(numArr, sizeof(numArr) / sizeof(int));
for (int i = 0; i < sizeof(numArr) / sizeof(int); i++) {
printf("%d ", numArr[i]);
}
printf("\n");
return 0;
}
// 1 2 3 4 5 6 7 8 9 10 ┌──┐8
[8][4][2][5][3][7][10][1][6][9]
4└──┘
┌──┐8
[4][8][2][5][3][7][10][1][6][9]
2└──┘
┌──┐8
[4][2][8][5][3][7][10][1][6][9]
5└──┘
.......
#include <stdlib.h>
void qsort(void *ptr, size_t count, size_t size, int (*comp)(const void *, const void *));
void qsort(정렬할포인터, 요소갯수, 요소크기, 비교함수포인터);
== 반환값이 1이면 스위칭이 발생한다. ==
오름차순
comp return -1 : a < b
comp return 0 : a == b
comp return 1 : a > b
내림차순
comp return 1 : a < b
comp return 0 : a == b
comp return -1 : a > b#include <stdio.h>
#include <stdlib.h>
// 오름차순: a > b => 1 반환
int AscendingCompare(const void *a, const void *b) {
int num1 = *(int *)a; // void 포인터를 int 포인터로 형변환 한 후, 역참조로 값을 가져옴
int num2 = *(int *)b; // void 포인터를 int 포인터로 형변환 한 후, 역참조로 값을 가져옴
if (num1 < num2) {
return -1;
} else if (num1 > num2) {
return 1;
}
return 0; // 두 조건 다 만족하지 않으면(a==b 일 때), 0 반환
}
// 내림차순: a < b => 1 반환
int DescendingCompare(const void *a, const void *b) {
int num1 = *(int *)a; // void 포인터를 int 포인터로 형변환 한 후, 역참조로 값을 가져옴
int num2 = *(int *)b; // void 포인터를 int 포인터로 형변환 한 후, 역참조로 값을 가져옴
if (num1 > num2) {
return -1;
} else if (num1 < num2) {
return 1;
}
return 0; // 두 조건 다 만족하지 않으면(a==b 일 때), 0 반환
}
int main(int argc, char *argv[]) {
int numArr[] = {8, 4, 2, 5, 3, 7, 10, 1, 6, 9};
size_t arrCount = sizeof(numArr) / sizeof(int);
size_t eleSize = sizeof(int);
// 오름차순
qsort(numArr, arrCount, eleSize, AscendingCompare);
printf("Ascending: ");
for (int i = 0; i < arrCount; i++) {
printf("%d ", numArr[i]);
}
printf("\n");
// 내림차순
qsort(numArr, arrCount, eleSize, DescendingCompare);
printf("Descending: ");
for (int i = 0; i < arrCount; i++) {
printf("%d ", numArr[i]);
}
printf("\n");
return 0;
}
// Ascending: 1 2 3 4 5 6 7 8 9 10
// Descending: 10 9 8 7 6 5 4 3 2 1여기서 const void * 는 void 형 상수를 가리키는 포인터이다. compare 함수가 포인터를 전달받았을 때 포인터가 가리키는 값이 상수라는 뜻이다. 따라서 compare 함수 안에서 값을 임의로 변경해서는 안 된다. 코드 인자로 이렇게 사용한다는 것은, 함수 사용자에게 이 함수 내부에서는 값을 임의로 바꾸지 않는다 즉 읽기전용으로 쓴다는 것을 나타내기 위함이다.