쥬코딩

오늘은 계수정렬에 대해 알아보겠습니다. 계수정렬은 x보다 작은 원소의 개수가 i-1개 라면, 정렬 후 x는 i번째에 위치해야 한다는 것을 이용합니다. 아래와 같은 arr배열에 있는 수를 정렬해야 한다고 할 때, arr 안에 있는 각 숫자가 몇 개 들어있는지 저장하는 cnt배열이 있습니다. cnt배열의 크기는 (arr 안에 있는 숫자 중 가장 큰 수 - 가장 작은 수 + 1)로 지정할 수 있습니다. cnt배열은 0으로 초기화 해준 뒤, arr 안에 있는 각 숫자가 몇 개 들어있는지 저장해야 합니다. 그 다음 cnt배열의 값들을 누적해서 다시 cnt에 저장하면 그것이 각 수가 저장될 배열의 위치가 됩니다. 이 부분에 맨 처음에 말한 "x보다 작은 원소의 개수가 i-1개 라면, 정렬 후 x는 i번째에 위치해야..

알고리즘 2021. 12. 20. 15:21

오늘은 삽입정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다. 오름차순으로 정렬하기 위해서는 정렬할 값과 정렬된 배열의 끝(가장 큰 수)부터 차례대로 비교해가면서 알맞은 자리에 삽입하면 됩니다. 정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다. 처음에는 인덱스가 0인 부분만 정렬된 상태이고 그 뒤의 숫자는 정렬되지 않은 즉, 정렬할 값이라고 생각하면 됩니다. 배열 위의 화살표는 현재 삽입정렬을 할 숫자이고, 배열 밑의 화살표는 삽입정렬 수행 시 비교하는 숫자들과 연결한 것입니다. 현재 삽입정렬를 할 숫자를 key라고 부르겠습니다. 반복문을 돌면서 정렬된 부분(보라색 부분)의 숫자가 key값보다 크면 뒤로 한칸씩 밀어주고, 만약 정렬된 부분(보라색 부분)의 숫자가 key..

알고리즘 2021. 12. 14. 14:49

안녕하세요 지코딩입니다. 오늘은 선택정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다. 오름차순으로 정렬하기 위해서는 정렬되지 않은 배열 인덱스 중 가장 작은 값을 선택해서 정렬되지 않은 부분의 맨 앞의 값과 자리를 바꾸면서 진행하면 됩니다. 정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다. 처음에는 배열의 모든 인덱스가 정렬되지 않은 상태입니다. 정렬되지 않은 인덱스 중 가장 작은 값을 찾고 정렬되지 않은 배열 부분의 맨 앞의 값과 자리를 바꿉니다. 위의 과정을 반복하면 다음과 같습니다. 마지막 남아있는 수는 전체 배열 중 가장 큰 수 이면서 정렬되지 않은 배열 인덱스 중 가장 작은 수 이기 때문에 따로 정렬을 하지 않아도 됩니다. 이제 전체 코드를 공유하겠습니다. ..

알고리즘 2021. 12. 13. 11:57