병합 정렬(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..

삽입 정렬(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..

기수 정렬(Radix Sort) 알고리즘

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

기수 정렬(Radix Sort) 알고리즘이란? 데이터의 모양에 따른 제한이 있는 버킷 정렬의 문제를 개선하여 만들어짐. (ex) 데이터가 '1, 1000'이라면 1000개의 공간 필요. 각 자릿수별로 버킷 정렬을 반복 수행하는 방법. 간단하고, 버킷 정렬보다 시스템 리소스 낭비가 적으며 빠르다. 기수 정렬 방법 1. 정렬할 데이터를 확보한다. 2. 각 자릿수는 0~9의 값을 가지므로 10개의 데이터 공간을 확보한다. 3. 각 데이터의 1의 자릿수를 기준으로 버킷 정렬 4. 각 데이터의 10의 자릿수를 기준으로 버킷 정렬 5. 각 데이터의 100의 자릿수를 기준으로 버킷 정렬 ... 반복 lktprogrammer.tistory.com/48 06 정렬 알고리즘 - 기수 정렬(Radix Sort) 기수정렬 (..

버킷 정렬(Bucket Sort) 알고리즘

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

버킷 정렬 알고리즘이란? 자료를 버킷이라는 단위 기억 장소에 정렬하고, 버킷별 키 값에 따라 다시 정렬하는 알고리즘. 사용방법 1. 정렬할 데이터를 확보한다. 2. 정렬할 데이터 숫자 이상의 공간을 확보하고, 숫자를 해당하는 공간에 차례대로 할당한다. 3. 데이터를 각자의 위치에 넣는다. 4. 배열을 처음부터 읽어서 값이 있으면 출력한다.