병합 정렬(Merge Sort)

알고리즘/정렬 알고리즘 2020.11.23

병합 정렬이란? 배열의 요솟수가 2개 이상인 경우, 배열을 반으로 나눠 앞부분을 병합 정렬하고 뒷부분을 병합 정렬한 후, 앞부분과 뒷부분을 병합하는 정렬 알고리즘. 여기서 병합이란 단순히 합치는 것이 아니라, 다음과 같이 이미 정렬된 두 배열의 요소 중 더 작은 요소를 선택해 목표 배열에 넣는 것이다. 이미 정렬된 두 배열 병합하기 static void mergeArray(int[] a, int[] b, int[] c) { //각 배열의 포인터를 모두 0으로 초기화 int pa, pb, pc; pa=pb=pc=0; //두 배열의 포인터가 모두 각 배열의 끝에 닿지 못했을 때 while(pa

셸 정렬 알고리즘

알고리즘/정렬 알고리즘 2020.11.22

단순 삽입 정렬의 장점(정렬을 마친 상태에 가까울 수록 정렬 속도가 매우 빨라짐)은 그대로 가져가고 단점(삽입할 위치가 멀리 떨어져 있으면 이동해야하는 횟수가 많아짐)을 보완한 알고리즘. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법. 자바로 구현하기 static void shellSort(int[] a, int n) { //각 부분 리스트의 요소가 1이 될 때까지, //즉 증분값 h가 1이 될 때까지 전체 반복 for(int h=n/2; h>0; h/=2) { //부분 리스트들끼리 나눠서 반복할 수도 있지만 여기서는 //전체 요소들을 반복하면서 각 부분 리스트에 맞게 비교 되도록 구현하겠다. for(int..

버블 정렬(Bubble Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

버블 정렬(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 =..

힙 정렬(Heap Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

힙 정렬(Heap Sort) 알고리즘이란? 힙의 개념을 이용하여 정렬하는 알고리즘. 사용 방법 1. 주어진 데이터를 힙으로 구성한다. 큰 수에서 작은 수로 정렬하려면 최상위 데이터를 가장 큰 수로 설정한다. 2. 최상위 데이터를 빼고(배열에 넣고) 나머지 데이터로 다시 힙을 구성한다. 가장 큰 수를 계속 최상위 데이터로 설정한다. 3. 위 작업을 반복한다. lktprogrammer.tistory.com/70 07 정렬 알고리즘 - 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다. ■ 정렬 과정 ▶ 이번 lkt..

퀵 정렬(Quick Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

퀵 정렬(Quick Sort) 알고리즘이란? 중앙 값 정렬 방식을 확장해서 개발한 방식. 먼저 배열을 둘로 나눠 두 그룹을 만들고, 그 기준을 피벗(pivot)이라고 한다. 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마친다. 가장 빠른 정렬 알고리즘 중의 하나. 사용 방법 1. 임의로 선정된 데이터를 중심으로 데이터를 2등분한다. 2. 각 분리된 부분의 첫 번째 원소를 기준으로 데이터를 분리한다. 3. 이 작업을 계속 반복한다. 자바로 구현하기 static void quickSort(int[] a, int left, int right) { //왼쪽 포인터를 왼쪽 끝에, 오른쪽 포인터를 오른쪽 끝에 두고 피벗을 설정한다. int pl = left; int pr = r..

병합 정렬(Merge Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

병합 정렬(Merge Sort) 알고리즘이란? 데이터를 분할한 다음 각자 계산하고 나중에 합쳐서 정렬하는 알고리즘 사용 방법 1. 정렬할 데이터를 최소 단위(1개)가 될 때까지 분할 작업을 반복한다. 2. 분할된 데이터를 대상으로 2개, 4개, 8개씩, ... 병합하면서 정렬을 수행한다. lktprogrammer.tistory.com/41 05 정렬 알고리즘 - 병합 정렬 (Merge Sort) 병합 정렬 (Merge Sort) 전체 원소를 하나의 단위로 분할한 후에 분할한 원소를 다시 병합하며 정렬해 나가는 방식입니다. ■ 정렬 방식 1. 정렬하고자 하는 데이터 집합을 반으로 나눈다. 2. 반으로 lktprogrammer.tistory.com

셀 정렬(Shell Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

셀 정렬(Shell Sort) 알고리즘이란? 삽입 정렬 알고리즘의 느린 속도를 보완하기 위해 만들어진 알고리즘. 데이터의 그룹을 나누어, 그룹 안에서 쉘 정렬을 수행하고 마지막에 삽입 정렬을 수행하는 알고리즘. 사용 방법 (오름차순 정렬이라고 가정) 1. 정렬할 데이터를 2개의 무리로 분할하고, 각 무리의 처음 값을 비교하여 작은 것이 앞으로 가도록 한다. 두 번째, 세 번째, ..., 마지막 수까지 비교한다. 2. 수정된 데이터를 대상으로 다시 3개의 무리로 분할하고 똑같은 작업을 수행한다. 3. 한 무리가 1개의 데이터로 구성될 때까지 진행한다. 그리고 인접한 무리와 수를 비교한다. 4. 전체 데이터를 대상으로 삽입 정렬을 수행한다.

삽입 정렬(Insert Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

삽입 정렬(Insert Sort) 알고리즘이란? 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘. 선택 정렬 알고리즘과도 비슷하지만, 선택 정렬은 값이 가장 작은 요소를 선택한다는 것이 다르다. 사용 방법 1. 정렬할 데이터를 확보 2. 처음엔 앞에서부터 데이터를 비교하여, 교환한다. 3. 위치가 바뀐 데이터가 있다면 그 데이터를 앞의 데이터와 또 비교한다. 4. 과정 반복. 앞의 데이터와 비교하여 교환하는 것이 교환 정렬 알고리즘과 비슷하지만, 교환 정렬은 비교할 데이터가 고정인 반면 삽입 정렬은 위치 교환이 발생한 데이터를 주변의 데이터와 비교하여 위치를 교환한다. 자바로 구현하기

교환 정렬(Exchange Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

교환 정렬(Exchange Sort) 알고리즘이란? 작은 것부터 큰 순서로 정렬할 경우, 작은 키를 갖는 데이터를 찾아 앞 데이터와 교환하는 알고리즘. 사용 방법 1. 정렬할 데이터를 대상으로 앞에서부터 인접한 두 개의 크기를 비교하여 작은 것이 앞으로 가도록 교환한다. 2. 나머지 데이터도 계속 비교하면서 작은 것이 앞으로 가도록 위치를 교환한다. 3. 끝까지 수행한 후에 다시 처음부터 동일한 작업을 반복한다.

선택 정렬(Selection Sort) 알고리즘

알고리즘/정렬 알고리즘 2020.11.16

선택 정렬(Selection Sort) 알고리즘이란? 가장 작은 데이터를 찾아 가장 앞 데이터와 교환하는 알고리즘 사용 방법 1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다. 2. 가장 작은 값과, 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 자바에서 구현하기 package sort; import java.util.Random; public class selectionSort { //두 인접한 요소의 값을 교환한다. static void swap(int[] a, int idx1, int idx2) { int tmp = a[idx1]; a[idx1] = a[idx2]; a[idx2] = tmp; } //(단순) 선택 정렬 static void selectionSort(int[] a..