기수정렬 (Radix Sort)이때까지의 정렬 방법들은 모두 레코드들을 비교하여 정렬했습니다. 따라서 비교가 불가능한 레코드는 정렬할 수 없었습니다.기수정렬은 레코드를 비교하지 않고도 정렬하는 방법입니다.- 입력 데이터에 대해 어떠한 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 기법 기수란 숫자의 자리수입니다.- 예를 들면 숫자 42는 4와 2의 두개의 자리수를 가지고 이것이 기수가 됩니다.기수정렬은 이러한 자리수의 값에 따라 정렬을 하기 때문에 기수정렬이라는 이름을 얻었습니다. {8, 2, 3, 7, 5}를 정렬하기 위해 10진수라는 점을 착안하여 10개의 버킷을 만들고 입력 데이터를 각 자리수의 값에 따라 상자에 넣습니다.그리고 각 왼쪽 상자부터 순차적으로 버킷 안에 들어있는 숫자를 읽습니다...

힙 정렬 (Heap Sort)최대/최소 힙을 이용한 정렬 방법으로 내림차순 정렬을 하려면 최대 힙을, 오름차순 정렬을 하려면 최소 힙을 이용한 정렬입니다.그렇다면 힙(Heap)은 무엇일까요? 힙의 개념힙(Heap)을 영어사전에서 찾아보면 "더미"라고 되어 있습니다.컴퓨터 분야에서의 힙은 완전이진트리 기반의 "더미"와 모습이 비슷한 자료구조를 말합니다.힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 입니다.- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말합니다.- Key(A) >= Key(B) - 힙은 중복된 값을 허용합니다. 최대 힙 : Key(부모노드) >= Key(자식노드)최소 힙 : Key(부모노드)

퀵 정렬 (Quick Sort)퀵 정렬, 말 그대로 빠른 정렬입니다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 퀵 정렬도 합병 정렬처럼 분할-정복(Divide & Conquer) 방식을 사용합니다.하지만, 합병정렬과는 다르게 퀵 정렬은 리스트를 비균등하게 분할합니다. 1. 리스트 안에 한 요소를 피벗으로 선택한다. 대체로 첫 번째 요소를 피벗으로 선정합니다.2. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로, 큰 요소들은 오른쪽으로 옮깁니다.3. 피벗을 제외한 왼쪽과 오른쪽의 리스트들을 대상으로 1~2의 과정을 반복해 정렬을 완료합니다. 위 그림의 마지막 상태는 피벗 5를 기준으로 왼쪽 리스트는 피벗보다 작은 데이터, 오른쪽 리스트는 피벗보다 큰 데이터들로 구성되어 리스트가 분할된 것을 보..

합병정렬(Merge Sort)합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다.이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다.- 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다. 1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다.3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다. 합병정렬의 특징삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 실행속도가 ..

쉘 정렬(Shell Sort)쉘 정렬은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법입니다.쉘 정렬의 속도는 삽입정렬의 O(n^2)보다 빠릅니다. 쉘 정렬의 속도는 약 O(n^1.5) : 몇개로 그룹들을 나누느냐에 따라 실행속도가 달라집니다. 삽입정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것입니다.만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 이미 정렬된 요소들이 많은 이동을 해야만이 제자리로 삽입될 수 있습니다.- 정렬 위치 이후의 모든 요소들이 한 칸씩 옆으로 이동해야 정렬이 됨쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있습니다. 1. 정렬해야 할 리스트들을..

버블정렬 (Bubble Sort)버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행합니다. 이렇게 되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 되는데 이 과정을 스캔이라고 합니다. 이 스캔 과정을 반복하며 숫자가 정렬될 때까지 반복 수행합니다.레코드의 이동 과정이 마치 물 속에서 거품이 보글보글 떠오르는 것과 유사하다고 하여 버블정렬이라고 부릅니다. 1. 인접한 2개의 레코드 비교, 작은 숫자를 앞으로 교환2. 가장 큰 수가 오른쪽 끝으로 가게 됨3. 1의 과정을 다시 진행하여 모든 숫자가 정렬될 때 까지 반복 스캔 과정 버블정렬의 특징버블정렬은 안정성이 있고, 비효율적인 정렬입니다. 알고..