🧪 컴퓨터과학 : CS

[Alogrithm] 삽입 정렬 (Injection Sort)

삽입 정렬 (Injection Sort) 삽입 정렬은, 한 배열을 '앞 배열'과 '뒷 배열'로 쪼개어 '뒷 배열'의 요소를 정렬된 '앞 배열'에 들어갈 올바른 위치를 찾아 삽입하는 정렬이다. 잘 이해가 되지 않을 수 있으므로, 하나씩 설명을 해보겠다. 다음과 같이 주어진 배열이 있다고 하자. array = [3, 4, 5, 2, 1, 6, 7] 3 4 5 2 1 6 7 정렬 알고리즘 전, 주어진 배열을 다음과 같이 빨간 부분과 파란 부분으로 볼 수 있다. 빨간 부분은 이미 정렬이 된 '앞 배열', 파란 부분은 '앞 배열'에 삽입이 되기 위해 대기하고 있는 '뒷 배열'로 이해하면 좋다. 정렬 알고리즘은 '뒷 배열'에 들어있는 첫 번째 원소부터 시작하므로, 전체 배열로 생각하면 두 번째 요소부터 정렬 대상이..

[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort) 선택 정렬은, 배열의 제일 앞에서부터 해당 자리에 들어갈 숫자를 선택하는 정렬이다. 들어갈 숫자를 결정하는 것은 배열 내의 모든 요소를 비교해 가장 작은 것을 선택한다. 다음 loop 부터는 이미 자리가 결정된 숫자는 비교하지 않고, 나머지 수들 중에 들어갈 것을 찾기를 반복한다. 즉, 1번째 loop에서는 배열의 첫 번째 자리에 들어갈 원소를 n개를 모두 비교해 선택하고, 2번째 loop에서는 이미 결정된 첫 번째 자리의 숫자를 제외한 나머지 n-1개를 비교해 두 번째 자리에 들어갈 숫자를 결정한다. 3번재 loop에서는 이미 결정된 1~2번째 자리의 숫자를 제외한 나머지 n-2개를 비교해 세 번째 자리에 들어갈 숫자를 결정하고, 모든 자리에 들어갈 숫자가 정해..

[Algorithm] 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort) 버블 정렬은, 이웃한 두 숫자를 계속해서 비교하며 정해진 규칙에 따라 자리를 스위칭하는 정렬이다. 예를 들어, 오름차순이라면 이웃한 두 숫자 중 더 큰 숫자가 뒷 자리로 이동하도록 서로 바꿔준다는 것이다. 버블 정렬이라는 이름이 붙은 이유는 가장 가벼운 것이 위로 올라가는 거품의 움직임에 빗대어 붙여진 이름이라 한다. (그렇게 공감이 가진 않는다) 위 그림은 버블 정렬의 switching 하는 과정을 보여주는 그림이다. 연속된 두 이웃의 값을 비교해 더 높은 값을 뒷자리로 스위칭하게 된다. 특징은, 한 loop가 돌 때마다, 제일 마지막 자리의 숫자가 결정된다는 것이다. 다음 loop는 n-1번째 자리의 숫자가, 그 다음은 n-2번째 자리의 숫자가 결정된다는 특징을 알..