본문 바로가기

정렬
10

병합 정렬(Merge Sort) 병합 정렬이란? 배열의 요솟수가 2개 이상인 경우, 배열을 반으로 나눠 앞부분을 병합 정렬하고 뒷부분을 병합 정렬한 후, 앞부분과 뒷부분을 병합하는 정렬 알고리즘. 여기서 병합이란 단순히 합치는 것이 아니라, 다음과 같이 이미 정렬된 두 배열의 요소 중 더 작은 요소를 선택해 목표 배열에 넣는 것이다. 이미 정렬된 두 배열 병합하기 static void mergeArray(int[] a, int[] b, int[] c) { //각 배열의 포인터를 모두 0으로 초기화 int pa, pb, pc; pa=pb=pc=0; //두 배열의 포인터가 모두 각 배열의 끝에 닿지 못했을 때 while(pa 2020. 11. 23.
셸 정렬 알고리즘 단순 삽입 정렬의 장점(정렬을 마친 상태에 가까울 수록 정렬 속도가 매우 빨라짐)은 그대로 가져가고 단점(삽입할 위치가 멀리 떨어져 있으면 이동해야하는 횟수가 많아짐)을 보완한 알고리즘. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법. 자바로 구현하기 static void shellSort(int[] a, int n) { //각 부분 리스트의 요소가 1이 될 때까지, //즉 증분값 h가 1이 될 때까지 전체 반복 for(int h=n/2; h>0; h/=2) { //부분 리스트들끼리 나눠서 반복할 수도 있지만 여기서는 //전체 요소들을 반복하면서 각 부분 리스트에 맞게 비교 되도록 구현하겠다. for(int.. 2020. 11. 22.
버블 정렬(Bubble Sort) 알고리즘 버블 정렬(Bubble Sort) 알고리즘이란? 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘. //두 인접한 요소의 값을 교환한다. static void swap(int[] a, int idx1, int idx2) { int tmp = a[idx1]; a[idx1] = a[idx2]; a[idx2] = tmp; } //버블 정렬을 실행한다. static void bubbleSort(int[] a) { int n = a.length; int k = 0; while(k k; j--) { if(a[j-1] > a[j]) { swap(a, j-1, j); last = j; } } k =.. 2020. 11. 16.
힙 정렬(Heap Sort) 알고리즘 힙 정렬(Heap Sort) 알고리즘이란? 힙의 개념을 이용하여 정렬하는 알고리즘. 사용 방법 1. 주어진 데이터를 힙으로 구성한다. 큰 수에서 작은 수로 정렬하려면 최상위 데이터를 가장 큰 수로 설정한다. 2. 최상위 데이터를 빼고(배열에 넣고) 나머지 데이터로 다시 힙을 구성한다. 가장 큰 수를 계속 최상위 데이터로 설정한다. 3. 위 작업을 반복한다. lktprogrammer.tistory.com/70 07 정렬 알고리즘 - 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다. ■ 정렬 과정 ▶ 이번 lkt.. 2020. 11. 16.

최근댓글

최근글

skin by © 2024 ttuttak

티스토리툴바