Coding Diary

1. 개념 일의 자리만 보고 정렬을 한다. 그 이후에 십의 자리만 보고 정렬을 한다. 즉 기수만 보고 정렬을 진행하는 것이다. 여기서 기수란 각 진수에서 표현할 수 있는 수를 말한다. 예를 들어 10진수면 기수는 0~9이다. 보통 이런 기수 정렬은 기수를 담을 큐를 만들어 놓고, 수를 기수에 맞는 큐에 넣었다 빼며 정렬을 진행한다. 예를 들어 10 32 11 25 이런 수가 있을 때, 0을 담는 큐를 만들고, 1을 담는 큐를 만들고... 9를 담는 큐를 만든다. 그리고 10의 일의자리는 0이니 0을 담는 큐에 10을 넣는다. 32의 일의자리는 2이니 2를 담는 큐에 32를 넣는다. 11의 일의자리는 1이니 1을 담는 큐에 11을 넣는다. 25의 일의자리는 5이니 5를 담는 큐에 25를 넣는다. 그리고 나..

1. 개념 하나의 배열을 크기가 같은 2개의 배열로 분할한다. 분할은 분할 대상의 배열 길이가 2이상이면 계속 반복하다 분할 대상 배열 길이가 1이하가 되면 반복을 멈춘다. 분할된 배열을 병합하는데, 정렬을 하면서 병합을 진행한다. 병합을 진행할 때는 병합 대상이 되는 2개의 배열 각각에 포인터를 두고, 포인터가 가리키는 원소 중 더 작은 것을 병합 결과 배열에 놓고, 병합 결과 배열에 놓인 원소의 포인터는 증가시킨다. 2. 특징 분할 정복 방법이 적용된다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 각각을 해결할 때는 재귀적으로 함수 호출을 진행하여 해결한다. 만약 배열로 데이터를 다루면 제자리 정렬이 아니다. 병합된 내용을 담을 추가 메모..

1. 개념 배열에서 피봇을 하나 정한다. 맨 왼쪽에서 시작해서 배열을 살피는 화살표가 하나 있고, 맨 오른쪽에서 시작해서 배열을 살피는 화살표가 하나 있다. 왼쪽 시작 화살표를 옮겨가며 피봇보다 크거나 같은 원소를 찾는다. 오른쪽 시작 화살표를 옮겨가며 피봇보다 작은 원소를 찾는다. - a 만약 왼쪽 시작 화살표가 원소를 하나 찾고, 오른쪽 시작 화살표가 원소를 하나 찾으면 둘을 교환한다. 교환 후 왼쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 크거나 같은 원소를 찾고, 오른쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 작은 원소를 찾는다. - b-1 만약 왼쪽 시작 화살표와 오른쪽 시작 화살표가 만나면 만난 위치에 있는 원소와 피봇을 교환한다. 교환된 피봇은 확정된다. - b-2..

1. 개념 맨 앞부터 시작. 첫 번째 원소와 그 다음 원소를 비교. 만약 다음 원소가 더 작으면 교환하고 그렇지 않으면 그대로 둠. 그리고 두 번째 원소, 세 번째 원소로 가서 앞에서 진행했던 거를 반복. 이걸 한 싸이클 진행하면 맨 뒤에 가장 큰 수가 남게 되고 그 수는 고정이 된다. 위와 같은 과정을 반복하면 버블정렬이 완료됨 2. 특징 1) 장점 안정 정렬이 가능함(같은 원소가 있어도 같은 원소의 상대적인 위치, 즉 누가 앞에 있던 거고 누가 뒤에 있던 건지가 바뀌지 않음) 구현이 쉬움 추가 메모리가 거의 필요하지 않음 2) 단점 교환 과정이 많음 시간 복잡도가 O(n2) 3. 시간복잡도 1) 비교 횟수 항목의 개수가 n이면 (n-1) + (n-2) + (n-3)... + 1 만큼 비교를 한다. 이..

1. 개념 배열의 원소를 하나씩 살피면서, 살피는 원소와 살피는 원소 앞에 있는 원소를 비교해서 만약 앞에 있는 원소보다 작다면 살피는 원소를 앞으로 보낸다. 더 이상 앞으로 보낼 수 없을 때까지 반복한다.(오름차순 기준) 2. 특징 1) 장점 안정한 정렬 방법(정렬하면서 같은 원소가 있어도 위치가 변하지 않는다) 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다. 2) 단점 비교적 많은 레코드들의 이동을 포함한다. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다. 3. 시간복잡도 1) 최선(다 정렬되어 들어올 경우) 비교횟수 target이 target 바로 전 것과 비교되고 ..

1. 개념 배열의 원소를 순서대로 살피면서, 살피는 원소 아래에 있는 모든 원소를 확인해서 만약 더 작은 것이 있다면 현재 살피는 원소와 해당 원소를 바꾼다. 2. 특징 제자리 정렬 알고리즘의 하나(입력 배열 이외에 추가 메모리를 요구하지 않음) 1) 장점 구현이 쉽다 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 2) 단점 안정 정렬이 아니다(값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.) 정렬 규칙이 다수이거나 특정 순서를 유지해야 할 때 문제가 될 수 있다. 시간복잡도 상 효율이 좋지 않음 3) 단점 보완 방법 이중 선택 정렬 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다. 탐색을 응용하여 개선 한 번의 탐..