Developer Cafe

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방식..

컴퓨터 정렬에서 실제로 가장 많이 쓰이는게 바로 내장 정렬 함수 퀵 정렬이다. 퀵 정렬은 매우 빠른 알고리즘으로 특히 평균 시나리오 에서 효율적이다. 분할 분할은 배열로부터 임의의 수를 가져와(이 수를 피벗이라 부름) 피벗보다 작은 모든 수는 왼쪽, 큰 수는 오른쪽에 둔다. 1 4 2 3 임의의 수 를 선택(2선택 피벗지정) 후 왼쪽 포인터(1)과 오른쪽 포인터(3)을 고른다. 1. 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 2. 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 4. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽..