본문 바로가기
반응형

sort

카테고리 없음 O(n^2) 정렬 - 버블정렬(Bubble Sort) 시간복잡도 O(n^2)의 버블정렬입니다. 배열을 n바퀴 순회하며 인접한 인덱스의 배열 값끼리 비교연산(최대 n번) Swap함으로써 정렬을 실행합니다. #include using namespace std; #define MAX 500 int ar[MAX]; void Swap(int a, int b) { ar[a] = ar[a] + ar[b]; ar[b] = ar[a] - ar[b]; ar[a] = ar[a] - ar[b]; } void BubbleSort(int size) { for (int i = 0; i ar[j + 1]) { Swap(j, j + 1); } } } } int mai..
개발/알고리즘 & 자료구조 O(n+k) 정렬 - 카운팅 정렬(Counting Sort) 수열의 길이가 매크로 선언된 RAN인 수열을 정렬하는 카운팅 정렬입니다. 시간복잡도는 O(MAX+RAN)입니다. 수열을 한 바퀴 순회하면서 ar[i]값에 따라서 cnt[ar[i]]를 1씩 증가시킵니다. #include #include using namespace std; #define MAX 500 #define RAN 10000 int ar[MAX]; int cnt[RAN]; void CountingSort(int size) { memset(cnt, 0, sizeof(cnt)); for (int i = 0; i > n; for (int j = 0; j > ar[j]; }..
개발/알고리즘 & 자료구조 O(n^2) 정렬 - 선택정렬(SelectionSort) 오름차순으로 정렬하기 위해 2중 for문을 이용합니다. 행렬의 i 위치보다 작은 값중에 가장 작은 값을 (i+1)~(size-1)위치에서 찾아, i위치와 교환(Swap) 합니다. 시간복잡도는 삽입정렬이나 버블정렬과 같이 빅오 n제곱을 갖습니다. #include #include using namespace std; #define MAX 500 int ar[MAX]; void Swap(int idx1, int idx2) { int tmp = ar[idx1]; ar[idx1] = ar[idx2]; ar[idx2] = tmp; } void SelectionSort(int size) { for (int i = 0; i < size - 1; i++) { int idx = i, min = ar[i]; for (int..
728x90
반응형

티스토리툴바