선택 정렬 알고리즘 분석 및 C 구현
8437 단어 algorithmsccomputerscience
O(n2)O(n^2)O(n2)
그러나 이것은 정말 간단한 알고리즘이고 분석은 간단합니다. 의사 코드를 보고 분석한 다음 마지막으로 C 언어를 사용한 예를 살펴보겠습니다.
ALGORITHMSelectionSort(A[0..n−1])//주어진 배열을 선택 정렬로 정렬//입력: 정렬 가능한 요소의 배열 A[0..n - 1]//출력: 배열 A[0..n - 1] i←0 ~n−2 domin← ifor j←i+1 ~n−1 doifA[j]
\newline\text{//주어진 배열을 선택 정렬로 정렬}
\newline\text{//입력: 정렬 가능한 요소의 배열 A[0..n - 1]}
\newline\text{//출력: 배열 A[0..n - 1]이 내림차순으로 정렬됨}
\newline
\bold{for}\space i\gets 0\space\bold{to}\space n-2\space\bold{do}
\newline\quad min\gets\space i
\newline\quad\bold{for}\space j\gets i + 1\space\bold{to}\space n-1\space\bold{do}
\newline\quad\quad\bold{if} A[j] < A[min]\space min\gets j
\newline\quad swap\space A[i]\space 및\space A[min]
ALGORITHMSelectionSort(A[0..n−1])//주어진 배열을 선택 정렬로 정렬//입력: 정렬 가능한 요소의 배열 A[0..n - 1]//출력: 배열 A[0..n - 1] i←0 ~n−2 domin← ifor j←i+1 ~n−1 doifA[j]
여기에서 알고리즘 분석을 볼 수 있습니다. 두 개의 for 루프가 있으므로 두 개의 합계로 분석을 시작합니다.
C(n)=∑i=0n−2∑j=i+1n−11=∑i=0n−2[(n−1)−(i+1)+1]=∑i=0n−2(n −1−i)
C(n) =\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1} 1 =\sum_{i=0}^{n-2}[( n-1)-(i+1)+1] =\sum_{i=0}^{n-2}(n-1-i)
C(n)=i=0∑n−2j=i+1∑n−11=i=0∑n−2[(n−1)−(i+1)+1]=i =0∑n−2(n−1−i)
조금 더 단순화하면 분자에 2차 요소가 있는 분수로 변하는 것을 볼 수 있습니다. 이 요소를 무한으로 제한하면
∞\infty ∞
, 우리는 단지 일반
n2n^2 n2
C(n)=∑j=i+1n−11=∑i=0n−2(n−1−i)=(n−1)n2=(n2−n)2
C(n) =\sum_{j=i+1}^{n-1} 1 =\sum_{i=0}^{n-2}(n-1-i) =\frac{(n-1 )n}{2} =\frac{(n^2-n)}{2}
C(n)=j=i+1∑n−11=i=0∑n−2(n−1−i)=2(n−1)n=2(n2−n)
오(n2)
오(n^2)
오(n2)
마지막으로 C를 사용한 예제를 볼 수 있습니다. 다음을 사용하여 컴파일할 수 있습니다.
gcc selection_sort.c -o selection_sort
#include <stdio.h>
void swap(int *a, int i, int min, int i_value, int min_value) {
a[i] = min_value;
a[min] = i_value;
}
int selection_sort(int *a, int n) {
int i, j, min;
for (i = 0; i < (n - 1); i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a, i, min, a[i], a[min]);
}
return 0;
}
int main() {
int n = 7;
int array[] = {89, 45, 68, 90, 29, 34, 17};
printf("Before: \n");
for (int x = 0; x < n; x++) {
printf("%d, ", array[x]);
}
printf("\n\n");
selection_sort(array, n);
printf("After: \n");
for (int x = 0; x < n; x++) {
printf("%d, ", array[x]);
}
printf("\n");
return 0;
}
Reference
이 문제에 관하여(선택 정렬 알고리즘 분석 및 C 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/rodolfobandeira/selection-sort-algorithm-analysis-and-implementation-in-c-k8m텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
