PSD( Private-Self-Development )

힙 정렬 알고리즘? 최대 힙 이나 최소 힙을 구성해 정렬하는 방법 내림차순은 최대 힙, 오름차순은 최소 힙 힙? https://chjysm.tistory.com/33 힙(heap) 힙 이란? 완전 이진트리의 일종이며, 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐? 우선순위 개념을 큐에 적용한 자료 구조이다. 가장 우선순위가 높은 데이터가 먼저 나간다. 배열, chjysm.tistory.com 정렬 절차 정렬해야 할 n개의 요소들로 힙 을 만든다. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열에 저장한다. 특징 장점 성능이 좋은편이다. 전체 자료를 정렬하는 기능 보다는 가장 큰 값과 작은 값이 필요한 경우이다. 구현 public static void heapSort( int[] targ..

퀵 정렬 알고리즘? 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 분할 정복 알고리즘 병합 정렬( Merge sort )과는 다르게 리스트를 비 균등하게 분할한다. 정렬 절차 분할(Divide): 입력 배열을 피벗을 기준으로 비 균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다. 정복(Conquer): 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 병합한다. 기준값인 피벗(pivot) 과 high, low 인덱스로 비교 및 교환 진행한다. 루틴이 한번 돌때마다 피벗은 제 위치를 찾아나간다. 특징 장점 속도가..

병합 정렬 알고리즘? 안정 정렬 이자 분할 정복 알고리즘이다. 작은 단위로 리스트를 나누어 이를 정렬 및 병합하여 결국 정렬된 결과를 가지게 된다. 정렬 절차 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀를 이용하여 다시 분할 정복 방법을 적용한다. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다. 추가적인 리스트가 필요하다. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다. 특징 장점 안정적인 정렬 방법 데이터의 분포에 영향을 덜 받는다. 즉,..

쉘 정렬 알고리즘? 삽입 정렬을 보완한 알고리즘 정렬 절차 먼저 정렬해야 할 리스트를 일정한 기준( ex. 일정 간격 마다 자른다 )에 따라 분류 연속적이지 않은 여러 개의 부분 리스트를 생성 각 부분 리스트를 삽입 정렬을 이용하여 정렬 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복 특징 장점 삽입 정렬 보다 성능이 좋다. 삽입 정렬의 단점인 레코딩 이동이 많은 점을 보완 알고리즘이 간단하여 쉽게 구현 가능하다. 구현 public static void shellSort( int[] target ){ shellSort( target, getGap( target.length ) ); } publ..

삽입 정렬 알고리즘? 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘. 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 특징 장점 레코드 수가 적거나 대부분의 레코드가 이미 정렬되어 있다면 매우 효율적이다. 단점 레코드 이동이 많을 수 있다..

선택 정렬 알고리즘? 각 자리마다 알맞은 수를 선택하여 교체함으로써 정렬하는 알고리즘 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 와 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다. 특징 장점 자료 이동 횟수가 미리 결정된다. 단점 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. 구현 public static void selectionSort( ..

버블 정렬 알고리즘? 서로 인접한 두 원소를 비교하여 오름차순 혹은 내림 차선으로 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 특징 장점 구현이 단순하다. 단점 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 다른 모든 요소들과 교환되어야 한다. 즉 성능이 좋지않다. 때문에 거의 쓰이지 않는다. 구현 public static void bubbleSort( int[] target ){ for( int i = target.length - 1; i > 0; i -- ){..