이 방법은 카드 놀이를 할 때 널리 사용됩니다. 요소(지도)는 정신적으로 이미 "준비된" 시퀀스 A 1 , A 2 ,… , A i -1 과 "나머지"(정렬되지 않은) 부분 A i , A i +1 ,…

이 방법의 핵심은 각 i번째 단계(i = 2에서 시작)에서 i번째 요소가 정렬되지 않은 부분에서 추출되어 "완성된" 부분에 배치되는 동안 삽입된다는 것입니다. 올바른 장소.

텍스트 알고리즘 방법:

1. 시작합니다.

2. i가 2에서 N까지의 값을 갖는 동안 루프,
단계 = 1:

a) i 번째 요소(A(i))는 셀 A(0)에 배치됩니다.

b) j = -1을 할당합니다. 즉, j는 주제(i-th)의 왼쪽에 있는 요소의 수와 같으므로 "완성된" 시퀀스에 서 있습니다.

c) A(0) ≥ A(j)이면 요소 A(0)를 셀 A(j+1)에 배치하고, 그렇지 않으면 셀 A(j+1)에 요소 A(j)를 배치하고 값을 줄입니다. j를 1씩 반복하고 c) 단계를 반복합니다.

무화과에. 1은 정렬 방법의 블록도를 보여줍니다. 직접 연결.

이 방법은 다음과 같이 작동합니다. i 번째 단계(i = 2부터 시작)에서 i 번째 요소는 자유 셀(예: A(0))에 배치됩니다. 이 요소는 왼쪽의 "완성된" 부분에 있는 요소와 비교됩니다. 요소 A(0)이 작으면 비교 대상(j번째 요소)이 오른쪽으로 한 위치 이동한 후 비교를 위해 다음 요소가 사용됩니다. 요소 A(0)이 비교할 때보다 작지 않은 것으로 판명되면 비교된 요소 바로 뒤에 배치됩니다.

쌀. 1. 직접 포함 분류의 블록 다이어그램

무화과에. 도 2는 직접 포함에 의한 정렬의 예를 나타낸다.

소스 시퀀스
	A (0)
나는 = 2
나는 = 3
나는 = 4
나=5
나는 = 6
나는 = 7
나는 = 8
결과

쌀. 2. 직접 포함 정렬의 예

직접 포함 정렬은 정렬할 데이터가 순차적으로(하나씩) 도착하는 경우에 더 적합합니다.

직접 선택 정렬

방법의 본질은 다음과 같습니다. "나머지"(정렬되지 않은) 부분에서 가장 작은 요소가 선택되고 첫 번째 요소(동일한 정렬되지 않은 부분에서)와 교체됩니다. 그 후, 정렬되지 않은 부분의 길이는 하나의 요소(첫 번째 요소만큼)만큼 줄어들고 전체 프로세스는 (n - 1) 요소, 그런 다음 (n - 2) 요소 등으로 계속 진행되어 가장 큰 요소가 남을 때까지 요소.

이 방법은 어떤 의미에서 직접 포함 방법의 반대입니다. 직접 포함 방법에서는 각 단계에서 하나의 다음 요소와 시퀀스의 이미 "완료된" 부분의 모든 요소가 고려되며 그 중에서 이 다음 요소의 포함 지점이 발견됩니다. 그리고 직접 선택 방식에서는 하나의 (최소) 요소를 찾기 위해 정렬되지 않은 부분의 모든 요소를 ​​살펴보고 이 최소 요소를 이미 "준비된" 부분의 다음 요소로 배치합니다.

텍스트 알고리즘 방법:

1. 시작합니다.

2. i가 1에서 N - 1 사이의 값을 갖는 동안 루프,
단계 = 1:

a) 현재(i-th) 요소를 메모리 셀(X)에 넣고 기억하십시오. 일련 번호(i) 현재 요소(변수 K에서)

b) j가 i + 1(즉, i 다음 요소)에서 N까지의 값을 갖는 동안 루프, stride = +1:

루프 본문: X > A(j)인 경우 요소 A(j)를 셀 X에 배치하고 셀 K의 번호를 기억하십시오.

c) A(K) = A(i) 및 A(i) = X를 할당합니다.

무화과에. 도 3은 직접 선택에 의한 정렬의 예를 나타낸다.

쌀. 3. 직접 선택에 의한 정렬의 예

이 방법은 카드 놀이를 할 때 널리 사용됩니다. 요소(지도)는 정신적으로 이미 "준비된" 시퀀스 A1 ... An과 원래 시퀀스 Ai ... An으로 나뉩니다. 각 단계에서 i=2에서 시작하여 매번 I를 1씩 증가시키면 원래 시퀀스에서 추출됩니다. i번째 요소올바른 위치에 삽입된 상태에서 완성된 시퀀스로 이동합니다.

위의 예는 무작위로 선택된 8개의 숫자를 포함하여 정렬하는 과정을 보여줍니다. 이 정렬을 위한 알고리즘은 다음과 같습니다.

For i:=2 TO n DO

... a[j] 중 적절한 위치에 x 포함;

적절한 장소를 찾는 실제 과정에서는 X를 선별하는 것이 편리합니다. 즉, X가 다음 요소 aj와 비교되고 두 X 중 하나가 다음에 삽입됩니다. 자유 장소, 또는 aj는 오른쪽으로 이동(전송)되고 프로세스는 왼쪽으로 "떠납니다". 다음 두 가지 조건 중 하나가 충족되면 체질 프로세스가 종료될 수 있습니다.

1. X의 키보다 작은 키를 가진 요소 aj가 발견되었습니다.

2. 완료된 시퀀스의 왼쪽 끝에 도달했습니다.

두 개의 종료 조건이 있는 반복적인 프로세스의 이러한 일반적인 경우를 통해 잘 알려진 장벽 트릭(센티넬)을 사용할 수 있습니다. 여기서는 값 X로 장벽 a0을 설정하여 적용하기 쉽습니다. (이를 위해서는 변수 a에 대한 설명에서 인덱스 범위를 0 ... n으로 확장해야 합니다.)

직접 포함 방법 분석. i번째 선별에서 키 비교(Ci)의 수는 최대 i - 1, 최소 - 1입니다. n 키의 모든 순열이 동일할 가능성이 있다고 가정하면 평균 비교 횟수는 i/2입니다. 전송 수(요소 할당) Mi는 Ci + 2(장벽 포함)와 같습니다. 그렇기 때문에 총 수비교 및 전송 횟수는 다음과 같습니다.

저장 = (n2 + n - 2)/4,

Сmax = (n2 + n - 4)/4,

M min \u003d Z * (n - 1),

M ave \u003d (n2 + 9n - 10) / 4,

M 최대 = (n2 + 3n - 4)/2.

최소 추정은 이미 정렬된 초기 요소 시퀀스의 경우 발생하는 반면 최악의 추정은 처음에 역순으로 정렬될 때 발생합니다. 어떤 의미에서 내포물을 기준으로 정렬하는 것은 정말 자연스러운 동작을 나타냅니다. 위의 알고리즘이 안정적인 정렬 프로세스를 설명한다는 것은 분명합니다. 동일한 키를 가진 요소의 순서는 변경되지 않고 그대로 유지됩니다.

직접 삽입이 포함된 알고리즘은 삽입하려는 완성된 시퀀스(a1 ... ai-1 , 새로운 요소, 자체가 이미 주문되었습니다. 완성된 시퀀스의 중간과 비교를 시도하는 이진 탐색에서 멈추고 포함점을 찾을 때까지 반으로 나누는 과정이 계속되는 것은 당연하다. 이러한 수정된 정렬 알고리즘을 이진 삽입 방법이라고 합니다.

정렬은 선택한 매개변수에 따라 메모리에 있는 데이터를 정기적으로 정렬하는 것입니다. 규칙성은 데이터 배열의 처음부터 끝까지 매개변수 값의 증가(감소)로 간주됩니다.

데이터를 처리할 때 데이터의 정보 필드와 기계에서의 위치를 ​​아는 것이 중요합니다.

내부 정렬과 외부 정렬을 구별하십시오.

내부 정렬 - 정렬 랜덤 액세스 메모리;

외부 정렬 - 외부 메모리에서 정렬.

정렬할 레코드가 많은 양의 메모리를 차지하는 경우 이동하는 데 비용이 많이 듭니다. 그것들을 줄이기 위해 정렬이 수행됩니다. 키 주소 테이블즉, 포인터의 순열을 수행하고 배열 자체는 이동하지 않습니다. 그것 - 주소 테이블 정렬 방법.

정렬할 때 동일한 키가 발생할 수 있습니다. 이 경우 소스 파일과 동일한 순서로 정렬 후 동일한 키를 정렬하는 것이 바람직합니다.그것 - 안정적인 정렬.

추가 RAM을 사용하지 않는 종류만 고려할 것입니다. 이러한 종류를 "같은 자리에".

분류 효율성은 몇 가지 기준에 따라 고려할 수 있습니다.

정렬에 소요된 시간

정렬에 필요한 RAM의 양입니다.

프로그래머가 프로그램을 작성하는 데 소요한 시간입니다.

우리는 첫 번째 기준을 선택합니다. 정렬에 소요된 시간과 동일하다고 생각할 수 있습니다. 비교 횟수그리고 움직임의 수정렬할 때.

정렬 중 비교 및 ​​이동 횟수의 순서는

O(n log n)에서 O(n 2)로;

O(n)은 이상적이고 도달할 수 없는 경우입니다.

다음과 같은 정렬 방법이 있습니다.

엄격한 (직접) 방법;

개선된 방법.

엄격한 방법:

직접 연결 방법;

직접선택방식;

직접 교환 방식.

엄격한 방법의 효율성은 거의 동일합니다.

직접 포함 정렬

요소는 정신적으로 기성 시퀀스 a 1 ,...,a i-1 및 원본 시퀀스로 나뉩니다.

각 단계에서 i = 2부터 시작하여 매번 i를 1씩 증가시키면서 원래 시퀀스에서 i번째 요소를 추출하여 완성된 시퀀스로 옮기면서 올바른 위치에 삽입합니다.

알고리즘의 본질은 다음과 같습니다.

i = 2 ~ n에 대해

X = 에이(i)

우리는 (1) ... a (i) 중에서 x를 포함하는 장소를 찾습니다.

다음 나는

두 가지 직접 포함 정렬 알고리즘이 있습니다. 첫 번째 - 장벽 없음

배리어 프리 직접 포함 정렬 알고리즘

i = 2 ~ n에 대해

X = 에이(i)

j = i - 1에서 1까지

만약 x< a(j)

그러면 a(j + 1) = a(j)

그렇지 않으면 L로 이동

엔디프

다음 j

패: a(j + 1) = x

다음 나는

반품

위 알고리즘의 단점은 기술 위반 구조화된 프로그래밍, 무조건 점프를 사용하는 것은 바람직하지 않습니다. 내부 루프가 while 루프로 구성되어 있으면 "장벽"이 필요하며, 키의 음수 값으로 인해 컴퓨터의 중요성이 손실되고 "정지"가 발생합니다.

Barrier Direct Inclusion 정렬 알고리즘

i = 2 ~ n에 대해

X = 에이(i)

A(0) = x (a(0) - 장벽)

J = 나 - 1

동안 x< a(j) do

A(j+1) = 에이(j)

J = j - 1

그 동안

A(j+1) = x

다음 나는

반품

직접 포함 알고리즘의 효율성

i 번째 선별에서 주요 비교 Ci의 수는 최대 i-1, 최소 -1입니다. N 키의 모든 순열이 동일할 가능성이 있다고 가정하면 평균 비교 횟수 = i/2입니다. 전송 횟수는 Mi=Ci+3(배리어 포함)입니다. 최소 추정은 이미 정렬된 초기 요소 시퀀스의 경우 발생하는 반면 최악의 추정은 처음에 역순으로 정렬될 때 발생합니다. 어떤 의미에서 포함을 기준으로 정렬하는 것은 정말 자연스러운 동작을 나타냅니다. 위의 알고리즘이 안정적인 정렬 프로세스를 설명한다는 것은 분명합니다. 동일한 키를 가진 요소의 순서는 변경되지 않고 그대로 유지됩니다.

최악의 경우의 비교 횟수, 배열을 반대로 정렬하면 C max = n(n - 1) / 2, 즉 - O(n 2). 순열의 수 M max = C max + 3(n-1), 즉 - 오 (n 2). 배열이 이미 정렬된 경우 비교 및 ​​순열의 수는 최소입니다. C min = n-1; Mmin = = 3(n-1).

직접 교환 정렬(버블 정렬)

에 이번 장두 요소의 위치 교환이 프로세스의 가장 특징적인 기능인 방법이 설명됩니다. 아래에 설명된 직접 교환 알고리즘은 쌍의 위치를 ​​비교하고 변경하는 것을 기반으로 합니다. 이웃 요소모든 요소가 주문될 때까지 이 프로세스를 계속합니다.

나머지 시퀀스의 가장 작은 요소를 배열의 왼쪽 끝으로 이동할 때마다 배열을 반복합니다. 배열을 수평 구조가 아닌 수직 구조로 간주하면 요소는 키에 해당하는 각각의 무게와 함께 물통에 있는 거품으로 해석될 수 있습니다. 이 경우 통과할 때마다 하나의 거품이 말 그대로 해당 무게에 해당하는 수준으로 올라갑니다(아래 그림의 그림 참조).

C min = n - 1, 차수 O(n),

그리고 전혀 움직임이 없습니다.

직접 분류 방법에 대한 비교 분석은 고전적 형태의 교환 "분류"가 내포물을 사용한 분류와 선택을 사용한 분류 사이의 교차임을 보여줍니다. 위의 개선 사항이 적용되면 충분히 정렬된 배열의 경우 버블 정렬심지어 이점이 있습니다.

이 방법은 일반적으로 "버블 정렬"로 알려져 있습니다.

직접 교환 방법 알고리즘

j = n에서 i 단계 -1에 대해

만약 a(j)< a(j - 1) then

우리의 경우 "유휴" 패스가 하나 있습니다. 요소를 다시 한 번 보지 않고 비교하기 위해 이에 시간을 할애하려면 확인란을 입력할 수 있습니다. 플로리다, 값에 남아 거짓, 다음 패스 중에 교환이 이루어지지 않는 경우. 아래 알고리즘에서 추가는 굵게 표시됩니다.

fl = 사실

fl = false이면 반환

fl=거짓

j = n에서 i 단계 -1에 대해

만약 a(j)< a(j - 1) then

fl = 사실

버블 정렬의 개선 사항은 각 통과 후 내부 루프에서 방향이 반전되는 셰이커 정렬입니다.

직접 교환 정렬 알고리즘의 효율성

비교 횟수 C max = n(n-1)/2 , 차수 O(n 2).

이동 횟수 M max \u003d 3C max \u003d 3n (n-1) / 2, O (n 2)의 순서.

배열이 이미 정렬되어 있고 플래그 알고리즘이 적용된 경우 한 번만 통과하면 충분하며 최소 비교 횟수를 얻습니다.

단순 선택 정렬과 같은 직접 포함 정렬은 일반적으로 중복 요소를 포함하지 않는 배열에 사용됩니다.

위에서 설명한 모든 항목과 마찬가지로 직접 포함 방법에 따른 정렬은 단계적으로 수행됩니다. k 번째 단계에서 첫 번째 k-1개 요소를 포함하는 배열의 일부가 이미 정렬된 것으로 간주됩니다.

a ≤ a ≤ ... ≤ a .

다음으로, k 번째 요소를 가져와서 배열의 정렬된 부분에서 해당 위치를 찾아 삽입 후 순서가 위반되지 않도록 해야 합니다. 즉, 다음과 같은 j(1 ≤ j ≤ k -1) a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

각 단계마다 배열의 정렬된 부분이 증가합니다. 완전한 정렬을 수행하려면 n-1 단계가 필요합니다.

이 과정을 예를 들어 살펴보겠습니다. 직접 포함 방법을 사용하여 10개 요소의 배열을 오름차순으로 정렬해야 한다고 가정합니다.

1 - 세 번째 단계

13 6 8 11 3 1 5 9 15 7

멘타(13). 두 번째를 넣어야 합니다.

배열 요소(6)는

성을 유지했습니다. 6부터< 13, вставляем

6위 1위. 정렬된 부분

배열에는 두 개의 요소가 있습니다(6 13).

3 - 세 번째 단계

6 8 13 11 3 1 5 9 15 7 다음 요소- 11. 11 > 8 이므로 배열의 순서 부분에 3번째로 작성되지만 11< 13.

5- 단계

3 6 8 11 13 1 5 9 15 7 같은 이유로 1이 첫 번째에 기록됩니다.

6 - 단계

1 3 6 8 11 13 5 9 15 7 5 > 3 이후이지만 5< 6 то место 5 в упоря-

딸 부분은 세 번째입니다.

7 -단계

1 3 5 6 8 11 13 9 15 7 숫자 9의 자리는 여섯 번째입니다.

8 -단계

1 3 5 6 8 9 11 13 15 7 끝에서 두 번째 위치 결정

요소 15. 이 요소는

배열의 요소가 이미 있습니다.

9 -단계

1 3 5 6 8 9 11 13 15 7 적절한 장소를 찾는 것이 남아 있습니다.

마지막 요소(7).

1 3 5 6 7 8 9 11 13 15 배열이 완전히 정렬됩니다.

이제 직접 포함 정렬 알고리즘의 일부를 간략하게 설명할 수 있습니다.

k의 경우:= 2 ~ n Do

(나는 좋은 장소를 찾는 것으로 정렬을 시작하기 때문에, 나는 2에서 n으로 간다)

', ..., a[k]의 적절한 위치에 x를 삽입'

요소 x에 적합한 장소를 찾는 방법에 대한 질문에 답해야 합니다. 다음을 수행합니다. x의 왼쪽에 있는 요소(즉, 이미 정렬된 요소)를 살펴보고 배열의 시작 부분으로 이동합니다. 요소 a[ j ], j가 k-1에서 1로 변경되는 것을 스캔해야 합니다. 이러한 스캔은 다음 조건 중 하나가 충족될 때 종료되어야 합니다.

발견된 요소 a[j]< x, что говорит о необходимости вставки x между a и a[j].

· 배열의 정렬된 부분의 왼쪽 끝에 도달했으므로 먼저 x를 삽입해야 합니다.

이러한 조건 중 하나가 충족될 때까지 표시된 요소를 오른쪽의 첫 번째 위치로 이동하고 결과적으로 x 아래의 공간이 정렬된 부분에서 해제됩니다.

직접 포함 분류 프로그램:

프로그램 n3; ( 내림차순으로 정렬 )

유형 ar=정수 배열;

절차 sorting3(var a:ar);

var i,j,x,k:정수;

k:=2에서 n에 대해

x:=a[k]; j:=k-1;

(j>0)and(x>=a[j]) 하는 동안

writeln("원본 배열을 입력하세요:");

for i:=1 to n do read(a[i]);

writeln("정렬된 배열:");

for i:=1 to n do write(a[i]," ");

목적직접 포함 방법에 의한 배열 정렬을 조사하고 이 알고리즘의 효율성을 평가합니다.

일반 정보

단순 선택 정렬과 같은 직접 포함 정렬은 일반적으로 중복 요소를 포함하지 않는 배열에 사용됩니다. 이 방법에 의한 정렬은 단계별로 순차적으로 수행됩니다. 에 k번째 단계첫 번째 k-1 요소를 포함하는 배열의 일부가 이미 정렬된 것으로 간주됩니다. 다음으로 취해야 할 k번째 요소삽입 후 순서가 방해받지 않도록 배열의 정렬 된 부분에서 위치를 선택하십시오. 즉, 그런 것을 찾아야합니다. 그런 다음 찾은 위치에 요소[k]를 삽입해야 합니다. 각 단계마다 배열의 정렬된 부분이 증가합니다. 완전한 정렬을 수행하려면 n-1 단계가 필요합니다. 요소 x에 적합한 장소를 찾는 방법에 대한 질문에 답해야 합니다. 다음과 같이 진행할 것입니다. x의 왼쪽에 있는 요소(즉, 이미 정렬된 요소)를 살펴보고 배열의 시작 부분으로 이동합니다. 요소 a[j]를 스캔해야 하며 j가 k-l에서 1로 변경됩니다. 이러한 스캔은 다음 조건 중 하나가 충족될 때 종료됩니다: 요소 a[j]가 발견됩니다. 직접 포함을 사용하는 정렬 알고리즘: k:= 2에서 n까지 do beginx:= a[k]; j:=k-1; ( a, ..., a[k] 의 적절한 위치에 x 삽입 ) (이렇게 하려면 while ) ( j > 0 및 x 를 실행하는 루프를 구성합니다.

제어 작업

동일한 배열의 첫 번째 음수 요소 뒤에 배열의 마지막 요소를 삽입하는 프로그램을 작성하십시오.

작업 옵션

주목!!! 별도로 명시하지 않는 한 입력 데이터(소스 배열) 및 출력 데이터(정렬된 배열)는 다음과 같이 구성됩니다. 텍스트 파일, 정수 포함! 모든 작업에 대해 직접 포함 방법을 사용하여 배열을 정렬하는 절차를 미리 작성합니다. 1. n개의 요소를 포함하는 시리즈가 주어집니다. 모든 중복 요소를 버리고 오름차순으로 정렬합니다. 2. 패션을 정의하다 이 시리즈- 요소 중에서 가장 자주 발생하는 값. 3. 원본 데이터 세트는 성, 나이 및 근속 기간으로 구성된 일련의 레코드입니다. 이 목록을 인쇄하십시오: 1) 알파벳 순서로; 2) 나이가 많은 순서대로; 3) 업무 경험을 늘리기 위해. 4. 내림차순으로 정렬하는 절차를 작성하십시오. 5. 일련의 정수가 주어집니다. 모두 오름차순으로 가져오기 다양한 숫자이 시리즈에 포함되어 있습니다. 6. 일련의 n개의 고유한 정수가 제공됩니다. 다음과 같은 고유 정수를 얻으십시오. 7. 주어진 정수 찾기 가장 높은 가치이 순서에서 값을 가진 모든 구성원을 제거한 후 8. 주어진 자연 숫자는 n명의 선수가 100m를 100분의 1초 단위로 측정한 결과입니다. 4x100 계주 경기에 참가할 최고의 주자 4명으로 팀을 구성합니다. 즉, 4개의 자연수 i, j, k 중 하나를 표시 , 나는 합계가 값이 가장 작습니다. 9. 좌표(xi; yi)가 있는 n개의 독립적인 임의 점이 주어지면 원점을 중심으로 하는 반지름 1의 원에 균일하게 분포됩니다. 중심에서 멀어지는 순서대로 점을 배열하는 프로그램을 작성하십시오. 10. n개의 양의 두 자리 정수가 제공됩니다. 각 숫자를 0-9 범위의 숫자 쌍으로 취급하여 오름차순으로 정렬합니다(숫자). 11. 평면에 n개의 점이 주어집니다. 이 모든 점을 통과하는 (n-1) 링크 자체 교차하지 않는 닫힌 폴리선을 지정합니다. (폴리라인의 인접 세그먼트는 동일한 직선에 놓일 수 있습니다.) 힌트. 가장 왼쪽에 있는 점(즉, x 좌표가 가장 작은 점)을 가져와 다른 모든 점으로 광선을 그립니다. 이제 이 광선을 아래쪽에서 위쪽으로 정렬하고 광선의 시작 부분으로부터의 거리만큼 한 광선의 점을 정렬합니다(이 작업은 아래쪽 및 위쪽 광선을 제외한 모든 광선에 대해 수행됨). 폴리라인은 아래쪽 광선을 따라 선택된(가장 왼쪽) 점을 떠난 다음 다른 모든 광선을 따라(설명된 순서대로) 위쪽 광선을 따라 돌아옵니다. 12. 평면에 n개의 점이 주어집니다. 볼록 껍질(볼록 껍질을 포함하는 최소 볼록 모양)을 구성합니다. (보드에 박힌 못 위로 뻗어 있는 고무 링은 볼록한 껍질입니다.) 표시. 포인트를 정리해보자. 그런 다음 점을 차례로 고려하여 이미 고려한 점의 볼록 껍질을 구성합니다.