정렬3 [정렬] 선택 정렬 (Selection Sort) 원소를 넣을 위치를 정해놓고 어떤 원소를 넣을지 찾아서 정렬한다. 오름차순의 경우, 가장 작은 값을 찾아서 왼쪽부터 정렬을 하거나, 가장 큰 값을 찾아 오른쪽부터 정렬을 하는 방식이다. 1. i = ( 1 ~ (n - 1) )인덱스까지 탐색 2. j = ( (i + 1) ~ n ) 인덱스까지 탐색 3. j의 값 중에 가장 작은 값을 찾아 i번째의 값과 위치를 바꾼다. 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } void Selection(int* arr, int size) { int min, tmp; fo.. 2020. 1. 20. [정렬] 삽입 정렬 (Insertion Sort) 두 번째 자료부터 시작하여 앞에 자료들과 비교하여 알맞은 위치에 자료를 넣는 형식의 정렬이다. 비교를 하는 앞의 배열은 이미 정렬이 되어있다. 즉, n번째 자료를 비교할 때 0 ~ (n - 1) 번째 자료는 정렬이 되어있다. 손에 카드를 들고 정렬하는 방식과 유사하다. 1. i = (1 ~ n)인덱스까지 탐색 2. j = ( (i - 1) ~ 0 ) 인덱스까지 탐색 3. j번째 값이 i번째 값보다 크면 j + 1의 값에 j의 값을 할당하고, 크지 않으면 해당 위치에 i번째 값을 삽입 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } pri.. 2020. 1. 20. [정렬] 버블 정렬 (Bubble Sort) 소개 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 다른 정렬 알고리즘에 비해 느린 편이지만, 코드가 간단하다. 정렬 과정 첫 번째 탐색 1. 5와 3을 비교 2. 앞에 있는 5가 더 크므로 5와 3의 위치를 바꾼다. 3. 5와 1을 비교 4. 앞에 있는 5가 더 크므로 5와 1의 위치를 바꾼다. 5. 5와 9를 비교 6. 뒤에 있는 9가 더 크므로 위치를 변경하지 않는다. 7. 9와 7을 비교 8. 앞에 있는 9가 더 크므로 9와 7의 위치를 바꾼다. 9. 첫 번째 순회가 끝난 배열 첫 번째 탐색의 과정을 보면 가장 큰 수가 맨 뒤로 이동하게 된다. 즉, 매 순회마다 정렬된 수를 제외한 가장 큰 수가 맨 뒤로 가 뒤에서부터 정렬이 된다. 그러므로 맨 순회마다 배열의 전체를 탐색할 필요 없이 정.. 2019. 11. 21. 이전 1 다음
