배열에 있는 값을 오름차순 또는 내림차순으로 정렬(정렬)하기 위해 많은 방법이 개발되었다[Wirt, Knuth. m 3]. 명확성을 위해 처음 n, n=6, 배열 X의 요소가

다음 i번째 단계마다 i=2, 3,… 이전 셀에 더 작은 숫자가 포함된 것으로 판명될 때까지 셀 인덱스를 줄이는 방향으로.

방법을 구현할 때 위의 내용을 따릅니다. 직접 연결외부 루프는 n-1번 실행되어야 하며, 내부 루프의 가능한 최대 실행 횟수는 숫자의 비교 및 ​​순열이 수행되어야 하는 본문에서 1에서 n-1로 증가합니다. 그러나 내부 루프는 조건이 발생할 때 종료되거나 전혀 실행되지 않는 방식으로 구성되어야 합니다. 이전 배열 셀의 값이 현재 배열 셀의 값보다 작습니다.

우리의 예에서:

i=2일 때 셀 X 3의 숫자 15는 셀 X 2의 숫자 34와 차례로 자리를 바꾼 다음 셀 X 1의 숫자 21,

i=4일 때 셀 X 5의 숫자 25는 셀 X 3의 숫자 34와 자리를 바꿉니다.

다음은 직접 포함 방법(순서 보존 포함)을 사용하여 배열 X의 처음 n개 요소를 오름차순으로 정렬하는 프로그램의 일부입니다.

i:=1 ~ n-1의 경우

2. 동안 (X 0) 할

3. R:=X[j];

   X[j]:=X;

   X:=R;

배열의 숫자를 내림차순으로 정렬하려면 각 단계에서 배열의 인접 셀에 있는 숫자를 치환하는 조건을 반대로 하는 것으로 충분합니다. 즉, 다음과 같은 경우 인접 셀의 값 교환이 수행됩니다. 이전 것이 현재 것보다 작습니다.

직접 교환 방식(버블 방식).

이 방법은 앞의 방법과 마찬가지로 이웃한 배열 셀의 값 교환을 기반으로 하지만, 순차 분석의 첫 번째 단계부터 배열의 한쪽 끝에서 다른 쪽 끝으로 이동할 때 인접한 배열 셀의 모든 쌍 참가하다.

첫 번째 단계에서 j = n, n-1, ..., 2에 대해 순차적으로 배열의 인접 셀 값을 비교하고 조건 Х j일 때<Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

이 예에서 첫 번째 단계 후에 배열의 데이터는 다음과 같이 위치합니다.

각 다음 단계에서 검사된 셀 쌍의 수는 1씩 감소합니다. 일반적으로 i, i=1, 2, 3, ..., n-1 단계에서 n부터 j에 대해 프로세스가 수행됩니다. i+1로, 특히 i= n-1인 경우 – n번째 및 (n-1)번째 셀에 대해 한 번만.

위와 같이 직접 교환 방식을 구현할 경우 외부 루프를 n-1번 실행해야 하며, 본문에서 숫자의 비교 및 ​​순열을 수행해야 하는 내부 루프의 실행 횟수가 감소함을 알 수 있습니다. n-1에서 1로.

"거품 방식"이라는 용어의 기원은 다음과 같이 설명됩니다. 인덱스가 위에서 아래로 증가하는 배열 셀의 수직 배열을 상상하면 고려되는 가장 작은 숫자가 물 속의 거품처럼 상승할 것입니다.

우리의 예에서

i=3인 경우 순열은 배열의 다음 상태로 이어집니다.

버블 방식을 사용할 때 배열의 숫자 쌍의 분석이 위 또는 아래로 이동하는지 여부는 중요하지 않으며 정렬 유형(오름차순 또는 내림차순)은 숫자를 순열하는 조건에 의해서만 결정됩니다. 더 큰 뒤에 위치하거나 그 반대).

수정된 직접 교환 방식(수정된 버블 방식).

위의 수치 예시에서 알 수 있듯이 배열은 4단계 이후에 이미 정렬된 것으로 판명되었습니다. 이미 주문되었습니다. 이러한 검사는 다음을 기반으로 합니다. 내부 루프를 실행하는 동안 단일 순열이 없으면 배열이 이미 정렬되어 있고 외부 루프를 종료할 수 있습니다. 순열이 수행되었는지 여부의 표시로 부울 유형 변수가 사용됩니다. 내부 루프에 들어가기 전에 하나의 값(예: False)이 주어지고 순열이 수행되면 다른 값(예: True)이 주어집니다.

분명히, 정렬 프로세스의 속도를 높이는 수정되지 않은 방법과 비교하여 수정된 거품 방법을 사용하는 효과는 원래 숫자 시퀀스가 ​​원하는 방향으로 정렬되는 것과 가까우면 관찰될 것입니다. 제한적인 경우 배열이 이미 올바른 방식으로 정렬되어 있으면 외부 루프의 본문이 한 번만 실행됩니다.

방법: 수분 함량에 대한 이러한 물질의 유전 상수 의존성을 기반으로 물질의 수분 함량을 간접적으로 측정하는 방법. 출처: RMG 75 2004: 식량 제공을 위한 국가 시스템 ...

피- BLOOD(혈액) 몸의 동맥, 정맥, 모세혈관을 채우는 액체로 투명한 담황색을 띤다. 혈장의 색과 그 안에 떠 있는 모양 요소: 적혈구 또는 적혈구, 흰색 또는 백혈구, 혈액 플라크 또는 ... 큰 의학 백과사전

부동산- (부동산) 부동산의 정의, 부동산의 종류, 부동산의 임대 및 매매 부동산의 개념, 부동산의 종류, 부동산의 임대 및 매매, 과세 및 보험에 대한 정보 콘텐츠는 재산의 일종 , ... ... 투자자의 백과사전

이 용어에는 다른 의미가 있습니다. C 참조

무형자산의 평가- (영어 무형 자산 평가) - 국가가 지정한 기간 동안 중요한 내용이 없고 기업에 소득을 가져다주는 특정 그룹의 대상에 대한 기업의 권리 규모 가치 결정 .... . 금융 및 신용 백과사전

학교 일반 교육- 계정. 기르다. 교육의 기본 요소인 기관. 시스템. 이 능력에서 Sh. 연구 decomp의 주제. 학문: 교육학, 역사, 인구 통계, 사회학 및 기타 교육학에서만 Sh.의 문제는 완전히 독립적입니다. 장소. 학습... ... 러시아 교육 백과사전

시각- 3.3.4 시간 tE(시간 tE): 정격 작동 모드에서 도달한 온도에서 최대 주변 온도에서 허용 온도까지 회전자 또는 고정자 권선의 초기 시동 교류 IA에 의한 가열 시간. 원천 … 규범 및 기술 문서 용어 사전 참조 책

GOST R IEC 60204-1-2007: 기계 안전. 기계 및 메커니즘의 전기 장비. 1부. 일반 요구 사항- 용어 GOST R IEC 60204 1 2007: 기계 안전. 기계 및 메커니즘의 전기 장비. 1부. 일반 요구 사항 원본 문서: TN 공급 시스템 18.2.2에 따른 방법 1에 따른 테스트는 각 회로에 대해 수행할 수 있습니다. ... ... 규범 및 기술 문서 용어 사전 참조 책

자동 3.3.1 파이프라인을 통해 흐르는 유체의 대표적인 샘플을 채취하는 데 사용되는 자동 샘플러 장치 참고 오토샘플러는 일반적으로 프로브(프로브), 추출기 ... ... 규범 및 기술 문서 용어 사전 참조 책

전압- 3.10 응력: 공칭 치수에서 링크 단면적에 대한 인장력의 비율.

이 방법은 카드 놀이를 할 때 널리 사용됩니다. 요소(지도)는 정신적으로 이미 "준비된" 시퀀스 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. 직접 선택에 의한 정렬의 예

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

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

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

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

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

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

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

추가 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