삽입 정렬의 단점을 보완한 정렬 방식. 삽입 정렬의 단점??? 삽입 정렬은 한칸씩 이동하면서 비교하기 때문에 만일 가장 멀리 떨어진 곳에서 비교가 이루어진다면 이동 시 많은 오버헤드가 발생할 수 있다. 그 단점을 보완하기 위해 만들어진 방식!! 그림과 함께 살펴보도록 하자 1. 주어진 배열에 대해 반으로 쪼갠 후, 쪼갠 블록을 각 쌍으로 삽입 정렬을 시행한다. 예를 들면 {3,2}, {8,1}, {0,4} 가 쌍으로 삽입 정렬이 실행되고 결과는 {2,3}, {1,8}, {0,4} 로 나타날 것이다. 2. 삽입 정렬이 완료된 블록에 대해 다시 반으로 쪼갠 후, 쪼갠 블록의 각 index를 다시 삽입 정렬로 정렬한다. {2,1,3,8}, {0,4} => {1,2,3,8}, {0,4} 3. 결과에 대해 다시 ..

가장 작은 범위를 만든 후 해당 범위에서 가장 작은 수를 왼쪽으로 이동시키고, 점점 범위를 넓혀가며 범위 내에서 작은 수를 점차적으로 왼쪽으로 이동시키는 방법. 말로 설명하기엔 역시나 어려움이 따른다. -_- 하지만 직접 그림을 보거나 코드를 보면 금방 이해가 갈 것이다. 1. 처음에는 가장 최소 단위인 2개의 블록만 범위로 잡는다. 기존의 3이란 값에 8을 비교해야 하는 상황이다. 3과 8을 비교하면 8이 더 크기 때문에 따로 swap이 일어나지 않는다. 2. 범위를 3개로 넓힌다. 0이란 값이 새로 첨가된 상황이다. 0과 8을 비교한다. 0이 더 작기 때문에 0 위치에 8을 집어넣는다. 3. 0을 3과 비교한다. 0이 더 작으므로 0 위치에 3을 집어 넣는다. 범위 마지막 위치이기 때문에 현재 위치에..

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식. 1. 분할 아래 그림과 같이 배열 집합을 하나의 원소 단위로 각각을 분할한다. 2. 병합 분할된 각각의 원소에 대해 서로의 쌍을 비교하여 sorting 후 병합한다. 3. Sorting 과정. 병합시의 Sorting 과정을 살펴보면 우선 병합하려고 하는 크기의 메모리를 할당한 다음, 두 개의 원소에 대해 각각을 비교하여 할당된 메모리에 집어넣는다. 그림을 보며 설명하는게 더 나을지도.. 1. 0,3,8 과 1,2,4에 대한 병합 작업이 이루어지고 있다. 두 배열을 합치면 총 6의 공간이 필요하기 때문에 6의 메모리 배열을 새롭게 만들어 두고 작업을 진행한다. 각 배열의 제일 왼쪽 원소부터 서로 비교한다. 두 개의 원소 중 작은..

Sorting 알고리즘 중 가장 효율적이고 빠른 방식. 이름 자체에서도 퀵이란 명칭이 붙을 정도로 가장 많이 사용되고 가장 잘 사용되는 방식이다. 1. 먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정한다. 2. PIVOT 값과 LEFT 값을 비교한다. 만약 LEFT 값이 PIVOT 값보다 크다면 PIVOT 값과 RIGHT 값을 비교한다. RIGHT 값이 PIVOT 값보다 크다면, RIGHT 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT 값과 비교한다. 3. RIGHT 값이 PIVOT 값보다 작다면, LEFT 값과..

물 속에서 거품이 올라오는 모습과 비슷하게 정렬한다고 해서 붙여진 이름.왼쪽 끝에서부터 인접하는 두 개의 값을 비교하여 교환하는 방식으로 오른쪽 끝까지 가는 방식.구현은 쉽지만 상당히 비효율적인 정렬 방식으로 꼽히고 있다.원본 리스트 3 8 0 1 4 [STEP 1] 3 8 0 1 4 - 3과 8을 비교. 8이 더 크므로 변화가 없어도 된다. 3 8 0 1 4 - 그 다음 8과 0을 비교. 0이 더 작으므로 8과 0을 교환한다. 3 0 8 1 4 - 8과 1을 비교. 1이 더 작으므로 8과 1을 교환한다. 3 0 1 8 4 - 8과 4를 비교. 4가 더 작으므로 8과 4를 교환한다. 3 0 1 4 8 - 이로써 한 스텝이 끝났다. 다시 처음부터 비교를 한다.[STEP 2] 3 0 1 4 8 - 3과 0을..