데이터 구조-정렬 기법

정렬은 특정 형식으로 데이터를 정렬하는 것을 말합니다. 정렬 알고리즘은 특정 순서로 데이터를 정렬하는 방법을 지정합니다. 가장 일반적인 순서는 숫자 또는 사전 순서입니다.

정렬의 중요성은 데이터를 정렬 된 방식으로 저장하면 데이터 검색을 매우 높은 수준으로 최적화 할 수 있다는 사실에 있습니다. 정렬은 또한 더 읽기 쉬운 형식으로 데이터를 나타내는 데 사용됩니다. 다음은 실제 시나리오에서 정렬하는 몇 가지 예입니다.

• Telephone Directory − 전화 번호부에는 이름별로 정렬 된 사람의 전화 번호가 저장되어있어 이름을 쉽게 검색 할 수 있습니다.

• Dictionary − 사전은 단어를 알파벳 순서로 저장하므로 모든 단어를 쉽게 검색 할 수 있습니다.

내부 정렬 및 내부 정렬

정렬 알고리즘에는 비교를 위해 약간의 추가 공간이 필요할 수 있으며 소수의 데이터 요소를 임시로 저장할 수 있습니다. 이러한 알고리즘에는 추가 공간이 필요하지 않으며 정렬은 내부 또는 예를 들어 배열 자체 내에서 발생한다고합니다. 이것은 ... 불리운다in-place sorting. 버블 정렬은 내부 정렬의 한 예입니다.

그러나 일부 정렬 알고리즘에서 프로그램에는 정렬되는 요소보다 크거나 같은 공간이 필요합니다. 동일하거나 더 많은 공간을 사용하는 정렬을 호출합니다.not-in-place sorting. Merge-sort는 not-in-place 정렬의 예입니다.

안정적이고 불안정한 정렬

내용을 정렬 한 후 정렬 알고리즘이 내용이 나타나는 유사한 내용의 순서를 변경하지 않으면이를 호출합니다. stable sorting.

정렬 알고리즘이 내용을 정렬 한 후 나타나는 유사한 내용의 순서를 변경하면 unstable sorting.

예를 들어 튜플에서와 같이 원래 요소의 시퀀스를 유지하려는 경우 알고리즘의 안정성이 중요합니다.

적응 형 및 비 적응 형 정렬 알고리즘

정렬 알고리즘은 정렬 할 목록에서 이미 '정렬 된'요소를 활용하는 경우 적응 적이라고합니다. 즉, 소스 목록에 이미 정렬 된 요소가있는 경우 정렬하는 동안 적응 형 알고리즘은이를 고려하여 다시 정렬하지 않습니다.

비 적응 알고리즘은 이미 정렬 된 요소를 고려하지 않는 알고리즘입니다. 그들은 정렬을 확인하기 위해 모든 단일 요소를 다시 정렬하도록 강제합니다.

중요한 용어

일부 용어는 일반적으로 정렬 기술을 논의하는 동안 만들어집니다. 여기에 간단한 소개가 있습니다.

주문 증가

일련의 값은 increasing order, 연속 요소가 이전 요소보다 큰 경우. 예를 들어, 1, 3, 4, 6, 8, 9는 모든 다음 요소가 이전 요소보다 크므로 오름차순입니다.

주문 감소

일련의 값은 decreasing order, 연속 요소가 현재 요소보다 작은 경우. 예를 들어, 9, 8, 6, 4, 3, 1은 모든 다음 요소가 이전 요소보다 작기 때문에 내림차순입니다.

비 증가 주문

일련의 값은 non-increasing order, 연속 요소가 시퀀스의 이전 요소보다 작거나 같은 경우. 이 순서는 시퀀스에 중복 값이있을 때 발생합니다. 예를 들어, 9, 8, 6, 3, 3, 1은 모든 다음 요소가 이전 요소보다 작거나 같지만 (3의 경우) 크지 않으므로 증가하지 않는 순서입니다.

비 감소 주문

일련의 값은 non-decreasing order, 연속 요소가 시퀀스의 이전 요소보다 크거나 같은 경우. 이 순서는 시퀀스에 중복 값이있을 때 발생합니다. 예를 들어, 1, 3, 3, 6, 8, 9는 모든 다음 요소가 이전 요소보다 크거나 같지만 (3의 경우) 작지 않기 때문에 감소하지 않는 순서입니다.