알고리즘은 제한된 수의 단계에서 문제를 해결하는 데 사용되는 잘 정의된 규칙 집합입니다. 쉽게 말하면 컴퓨터가 문제를 해결하는 과정이다. 이 과정에서 문제 해결 아이디어를 구상하든, 프로그램을 작성하든 특정 알고리즘을 구현하게 됩니다. 전자는 추론에 의해 구현된 알고리즘이고, 후자는 연산에 의해 구현된 알고리즘이다.
알고리즘에는 다음과 같은 다섯 가지 중요한 특성이 있어야 합니다.
1. 유한성: 알고리즘은 유한한 수의 단계를 실행한 후에 종료되도록 보장해야 합니다.
2. 정확성: 알고리즘의 각 단계는 명확하게 정의되어야 합니다.
3. 입력: 알고리즘에는 피연산자의 초기 상황을 설명하기 위한 0개 이상의 입력이 있습니다.
4. 출력: 알고리즘에는 입력 데이터 처리 결과를 반영하는 하나 이상의 출력이 있습니다. 출력이 없는 알고리즘은 의미가 없습니다.
5. 타당성: 원칙적으로 알고리즘은 정확하게 실행될 수 있으며 제한된 수의 작업을 수행하기 위해 펜과 종이를 사용하여 사람들이 완료할 수 있습니다.
병합 정렬(MERGE SORT)은 다른 정렬 방법의 또 다른 유형입니다. 병합의 의미는 두 개 이상의 정렬된 데이터 시퀀스를 새로운 정렬된 데이터 시퀀스로 병합하는 것이므로 병합 알고리즘이라고도 합니다. 기본 아이디어는 배열 A에 N개의 요소가 있다고 가정하는 것입니다. 그러면 배열 A는 N개의 정렬된 하위 시퀀스로 구성되고 각 하위 시퀀스의 길이는 1인 다음 2를 2로 병합하여 N/2개의 정렬된 하위 시퀀스를 얻습니다. 그런 다음 길이 2 또는 1을 2개씩 병합하고 길이 N의 정렬된 데이터 시퀀스를 얻을 때까지 이 정렬 방법을 양방향 병합 정렬이라고 합니다.
예를 들어 배열 A에는 49 38 65 97 76 13 27의 7개 데이터가 있습니다. 그러면 병합 정렬 알고리즘을 사용하는 작업 프로세스가 그림 7에 표시됩니다.
초기값[49][38][65][97][76][13][27]
길이가 1인 7개의 하위 시퀀스로 구성된 것으로 보입니다. 첫 번째 합병 이후 [38 49] [65 97] [13 76] [27]
길이가 1 또는 2인 4개의 하위 시퀀스로 구성된 것으로 표시됩니다. 두 번째 합병 이후 [38 49 65 97] [13 27 76]
길이가 4 또는 3인 2개의 하위 시퀀스로 구성된 것으로 보입니다. 세 번째 병합 이후 [13 27 38 49 65 76 97]
그림 6 병합 정렬 알고리즘 프로세스 다이어그램 병합 알고리즘의 핵심 작업은 1차원 배열에서 두 개의 인접한 정렬된 시퀀스를 하나의 정렬된 시퀀스로 병합하는 것입니다. 병합 알고리즘은 재귀 알고리즘을 사용하여 구현할 수도 있는데, 이는 상대적으로 형태가 간단하지만 실용성이 떨어진다.
병합 알고리즘에서 병합 개수는 매우 중요한 수량으로, 계산에 따르면 배열의 요소가 3~4개일 경우 병합 개수는 2, 5~8개일 경우 병합 개수는 3입니다. , 9 ~ 16개의 요소가 있는 경우 병합 개수는 4개입니다. 이 규칙에 따르면 N개의 하위 시퀀스가 있는 경우 병합 개수는 다음과 같다고 추론할 수 있습니다.
X (2>=N, 하위 조건을 충족하는 가장 작은 X).
버블 알고리즘 설명:
버블 정렬 알고리즘을 설명하기 전에 먼저 배열 A의 10개 숫자 중 가장 큰 숫자를 마지막 위치에 놓는 알고리즘을 소개하겠습니다. 알고리즘은 다음과 같이 설명됩니다.
(1) 배열 A[1]부터 A[10]까지 인접한 두 숫자를 쌍으로 비교합니다. 즉, A[1]을 A[2]와 비교하고, 비교 후 A[2]를 A[3]과 비교하고...최종적으로 A[9]를 A[10]과 비교합니다.
(2) 각 비교 중에 앞의 숫자가 뒤의 숫자보다 크면 두 숫자가 서로 바뀌게 됩니다. 즉, 큰 숫자는 뒤로 이동되고 작은 숫자는 앞으로 이동됩니다. 예를 들어, 첫 번째 비교에서 A[1]이 A[2]보다 크면 A[1]과 A[2]의 값이 서로 바뀌게 됩니다. 아래 그림에서는 위의 알고리즘을 설명하기 위해 6개의 데이터를 사용합니다.
6개의 데이터가 다음과 같다고 가정합니다: A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 처음에는 A[1]=5와 A[2]=7을 비교하여 7>5로 교환을 수행하지 않습니다.
5 7 4 3 8 6 두 번째로 A[2]=7과 A[3]=4를 비교하여 4<7로 교환합니다.
그러면 두 번째 비교 후의 데이터는 5 4 7 3 8 6 입니다.
5 4 7 3 8 6 세 번째로 A[3]=7과 A[4]=3을 비교하여 3<7로 교환합니다.
그러면 세 번째 비교 후의 데이터는 5 4 3 7 8 6 입니다.
5 4 3 7 8 6 네 번째로 A[4]=7과 A[5]=8을 비교하면 8>7이며 스왑이 수행되지 않습니다.
5 4 3 7 8 6 다섯 번째로 A[6]=6과 A[5]=8을 비교하여 6<8로 교환합니다.
그러면 다섯 번째이자 최종 결과는 다음과 같습니다.
5 4 3 7 6 8
************************************************** * *****
선택 정렬 알고리즘에 대한 설명:
선택 정렬 방법을 소개하기 전에 가장 작은 숫자를 첫 번째 위치에 넣는 알고리즘을 소개하겠습니다. 물론 위에서 언급한 버블 정렬 방법을 사용할 수도 있습니다. 이제 새로운 알고리즘을 사용합니다. 처음에는 서둘러 자리를 바꾸지만, 일단 시작하세요. A[1]은 어느 숫자가 가장 작은지 확인하기 시작합니다. 스캔이 완료된 후 A[P]와 A[1]을 교환합니다. [1] ~ A[10]이 앞으로 이동합니다. 알고리즘의 단계는 다음과 같습니다.
1) 먼저 A[1]에 있는 숫자가 가장 작다고 가정하고 이때 위치 P=1에 주목한다.
2) A[P]와 A[I]를 차례로 비교합니다(I는 2에서 10으로 변경됩니다). 각 비교 중에 A[I]의 숫자가 A[P]의 숫자보다 작으면 I 값이 됩니다. P에 할당되므로 P는 항상 현재 스캔된 가장 작은 숫자의 위치를 가리킵니다. 즉, A[P]는 항상 스캔된 모든 숫자 중 가장 작은 숫자와 같습니다. 하나씩 비교한 후, P는 10개의 숫자 중 가장 작은 숫자의 위치를 가리킨다. 즉, A[P]는 10개의 숫자 중 가장 작은 숫자이다.
3) A[P]와 A[1]의 숫자를 반대로 하면 가장 작은 숫자가 A[1], 즉 맨 앞이 됩니다.
이제 이 알고리즘을 반복하지만 반복될 때마다 비교되는 계열의 범위가 한 위치 뒤로 이동합니다. 즉, 두 번째 비교에서는 범위가 2번째 숫자부터 N번째 숫자까지가 됩니다. 이 범위 내에서 가장 작은 숫자의 위치 P를 찾은 다음 A[P]와 A[2]를 바꿔서 2번째 숫자부터가 되도록 합니다. 처음부터 N 번째 숫자까지 가장 작은 숫자는 A에 있습니다. [2]는 성공하고, 세 번째는 3번째 숫자부터 N번째 숫자까지 가장 작은 숫자를 찾아 A[P]와 A[3]을 바꾸는 것인데... 이 과정을 N-1번 반복한 후, 그냥 정리하면 됩니다. 배열 A의 N개 숫자를 작은 것부터 큰 것 순으로 나열합니다. 이 정렬 방법은 선택 정렬입니다.
************************************************** * ***************
삽입 정렬 알고리즘 설명:
위의 두 가지 방법을 배우면 정렬의 기본 아이디어를 이해할 수 있으며, 정렬되지 않은 배열을 큰 것에서 작은 것(내림차순) 또는 작은 것에서 큰 것(오름차순)으로 정렬할 수도 있습니다. 이제 이미 정렬된 데이터 시퀀스가 있다고 가정하고, 이미 정렬된 이 데이터 시퀀스에 숫자를 삽입해야 하지만, 삽입 후에도 데이터 시퀀스가 여전히 정렬되어 있어야 합니다. 이때 새로운 정렬 방법이 필요합니다. 사용 - 삽입 정렬 방법, 삽입 정렬의 기본 작업은 정렬된 데이터에 데이터를 삽입하여 숫자에 1을 더한 새로운 정렬 데이터를 얻는 것입니다.
질문: 배열 A에는 N개의 데이터가 작은 것부터 큰 순서로 배열되어 있습니다. 숫자 X를 입력하고 X의 값을 배열 A에 삽입하면 삽입된 배열 A가 여전히 작은 것부터 큰 것의 순서로 배열됩니다. .
그러면 이 문제를 해결하는 알고리즘은 다음과 같습니다.
1) X를 I번째 위치에 배치해야 할 경우 크기를 비교하여 X를 삽입해야 하는 위치를 찾습니다.
2) I(I 포함)부터 시작하여 모든 배열 요소를 한 위치 뒤로 이동합니다. 즉, A[I+1]:=A[I];
퀵 정렬은 버블 정렬을 개선한 것입니다. 기본 아이디어는 단방향 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나누는 것입니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작으며, 그런 다음 데이터의 두 부분을 순차적으로 정렬합니다. 빠른 정렬을 위해서는 전체 정렬 과정을 재귀적으로 수행하여 전체 데이터가 정렬된 순서가 되도록 할 수 있습니다.
정렬할 배열이 A[1]...A[N]이라고 가정합니다. 먼저 데이터(보통 첫 번째 데이터)를 키 데이터로 무작위로 선택한 다음 그보다 큰 숫자를 모두 앞에 배치합니다. 그보다 큰 모든 숫자는 그 뒤에 배치됩니다. 이 프로세스를 빠른 정렬이라고 합니다. 빠른 정렬의 알고리즘은 다음과 같습니다.
1) 두 개의 변수 I, J를 설정합니다. 정렬이 시작되면 I:=1, J:=N;
2) 첫 번째 배열 요소를 키 데이터로 사용하고 이를 X에 할당합니다. 즉, X:=A[1];
3) J부터 앞으로 검색, 즉 뒤에서 앞으로 검색(J:=J-1)하여 X보다 작은 첫 번째 값을 찾아 두 값을 교환합니다.
4) I부터 역방향 검색, 즉 앞에서 뒤로 검색(I:=I+1)하여 X보다 큰 첫 번째 값을 찾아 두 값을 교환합니다.
5) I=J가 될 때까지 3단계와 4단계를 반복합니다.
예: 정렬할 배열 A의 값은 다음과 같습니다. (초기 키 데이터 X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
첫 번째 교환 이후: 27 38 65 97 76 13 49
(두 번째 교환을 위해 알고리즘의 세 번째 단계에 따라 뒤에서부터 검색한 후 : 27 38 49 97 76 13 65
(알고리즘의 4번째 단계를 따라가며 맨 앞부분부터 시작하여 값을 찾는다 >
세 번째 교환 이후: 27 38 13 97 76 49 65
(알고리즘의 다섯 번째 단계에 따라 마지막부터 다시 알고리즘의 세 번째 단계를 실행하여 네 번째 교환을 찾습니다. 27 38 13 49 76 97 65
(알고리즘의 네 번째 단계를 따라 맨 앞에서 시작하여 X보다 큰 값인 97>49를 찾고, 두 값을 교환합니다. 이때 J:=4)
이때, 세 번째 단계를 실행하면 I=J임을 알 수 있어 퀵 정렬이 종료됩니다. 27 38 13 49 76 97 65, 즉 49보다 큰 숫자는 모두 49에 들어갑니다. 이므로 49보다 작은 숫자는 모두 49 앞에 옵니다.
퀵정렬은 이 과정을 재귀적으로 호출하는 것인데, 49를 중간점으로 데이터열을 분할하고, 앞부분과 뒷부분도 비슷한 퀵정렬을 수행하여 전체 데이터열의 퀵정렬을 완성하고 마지막으로 데이터열을 뒤집는 것이다. 이 아이디어에 따르면 위의 배열 A를 빠르게 정렬하는 전체 프로세스가 그림 6에 나와 있습니다.
초기 상태 {49 38 65 97 76 13 27}
퀵 정렬을 거쳐 {27 38 13} 49 {76 97 65}로 나누어집니다.
앞부분과 뒷부분을 각각 빠르게 정렬하세요. {13} 27 {38}
끝 끝 {49 65} 76 {97} 49 {65} 끝 끝
************************************************** * *************************
그림 6 빠른 정렬 프로세스 전반에 걸친 빠른 정렬의 알고리즘 설명
1) N(N=10이라고 가정) 숫자가 S 배열에 저장되어 있다고 가정합니다.
2) S[1. . N]의 임의 요소를 비교 기준으로 사용합니다. 예를 들어 T=S[1]을 사용합니다. 초기 목적은 정렬 결과에서 T가 있어야 하는 위치 K를 결정하는 것입니다. . . K-1]<=S[K]<=S[K+1..N] 즉, S[K] 이전의 숫자는 모두 S[K]보다 작고, S[K] 이후의 숫자는 모두 S[K]보다 크다;
3) 분할정복 아이디어(즉, 크고 작은 것을 작게 만드는 전략)를 활용하면 S[1. . K-1] 및 S[K+1. . N] 그런 다음 그룹화 개체에 데이터가 하나만 남을 때까지 두 개의 데이터 세트가 빠르게 정렬됩니다.
특정 데이터가 다음과 같은 경우 첫 번째 빠른 정렬 프로세스는 다음과 같습니다.
배열 첨자: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ij
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53