Deok9의 I.T Blog

매번 보는 지겨운 정렬 알고리즘 실제 개발에 있어서 라이브러리를 잘 사용하여 짜기만 하면되는데.... 라는 생각을 떠나 언젠가 자기만의 커스텀 정렬을 위하여 이번 기회에 정리 합니다.목표 1, 정렬 알고리즘 종류와 방법을 이해 2. 정렬 알고리즘의 복잡도 이해 3. 고급정렬 알고리즘 용어 1. 레코드(record) : 정렬할 각 원소 2. 필드(field) : 레코드에 포함되어 있는 정보 3. 키 : 레코드간의 순서를 나타내는 자 4. 안전성(stability) : 상대적인 위치가 정렬후에도 유지가 될 것 비교에 의한 정렬 1. 선택정렬 O(N^2) 불안정 2. 버블정렬 O(N^2) 안정적 3. 삽입정렬 O(N^2) 안정적 4. 쉘정렬 O(N^3/2) 안정적 5. 히프정렬 O(NlogN) 불안정적 분포에..

정렬을 배우면 처음으로 접하는 정렬 방법이 바로 이 버블 정렬입니다 알고리즘, 자료구조 책을 참고해보면 일일이 하나씩 비교해서 정렬을 한다 라고 설명이 되어있는데 다른 정렬을 보다보면 조금 다른 방향으로 해석이 가능해집니다 루프가 두번 들어 가는 형태로 비교대상이 하나씩 줄어들며 계속해서 처음부터 비교해 나갑니다 아래 그림을 보겠습니다 이 예제는 5개의 배열이므로 첫번째 루프를 i, 두번쨰 루프를 j라고 하겠습니다 1. i=0, j=0 2. i=0, j=1 3. i=0, j=2 4. i=0, j=3 여기서 오른쪽 맨끝이 확정된 정렬이 되어집니다 5. i=1, j=0 6. i=1, j=1 7. i=1, j=2 여기서 오른쪽 두번쨰 끝이 확정된 정렬이 되어집니다 8. i=2, j=0 9. i=2, j=1 여..

합병정렬에 대해서 알아보자분할정복?!을 적용한 정렬이다.(분할정복 : 2개의 부분문제로 계속 나아가며 크기가 1/2씩 계속 감소하는 알고리즘) 그림으로 표현 하자(내림차순 정렬) 첫번째로 최소단위 까지 분할하여 내려간다. 두번째로 비교를 통하여 정렬한후 합병한다, 시간복잡도에 대하여 얘기해보자1. 분할하는 과정에서는 비교 형태가 아니며 중간(mid)값을 계산과 재귀호출 을 요구하므로 O(1)2. 합병하는 과정에서는 양쪽을 비교하는데 왼쪽의 크기를 m 오른쪽의 크기를 n 이라고 가정을하면 최대비교 횟수는 O(m+n-1)이된다. O(m+n-1) = > O(m+n) m 과 n은 입력값에 비례하므로 O(n)이 되게되는데 즉. 층당 O(n)이 적용되는데 이 층은 분할되어 1/2 가 작용되므로 log2n 이 되어진..