본문 바로가기
728x90

전체 글196

[C/algorithm]알고리즘 퀵 정렬(quick sort) C언어 ▶퀵 정렬 재귀 알고리즘이다. 피벗(pivot)을 선택해 피벗보다 작은 원소는 배열의 왼쪽으로, 큰 원소는 배열의 오른쪽으로 이동해 두 부분으로 나눈다. 왼쪽과 오른쪽으로 나눈 부분 배열을 각각 정렬한다. 평균 성능 시간 복잡도 : O(nlogn) 최악 성능 시간 복잡도 : O(n^2) 최선 성능 시간 복잡도 : O(nlogn) ▶소스코드 void QuickSort(int arr[], int left, int right) { int L = left, R = right; int temp; int pivot = arr[(L + R) / 2]; while (L pivot) R--; if (L left) QuickSort(arr, left, R); } 위 소스는 오름차순 정렬이다. ▶해석 퀵 정렬 함수 인자 l.. 2021. 11. 20.
[C/algorithm]알고리즘 합병(merge) 정렬 C언어 ▶합병 정렬 각 단계에서 입력을 반으로 나눠 재귀 호출해 다시 합치면서 정렬 평균 성능 시간 복잡도 : O(nlogn) 최악 성능 시간 복잡도 : O(nlogn) 최선 성능 시간 복잡도 : O(nlogn) ▶소스코드 #define SIZE 10 int temp[SIZE]; void Merge(int arr[], int left, int mid, int right) { int L = left; int R = mid + 1; int n = left; while (L 2021. 11. 20.
[C/algorithm]알고리즘 삽입 정렬(Insertion Sort) C언어 ▶삽입 정렬 버블 정렬보다 조금 더 나은 정렬. 배열의 앞부분부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아서 삽입한다. 순회한 원소들의 부분 배열은 정렬 상태를 유지함. 평균 성능 시간 복잡도 : O(n^2) 최악 성능 시간 복잡도 : O(n^2) 최선 성능 시간 복잡도 : O(n) ▶소스코드 void InsertionSort(int arr[], int size) { int i, j, temp; for (i = 1; i 0 && arr[j - 1] > temp; j--) { arr[j] = arr[j - 1]; } arr[j] = temp; } } 위 소스는 오름차순 정렬이다. ▶해석 자신보다 앞에 있.. 2021. 11. 20.
[C/algorithm]알고리즘 버블 정렬(Bubble Sort) C언어 ▶버블 정렬(아래에 업그레이드된 버블 정렬 있음) 가장 느린 정렬 중 하나. 인접한 값의 각 쌍을 비교하여 교환하며 연속적으로 다음 쌍을 비교한다. 오름차순이라면 가장 큰 값이 배열의 끝으로 이동하며 다음 정렬 때 제외된다. 평균 성능 시간 복잡도 : O(n^2) 최악 성능 시간 복잡도 : O(n^2) ▶소스코드 void BubbleSort(int arr[], int size) { int i, j, temp; for (i = 0; i arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 위 소스는 오.. 2021. 11. 20.
728x90