본문 바로가기

Tech/Algo

Tech/Algo 2022. 5. 6. [알고리즘] 쉘 정렬 (shell sort) 쉘 정렬은 어느 정도 정렬된 배열을 굉장히 빠르게 정렬하는 알고리즘 입니다. 셀 정렬은 일정한 간격 g만큼 떨어진 요소만을 대상으로 삽입 정렬을 반복합니다. #include #include #include #include #include using namespace std; long long cnt; int l; int A[100000]; int n; vectorG; void insertionSort(int A[], int n, int g) { for(int i = g; i = 0 && A[j] > v) { A[j + g] = A[j]; j -= g; cnt++; } A[j + g] = v; } } void shel..
Tech/Algo 2022. 5. 6. [알고리즘] 안정적인 정렬 안정적인 출력이란 같은 숫자를 가진 카드가 여러 개 있을 때, 이들을 입력한 순서대로 출력하는 것을 의미한다. 예를들면, H4 C9 S4 D2 C3 입력 값이면 숫자로 오름차순으로 정렬하면, D2 C3 H4 S4 C9가 출력이 된다. 버블정렬은 안정적인 정렬이라고 볼 수 있다. #include using namespace std; struct Card { char suit, value;}; void bubble(struct Card A[], int N) { for(int i = 0; i = i+1; j--) { if(A[j].value < A[j - 1].value) { Card t = A[j]; A[j] = A[j - 1]; A[j - 1] ..
Tech/Algo 2022. 5. 6. [알고리즘] 선택 정렬 (Selection sort) 선택 정렬은 각각의 단계에서 하나의 최소값을 선택해서 정렬하는 직관적인 알고리즘이다. #include int selectionSort(int A[], int N) { int i, j, t, sw = 0, minj; for(i = 0; i < N-1; i++){ minj = i; for(j = i; j < N; j++) { if(A[j] < A[minj]) minj = j; } t = A[i]; A[i] = A[minj]; A[minj] = t; if( i != minj) sw++; } return sw; } int main() { int A[100], N, i, sw; scanf("%d", &N); for(i = 0; i < N; i++) scanf("%d", &A[i]); sw = selectionSo..
Tech/Algo 2022. 5. 6. [알고리즘] 버블 정렬 (bubble sort) 버블 정렬은 이름 그대로 거품 (bubble)이 수면 위로 올라가는 것 처럼 배열 요소가 움직입니다. 버블 정렬은 다음과 같은 알고리즘으로 배열을 오름차순으로 정렬 합니다. #include using namespace std; int bubbleSort(int A[], int N) { int sw = 0; bool flag = 1; // swap이 한번도 없을 경우, operation 중단! for(int i = 0; flag; i++) { flag = 0; for(int j = N - 1; j >= i + 1; j--) { if(A[j] < A[j-1]) { swap(A[j], A[j - 1]); flag = 1; sw++; } } } return sw; } int main() { int A[100],..
Tech/Algo 2022. 5. 6. [알고리즘] 삽입정렬 (Insertion Sort) 책에서는 간단한 알고리즘 이라고 소개하고 있지만, 삽입정렬의 알고리즘은 초보자에게는 어려울 것이다. 배열수(N)이 라고 하면 복잡도는 O(N^2)이 되어 최악의 알고리즘이라고 할 수 있지만, 이미 어느 정도 정렬되어 있다고 가정하면 그렇게 나쁜 알고리즘은 아니다 ㅋㅋ arr = [8, 5, 4, 3, 2, 1] 이란 정수 배열이 있다고 가정하자. 이 알고리즘의 핵심은 i번째 배열의 값을 저장 후 0~(i-1) 배열의 값과 비교하는 과정이 있는데 0~(i-1)의 배열은 정렬이 되어 있다. i의 값을 1부터 N-1 (N은 배열수)까지 순회하면서 다음과 같은 작업을 진행한다. arr = [8, 5, 4, 3, 2, 1] print(arr) def insert_sort(arr): for i in range(1,..

티스토리툴바