버블 정렬 알고리즘

교환 정렬의 기본 아이디어는 정렬할 레코드의 키워드를 쌍으로 비교하여 두 레코드의 순서가 역전된 것으로 확인되면 다음까지 교환을 수행하는 것입니다. 역순으로 된 기록이 없습니다.

교환 정렬의 기본 개념을 적용한 주요 정렬 방법으로는 버블 정렬과 퀵 정렬이 있습니다.

버블 정렬

1. 정렬 방법
정렬된 레코드 배열 R[1..n]을 수직으로 배열하고, 각 레코드 R[i]는 Bubbles의 가중치를 갖는 것으로 간주됩니다. R[i].key의 경우. 가벼운 기포는 무거운 기포 아래에 있을 수 없다는 원리에 따라 배열 R은 아래에서 위로 스캔됩니다. 이 원리를 위반하는 가벼운 기포는 위쪽으로 "부유"됩니다. 마지막 두 개의 거품이 위쪽의 더 가벼운 거품이고 아래쪽의 더 무거운 거품이 될 때까지 이 과정이 반복됩니다.
(1) 초기
R[1..n]은 순서가 없는 영역입니다.

(2) 첫 번째 스캔
무질서한 부분의 바닥에서 위쪽으로 인접한 두 개의 거품의 무게를 비교하면 더 가벼운 것이 바닥에 있고 더 무거운 것이 위쪽에 있는 것으로 확인됩니다. 상단, 둘의 위치를 ​​바꿉니다. 즉, (R[n], R[n-1]), (R[n-1], R[n-2]),..., (R[2], R[1])을 비교합니다. 각 쌍 Bubble(R[j+1], R[j])에 대해 시퀀스, R[j+1].key 첫 번째 스캔이 완료되면 "가장 가벼운" 버블이 간격의 상단으로 떠오릅니다. 즉, 가장 작은 키워드가 포함된 레코드가 가장 높은 위치 R[1]에 배치됩니다.

(3) 두 번째 스캔
R[2..n]을 스캔합니다. 스캔이 완료되면 "두 번째 빛" 버블이 R[2] 위치로 떠오릅니다...
마지막으로 n-1 스캔 후 정렬된 영역 R[1..n]
은 다음과 같습니다. 참고:
i번째 스캔 동안 R[1..i-1] 및 R[i..n]은 각각 현재 정렬된 영역과 정렬되지 않은 영역입니다. 스캔은 여전히 ​​무질서한 영역의 바닥에서 영역의 상단까지 진행됩니다. 스캔이 완료되면 해당 영역의 가장 가벼운 버블이 상단 위치 R[i]로 떠오르고 결과적으로 R[1..i]가 새로운 정렬된 영역이 됩니다.

2. 버블 정렬 프로세스의 예
키워드 순서로 파일을 버블 정렬하는 프로세스 49 38 65 97 76 13 27 49

3. ) 분석
정렬 작업을 수행할 때마다 정렬된 영역에 거품이 추가되므로 n-1개의 정렬 작업을 수행하면 정렬된 영역에는 n-1개의 거품이 생기고 무질서한 영역의 거품 수는 가중됩니다. 항상 정렬된 영역의 버블 무게보다 크거나 같으므로 전체 버블 정렬 프로세스에는 최대 n-1 정렬 작업이 필요합니다.
특정 정렬 패스에서 버블 위치의 교환이 발견되지 않으면 정렬되지 않은 영역의 모든 버블이 위쪽에 있는 거품과 아래쪽에 있는 무거운 거품의 원리를 충족한다는 의미입니다. 버블 정렬 프로세스는 여기에서 수행할 수 있습니다. 정렬 후 종료하세요. 이를 위해 아래 알고리즘에서는 부울 교환이 도입되었으며 각 정렬이 시작되기 전에 FALSE로 설정됩니다. 정렬 중에 교환이 발생하면 TRUE로 설정됩니다. 교환은 각 정렬 패스가 ​​끝날 때 확인됩니다. 교환이 발생하지 않으면 알고리즘이 종료되고 다음 정렬 패스가 ​​수행되지 않습니다.

(2) 특정 알고리즘
void BubbleSort(SeqList R)
{ //R(l..n)은 정렬할 파일, 아래에서 위로 스캔, 버블 R 정렬
int i, j
불리언 교환; //교환 플래그
for(i=1;i exchange=FALSE ; /이 정렬이 시작되기 전에 교환 플래그가 false여야 합니다
for(j=n-1;j>=i;j--) //하단에서 현재 정렬되지 않은 영역 R[i..n]에 대해 Scan up
if(R[j+1].key R[0]=R[j+1] //R[0]이 아님 센티넬, 임시 저장 장치만
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE; the exchange 플래그가 true로 설정됩니다
}
if(!exchange) //이 정렬에서 교환이 발생하지 않습니다. 알고리즘을 조기에 종료합니다
/BubbleSort

버블정렬 알고리즘에 대한 더 많은 글은 PHP 중국어 홈페이지를 주목해주세요!