*참고 영상 : https://youtu.be/GUDLRan2DWM
#1 Selection Sort 선택정렬
1. Scan the whole array to find the minimum
2. Instead of filling 1 in 0th index on array B, SWAP with the 0th index. Because that's where 1 belongs, it belongs to 0th index.
3. Look for the next minimum, 1 need NOT to be considered. Scan index 1 to 5th. *The array is divided into 2 parts sorted or else. And we need to do (n-2) passes.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SWAP(X,Y) if((X)!=(Y)) (X)^=(Y)^=(X)^=Y
void SelectionSort(int* A, int n) {
for (int i = 0; i < n - 1; i++) {
int iMin = i;
for (int k = i + 1; k < n; k++) {
if (A[k] < A[iMin])
iMin = k;
}
SWAP(A[i], A[iMin]);
}
}
int main(void) {
int A[] = { 2,7,4,1,5,3 };
SelectionSort(A, 6);
for (int i = 0; i < 6; i++)
printf("%d ", *(A + i));
}
#2 Insertion Sort 삽입정렬
"Create a hole"
ex) int A[] = {7, 2, 4, 1, 5, 3}
1. Sorted subject or Sorted half. *0th index
2. Picking elements from the sorted subset and keep on inserting them into sorted.
* Keep expanding Sorted subset and also dividing by 2 ... sorted(empty) & unsorted
And create a hole in particular position... same as picking elements
3. Shift all numbers greater than '2'in the sorted part by one position to the right.
오름차순이니까 pick 한 수보다 큰 수들은 모두 오른쪽으로 밀면 된다. 만약 내림차순이라면 반대가 되겠지.
Finally 7 will be shifted one position toward right. And hole will go position 0th, fill up 2.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void InsertionSort(int* A, int n) {
int value, hole;
for (int i = 1; i < n; i++) {
value = A[i]; //삽입될 숫자
hole = i; //그리고 그 위치(인덱스) = hole
while (hole > 0 && A[hole - 1] > value) {
A[hole] = A[hole - 1];
hole = hole - 1;
}
A[hole] = value;
}
}
int main(void) {
int A[] = { 7,2,4,1,5,3 };
InsertionSort(A, 6);
for (int i = 0; i < 6; i++)
printf("%d ", *(A + i));
}
'Major > Data Structure & Algorithm' 카테고리의 다른 글
연결리스트 노드 개수 카운팅,특정 노드 순서 바꾸기,첫번째 노드 삭제하기 ... (0) | 2022.04.03 |
---|---|
[JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |
[python+]연결리스트,노드,삽입,삭제 (0) | 2022.04.02 |
배열 순차 자료구조, 선형 리스트, 다항식의 순차 자료구조 (0) | 2022.03.20 |
[2월 5일] 버블정렬 알고리즘, 문자수만큼 회전하기 (0) | 2022.02.15 |