힙 정렬 (Heap Sort) ▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다. ■ 정렬 과정 ▶ 이번 게시글에서는 최대힙을 기준으로 설명을 하겠습니다. 힙의 기본은 완전 이진 트리의 형태이면서 부모 노드가 자식 노드보다 큰 값을 가지는 힙 성질을 만족하는 트리를 의미합니다. 따라서 최상위 노드인 루트 노드는 전체 원소 중에서 항상 최대값을 가지게 됩니다. 1. 배열에 저장 된 원소들을 최대힙으로 구성 2. 루트 노드에 존재하는 값을 가지고 오고, 가장 말단에 있는 노드를 루트 노드에 위치 시킵니다. 새로 자리 잡은 루트 노드에 대하여 다시 힙 성질에 맞게끔 배열을 조..

기수정렬 (Radix Sort) 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저..

병합 정렬 (Merge Sort) 전체 원소를 하나의 단위로 분할한 후에 분할한 원소를 다시 병합하며 정렬해 나가는 방식입니다. ■ 정렬 방식 1. 정렬하고자 하는 데이터 집합을 반으로 나눈다. 2. 반으로 나누어진 하위 데이터의 개수가 2이상이면 1의 과정을 반복한다. 3. 같은 집합에서 나온 하위 데이터 둘을 정렬을 시도하면서 다시 병합합니다. 4. 원래의 데이터 집합이 될때까지 3의 과정을 반복합니다. - 분할과정 전체 데이터 크기(n=8)에서 반으로(n=4) 나눕니다. 이 과정에 대해서 데이터 집합의 크기가 1이 될 때까지 반복합니다. -병합과정 같은 집합에서 나온 하위 데이터집합 두개를 정렬과 동시에 병합을 시도합니다. 주목해야 할 점은 병합이 이루어진 데이터 집합에 대해서는 정렬이 이루어졌습니..

퀵 정렬 (Quick Sort) 기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같은 값을 지닌 자료는 앞으로 큰 값을 진ㄴ 자료는 뒤로 가도록 하여 기준 원소를 중심으로 분할해가며 정렬을 진행하는 방식입니다. ■ 정렬방식 1. 기준이 되는 원소를 정합니다. 배열의 시작 원소를 pivot으로 설정합니다. 2. 좌우 인덱스를 지정합니다. 해당 인덱스는 다음을 의미합니다. - left : pivot 보다 큰 값을 찾으러 다니는 index - right : pivot 보다 작은 값을 찾으러 다니는 index - left_hold : pivot을 제외하고 정렬 대상의 시작점 - right_hold : pivot을 제외하고 정렬 대상의 끝점 3. left를 pivot보다 큰 값을 찾을 때 까지 이동합니다...

버블정렬 (Bubble Sort) 두 인접한 배열요소를 차례대로 검사를 하여 정렬을 하는 방식 ■ 정렬 방식 1. 배열의 가장 앞에서 인접한 두 개의 요소에 대하여 비교를 한다. (배열의 첫 번째 요소와 두 번째 요소) 2. 배열의 다음 인접한 요소(두 번째와 세번째를 비교를 한다.) 3. 배열의 끝까지 반복을 한다. 한 사이클이 끝나면 배열의 맨 끝에는 정렬된 요소 하나가 정렬이 된 채 자리잡는다. 4. 정렬이 된 마지막 요소를 제외한 나머지에 대하여 1,2,3 번 과정을 반복한다. 정렬이 된 상태 비교 원소 5 4 3 2 1 최초 정렬이 이루어지지 않은 상태의 배열입니다. 5 4 3 2 1 첫 번째 요소와 두 번째 요소를 비교합니다. 4가 더 작으므로 둘의 위치를 교환합니다. 4 5 3 2 1 다음 ..

삽입 정렬 (Insetion Sort) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다. ■ 정렬 방식 1. 배열의 첫 번째 요소는 정렬 된 상태라고 가정한다. 2. 배열의 두 번째 요소부터 앞에 정렬된 배열을 차례대로 비교하며 교환한다. 3. 최종적으로 자신의 위치에 맞는 위치에 삽입된다. 4. 다음 배열 요소에 대해서 같은 작업을 반복한다. : 정렬이 완료 된 상태 : 비교되는 배열 요소들 5 4 3 2 1 첫 번째 배열요소는 정렬이 완료된 상태라고 가정을 합니다. 5 4 3 2 1 두 번째 요소부터 비교를 시작합니다. 앞에 정렬된 첫 번째 요소와 비교를 하고 4가 더 작으므로 둘의 위치를 바꿔줍니다. 4..

선택 정렬(Selection Sort) 기존 위치에 맞는 원소를 선택하여 교환하는 방식 ■ 정렬 방식 1. 아직 정렬이 안된 리스트 중에 가장 앞에 원소를 최소값으로 설정 2. 가장 앞에 원소를 제외한 나머지 원소를 차례로 비교하고 최소값을 찾아감 3. 리스트 끝까지 비교 후 찾은 최소값을 가장 앞에 원소와 교환 4. 정렬이 안된 원소들을 가지고 반복 ■ 특징 - 최소값을 찾기 위한 비교횟수는 많지만 교환 횟수는 적다. - 데이터의 개수가 적을 때 좋은 성능을 발휘한다. - 시간복잡도 : O(n＾2) ■ 소스코드 (Source Code) public int[] Selection_Sort(int[] data,int num) { int min,tmp; for(int i=0;i

collections 모듈을 이용해 dict 정렬하기 파이썬에서 자주 사용하는 Dictionary를 정렬하는 방법은 operator를 사용하는 방법도 있습니다. [바로가기] 이번에는 기본 모듈인 collections를 이용해서 dict 정렬하는 예제입니다. 소스코드 {2:3, 1:89, 4:5, 3:0} --> {1:89, 2:3, 3:0, 4:5} {2:3, 1:89, 4:5, 3:0}의 dict형태의 데이터를 저장하고, collections을 import 합니다. OrderedDict을 통해 정렬을 하는데, 이때 안에는 sorted(dict.items())를 넘겨주시면 됩니다. 아무래도 key와 value가 모두 정렬되니. 간편하게 사용이 가능 합니다. dict = {2:3, 1:89, 4:5, 3:..

Dictionary key기준, value기준으로 정렬하기 들어가며 파이썬을 사용하다 보면 자주 List만큼 자주 사용하는 객체가 있으니 그것이 바로 dictionary입니다. 그렇기 때문에 dict을 자유롭게 다룰 줄 알아야 합니다. 자 그렇다면 기본 중에 기본인 정렬하는 방법에 대해서 알아보겠습니다. 일단 dict의 형태에 대해서 간단하게 설명하면 key, value의 쌍으로 이루어져 있습니다. 예제를 통해 알아보겠습니다. 구현하기 operator를 통해 정렬을 할 수 있습니다. 두개의 차이는 operator.itemgetter()에서 1, 0을 넘기는 거에 따라 key로 정렬, value로 정렬을 할 수 있습니다. 1을 값을 기준으로 정렬을 할때 사용하고, 0은 키를 기준으로 정렬이 가능합니다. v..