알고리즘
-
[알고리즘] 삽입 정렬(Insertion Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 6. 17:32
아래의 숫자들을 오름차순으로 정렬한다고 생각해보자 1 10 5 8 7 6 4 3 2 9 버블 정렬과 선택정렬을 사용 할 수도 있지만, 삽입 정렬을 사용하면 특정상황에 따라서는 보다 효율적으로 정렬할 수 있다. 다른 정렬들은 무조건 위치를 바꾸는 방식이였지만, 삽입정렬의 다른점은 '필요할 때만' 위치를 바꾼다는 것이다. 예를들어 보자, 아래와 같은 숫자들을 오름차순 정렬한다고 했을때, 삽입정렬은 1 10 5 8 7 6 4 3 2 9 바로 옆의 10과 대소를 비교한다. 10은 1의 앞 혹은 지금 현재 자리에 있을 수 있는데, 오름차순이기때문에 현재 위치를 그대로 유지하면 된다. 그다음 10 과 5를 비교해보면, 5가 더 작기때문에 10과 5의 자리를 바꿔준다. 조금 더 쉽게 생각하면 빈칸이 있다고 생각을 해..
-
[알고리즘] 선택 정렬 (Selection Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 4. 11:28
예를 들어 *1 10 5 8 7 6 4 3 2 9 * 라는 숫자들을 오름차순으로 정렬하려고 한다고 가정해보자 사람이라면 직관적으로 보고 작은 수 를 찾아 순서대로 정렬하겠지만, 컴퓨터는 배열을 하나하나 읽기전 까지는 어떤 값이 들어있는지 알지 못한다. 따라서 정렬을 위해서는 알고리즘이 필요하다. 그 중에서도 선택정렬은 모든 배열을 탐색 후, 가장 작은 수를 앞으로 보내는 방식으로 동작한다. ex) arr[10] *1 10 5 8 7 6 4 3 2 9 * 모든 배열을 탐색 후 , 1이 가장 작은 숫자로 알맞은 위치에 있으므로, 이제는 1을 제외한 10 부터 9까지를 탐색해준다. *1 2 5 8 7 6 4 3 10 9 * 나머지 배열중에 가장 작은 수는 2이므로 arr[1] 인덱스의 값으로 넣어주고 원래 2..
-
[알고리즘] 병합 정렬알고리즘 & 자료구조 2021. 1. 21. 16:31
병합 정렬 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 그리고 이 과정은 재귀적으로 구현된다. 아래의 숫자들을 오름차순으로 정렬해 보자 7 4 5 2 6 3 8 1 먼저 숫자들을 반으로 나눈다. 7 4 5 2 | 6 3 8 1 그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다. 7 4 | 5 2 | 6 3 8 1 마지막으로 한 번 더 나눠준다 7 | 4 | 5 2 | 6 3 8 1 이제 숫자가 7 과 4로 나뉘어져있다. 두 숫자를 병합 해보자. 단, 작은 숫자가 먼저 오도록한다 4 7 | 5 2 | 6 3 8 1 마찬가지로 5 ,2 역시 나눈 후 병합해보면 4 7 | 2 5 | 6 3 8 1 이제 4 7 | 2 5 부분을 병합 2 4 5 7..