레퍼런스 마이닝

셸 정렬 기본 개념 "Donal L. Shell"이라는 사람이 제안한 방법으로, 삽입 정렬을 보안한 알고리즘이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠르다는 것을 착안하였다. 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 셸 정렬 구체적인 개념 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 k를 "간격(gap)"이라고 한다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다. 간격의 초기값 : 정렬할 리스트 사이즈 / 2 분할된 리스트의 개수는 gap과 같다. 간격은 홀수로 하는 것이 좋다. 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수를 만든다. 간격 ..

선택 정렬 기본 개념 제자리 정렬(in-place sorting) 알고리즘의 하나로, 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 선택 정렬 구체적인 개념 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세번째 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회차에서는 두 번째 자료를 가지고 비교한다. 선택 정렬 알고리즘 예제 import java...

삽입 정렬 기본 개념 손 안의 카드를 정렬하는 방법과 유사하다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분의 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬 구체적인 개념 삽입 정렬은 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 2|1, 3|2, 4|3 번째 자료와 비교한 후 삽입할 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key 자료는 두 번째 자료부터 시작한다. 삽입 정렬 알고리즘 예제 import java.util.Ar..

버블 정렬 기본 개념 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘(인접한 2개의 레코드를 비교하여 크기를 순서에 맞게 서로 교환한다.) 선택 정렬과 기본 개념이 유사하다. 버블 정렬 구체적인 개념 버블 정렬은 1|2, 2|3, 3|4 ... 이런 식으로 마지막(마지막 -1) 번째 자료까지 비교하여 교환한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 2번째 자료는 정렬에서 제외된다. 이런 식으로 정렬을 1회전 수행할 때마다 정렬에서 제외되는 자료가 하나씩 늘어난다. 버블 정렬 알고리즘 예제 import java.util.Arrays; public class BubbleSort { public stat..