교환의 종류가 가장 많다는 것은 모두가 잘 알고 있습니다. 빠른 방법이른바 빠른 정렬. 이에 대한 논문이 작성되고 Habré에 대한 많은 기사가 이에 전념하며 복잡한 하이브리드 알고리즘이 이를 기반으로 발명됩니다. 그러나 오늘 우리는 그것에 대해 이야기하지 않습니다 퀵소트, 그러나 다른 교환 방법에 대해 - 좋은 오래된 버블 정렬및 개선, 수정, 돌연변이 및 품종.

이러한 방법의 실제 결과는 그다지 뜨겁지 않으며 많은 habrauser가 1학년 때 이 모든 것을 겪었습니다. 따라서 이 기사는 알고리즘 이론에 이제 막 관심을 갖고 이 방향으로 첫 걸음을 내딛는 사람들을 대상으로 합니다.

이미지: 거품

오늘 우리는 가장 간단한 것에 대해 이야기 할 것입니다 분류 교환.

관심있는 사람이 있으면 다른 수업이 있다고 말할 것입니다- 선택 정렬, 삽입 정렬, 병합 정렬, 정렬 분포, 하이브리드 정렬그리고 병렬 정렬. 그건 그렇고, 있습니다 난해한 분류. 이것들은 근본적으로 실현할 수 없는 다양한 가짜, 코믹 및 기타 의사 알고리즘이며, 이에 대해 IT 유머 허브에서 몇 가지 기사를 작성하겠습니다.

그러나 이것은 오늘의 강의와는 아무 상관이 없으며, 우리는 지금 단순 교환 정렬에만 관심이 있습니다. 자체 교환 종류도 꽤 있으므로(12개 이상 알고 있음) 소위 버블 정렬그리고 그와 밀접하게 관련된 일부 다른 사람들.

위의 거의 모든 방법은 매우 느리고 시간 복잡성에 대한 심층 분석이 없을 것임을 미리 경고합니다. 일부는 더 빠르고 일부는 더 느리지만 대략적으로 말하자면 평균적으로 다음과 같이 말할 수 있습니다. 영형(n 2). 또한 모든 프로그래밍 언어로 구현된 기사를 어지럽힐 이유가 없습니다. 관심 있는 사람들은 Rosetta, Wikipedia 또는 다른 곳에서 코드 예제를 쉽게 찾을 수 있습니다.

그러나 교환 분류로 돌아갑니다. 배열의 반복적인 순차적 열거와 요소 쌍을 서로 비교한 결과 정렬이 발생합니다. 비교된 요소가 서로 상대적으로 정렬되지 않은 경우 교환합니다. 유일한 질문은 어레이를 정확히 우회하는 방법과 비교를 위해 쌍을 선택하는 기준입니다.

참조 버블 정렬이 아니라 ...

어리석은 정렬

정렬은 정말 어리석은 일입니다. 배열을 왼쪽에서 오른쪽으로 살펴보고 그 과정에서 이웃을 비교합니다. 서로 정렬되지 않은 한 쌍의 요소를 만나면 이를 교환하고 1제곱, 즉 맨 처음으로 돌아갑니다. 우리는 배열을 다시 살펴보고 "잘못된" 인접 요소 쌍을 다시 만나면 장소를 바꾸고 처음부터 다시 시작합니다. 배열이 천천히 정렬될 때까지 계속합니다.

"그래서 모든 바보는 정렬 방법을 알고 있습니다"-당신은 말할 것이고 당신은 절대적으로 옳을 것입니다. 그래서 정렬을 "바보"라고 합니다. 이 강의에서 우리는 지속적으로 개선하고 수정할 것입니다. 이 방법. 이제 그는 시간 복잡도를 가지고 있습니다. 영형(3), 한 번 수정하면 이미 영형(n 2) 그런 다음 조금 더, 그 다음에는 조금 더 속도를 높이면 결국 영형(N통나무 N) - "빠른 정렬"이 전혀 되지 않습니다!

어리석은 정렬을 한 가지 개선해 보겠습니다. 통과하는 동안 정렬되지 않은 인접한 두 요소를 찾아 교체한 후 배열의 시작 부분으로 롤백하지 않고 침착하게 끝까지 순회를 계속할 것입니다.

이 경우 우리는 잘 알려진 것 외에는 아무것도 없습니다 ...

버블 정렬

또는 단순 교환으로 정렬. 장르의 불후의 명작. 동작 원리는 간단합니다. 배열을 처음부터 끝까지 이동하면서 정렬되지 않은 것을 동시에 교환합니다. 이웃 요소. 첫 번째 패스의 결과로 최대 요소가 마지막 위치까지 "팝업"됩니다. 이제 배열의 정렬되지 않은 부분을 다시 둘러보고(첫 번째 요소에서 끝에서 두 번째 요소까지) 정렬되지 않은 이웃을 변경합니다. 두 번째로 큰 요소는 끝에서 두 번째 위치에 있습니다. 계속해서 같은 정신으로 배열의 계속 감소하는 정렬되지 않은 부분을 우회하여 발견된 최대값을 끝까지 밀어 넣습니다.

최고점을 끝까지 밀어넣을 뿐만 아니라 최저점을 처음으로 이동하면 ...

셰이커 정렬

그녀는 셔플 정렬, 그녀는 칵테일 분류. 프로세스는 "거품"처럼 시작됩니다. 우리는 뒷마당까지 최대한으로 짜냅니다. 그 후, 우리는 180 0 주위를 돌고 반대 방향으로 이동하면서 이미 최대가 아니라 최소가 시작 부분으로 롤링합니다. 배열의 첫 번째 요소와 마지막 요소를 정렬한 후 다시 재주 넘기를 수행합니다. 몇 번이고 왔다 갔다 하다 결국 목록의 중간에 있는 과정을 끝내고 맙니다.

셰이커 정렬은 버블 정렬보다 약간 더 빠르게 작동합니다. 왜냐하면 고점과 저점이 어레이를 통해 올바른 방향으로 교대로 이동하기 때문입니다. 그들이 말했듯이 개선은 분명합니다.

보시다시피 반복 프로세스에 창의적으로 접근하면 무거운(가벼운) 요소를 배열의 끝으로 밀어 넣는 것이 더 빠릅니다. 따라서 장인들은 목록을 우회하기 위해 또 다른 비표준 "로드맵"을 제안했습니다.

짝수-홀수 정렬

이번에는 어레이를 앞뒤로 서두르지 않고 다시 왼쪽에서 오른쪽으로 체계적인 우회의 아이디어로 돌아가지만 더 넓은 단계를 밟을 뿐입니다. 첫 번째 패스에서 홀수 키가 있는 요소는 짝수 위치를 기준으로 이웃과 비교됩니다(1번째는 2번째와 비교한 다음 3번째는 4번째와, 5번째는 6번째와 비교 등). 그런 다음 그 반대의 경우도 마찬가지입니다. "짝수" 요소는 "홀수"와 비교/변경됩니다. 그런 다음 다시 "홀수-짝수", 다시 "짝수-홀수"입니다. 어레이를 두 번 연속으로 통과한 후("홀수-짝수" 및 "짝수-홀수") 교환이 발생하지 않으면 프로세스가 중지됩니다. 그래서 정리했습니다.

각 패스 중 일반적인 "거품"에서 배열의 끝까지 현재 최대값을 체계적으로 짜냅니다. 짝수 인덱스와 홀수 인덱스를 건너뛰면 배열의 더 많거나 적은 큰 요소가 동시에 한 번에 한 위치씩 오른쪽으로 밀려납니다. 그래야 더 빨라집니다.

마지막으로 분석해보자 보수* 을 위한 전구 분류** - 빗자루로 정렬***. 이 방법은 매우 빠르게 정리하고, 영형(n 2)는 최악의 복잡성입니다. 시간이 지남에 따라 평균적으로 영형(N통나무 N), 그리고 가장 좋은 것조차 믿지 마십시오. 영형(N). 즉, 재귀를 사용하지 않고 모든 "빠른 정렬"에 대한 매우 가치 있는 경쟁자입니다. 다만, 오늘은 순항 속도에 대해 깊게 파고들지 않기로 약속했기에 조용히 알고리즘으로 넘어가겠습니다.

다 거북이 탓이야

약간의 뒷이야기. 1980년 Włodzimierz Dobosiewicz는 버블 정렬과 파생 상품이 왜 그렇게 느린지 설명했습니다. 거북이에 관한 모든 것입니다.. "거북이"는 목록 끝에 있는 작은 항목입니다. 눈치채셨겠지만, 버블 정렬은 "토끼"(Babushkin의 "토끼"와 혼동하지 말 것)에 초점을 맞추고 있습니다. 즉, 목록 시작 부분의 값이 큰 요소입니다. 그들은 결승선을 향해 매우 활발하게 움직입니다. 그러나 느린 파충류는 마지못해 처음으로 기어갑니다. 다음을 사용하여 "또띠요"를 사용자 정의할 수 있습니다. 빗.

이미지: 유죄 거북이

빗 정렬

"bubble", "shaker" 및 "even-odd"에서 배열을 반복할 때 인접 요소가 비교됩니다. "빗"의 주요 아이디어는 처음에 충분히 취하는 것입니다 긴 거리비교된 요소 사이에서 배열이 정렬됨에 따라 이 거리를 최소로 좁힙니다. 따라서 우리는 배열을 빗질하여 점차적으로 점점 더 정확한 가닥으로 부드럽게합니다.

어쨌든 비교되는 요소들 사이의 초기 간격을 고려하는 것이 더 낫습니다. 감소 요인, 최적 값은 약 1.247입니다. 첫째, 요소 사이의 거리는 배열의 크기를 다음으로 나눈 값과 같습니다. 감소 계수(결과는 자연스럽게 가장 가까운 정수로 반올림됩니다). 그런 다음이 단계로 배열을 거친 후 단계를 다시 나눕니다. 감소 계수목록을 다시 살펴보십시오. 이것은 인덱스 차이가 1에 도달할 때까지 계속됩니다. 이 경우 배열은 일반 거품으로 다시 정렬됩니다.

최적의 값은 실험적, 이론적으로 설정되었습니다. 감소 계수:

이 방법이 발명되었을 때 70년대와 80년대로 접어들면서 이 방법에 주목한 사람은 거의 없었습니다. 10년 후, 프로그래밍이 많은 IBM 과학자와 엔지니어를 그만두고 이미 빠르게 대중적인 인기를 얻었을 때, 이 방법은 1991년 Stephen Lacey와 Richard Box에 의해 재발견, 연구 및 대중화되었습니다.

그것이 사실 제가 여러분에게 버블 정렬과 이와 유사한 다른 것들에 대해 말하고 싶은 전부입니다.

- 메모

* 단축( 우크라이나 인) - 개선
** 전구로 분류( 우크라이나 인) – 버블 정렬
*** 빗으로 정렬( 우크라이나 인) – 빗 정렬

중앙 집중식 컴퓨터가 데이터 정렬에 소비하는 시간의 최대 4분의 1이 소요되는 것으로 추정됩니다. 미리 정렬된 배열에서 값을 찾는 것이 훨씬 쉽기 때문입니다. 그렇지 않으면 검색은 건초 더미에서 바늘을 찾는 것과 같습니다.

정렬 알고리즘을 연구하고 구현하는 데 모든 작업 시간을 보내는 프로그래머가 있습니다. 이는 비즈니스 소프트웨어의 대부분이 데이터베이스 관리와 관련되기 때문입니다. 사람들은 항상 데이터베이스에서 정보를 찾습니다. 이것은 검색 알고리즘에 대한 수요가 높다는 것을 의미합니다.

그러나 하나의 "그러나"가 있습니다. 검색 알고리즘이미 정렬된 데이터베이스에서 훨씬 빠르게 작업합니다. 이 경우 선형 검색만 필요합니다.

컴퓨터에 사용자가 없는 경우도 있지만 정렬 알고리즘은 데이터베이스에서 계속 작동합니다. 다시 한 번, 검색자들이 들어오고 데이터베이스는 이미 하나의 검색 목표 또는 다른 목표에 따라 정렬되었습니다.

이 문서에서는 표준 정렬 알고리즘 구현의 예를 제공합니다.

선택 정렬

배열을 오름차순으로 정렬하려면 각 반복에서 가장 높은 가치. 그것으로 마지막 요소를 바꿔야합니다. 가장 높은 값을 가진 다음 요소가 끝에서 두 번째 요소가 됩니다. 이것은 배열의 첫 번째 위치에 있는 요소가 올바른 순서가 될 때까지 발생해야 합니다.

C++ 코드

무효 SortAlgo::selectionSort(int 데이터, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i 데이터[k])( j = k; ) ) tmp = 데이터[i]; 데이터[i] = 데이터[j]; 데이터[j] = tmp; ) )

버블 정렬

버블 정렬은 인접한 요소를 비교하고 다음 요소가 이전 요소보다 작으면 교체합니다. 데이터를 여러 번 통과해야 합니다. 첫 번째 패스 동안 배열의 처음 두 요소가 일치합니다. 순서가 맞지 않으면 교체되고 다음 쌍의 요소가 비교됩니다. 같은 조건에서 장소도 바꿉니다. 따라서 배열의 끝에 도달할 때까지 각 주기에서 정렬이 발생합니다.

C++ 코드

무효 SortAlgo::bubbleSort(int 데이터, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( if (데이터[j])

삽입 정렬

삽입 정렬은 배열을 정렬된 영역과 정렬되지 않은 영역으로 나눕니다. 처음에는 전체 배열이 순서가 지정되지 않은 영역입니다. 첫 번째 패스에서 정렬되지 않은 영역의 첫 번째 요소가 제거되고 정렬된 영역의 올바른 위치에 배치됩니다.

각 패스에서 정렬된 영역의 크기는 1씩 증가하고 정렬되지 않은 영역의 크기는 1씩 줄어듭니다.

메인 루프는 1에서 N-1까지의 범위에서 실행됩니다. j번째 반복에서 요소 [i]는 정렬된 영역의 올바른 위치에 삽입됩니다. 이것은 [i]보다 한 위치 더 큰 정렬된 영역의 모든 요소를 ​​오른쪽으로 이동하여 수행됩니다. [i]보다 작은 요소와 [i]보다 큰 요소 사이의 간격에 [i]가 삽입됩니다.

C++ 코드

무효 SortAlgo::insertionSort(int 데이터, int lenD) ( int 키 = 0; int i = 0; for (int j = 1; j =0 && 데이터[i]>키)( 데이터 = 데이터[i]; i = i-1; 데이터=키; ) ) )

병합 정렬

C++ 코드

void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int ; int * R = new int ; for ( 정수 나는 = 0; 나는

빠른 정렬

Quicksort는 분할 정복 알고리즘을 사용합니다. 원래 배열을 두 영역으로 분할하는 것으로 시작합니다. 이 부분은 피벗이라고 하는 표시된 요소의 왼쪽과 오른쪽에 있습니다. 프로세스가 끝나면 한 부분에는 피벗보다 작은 요소가 포함되고 다른 부분에는 피벗보다 큰 요소가 포함됩니다.

C++ 코드

void SortAlgo::quickSort(int * 데이터, int const len) ( int const lenD = len, int 피벗 = 0, int ind = lenD/2, int i,j = 0,k = 0, if (lenD>1) ( int * L = new int ; int * R = new int ; 피벗 = 데이터; for (i=0;i

안녕하세요 여러분!

오늘 우리는 "거품" 방법으로 정렬을 분석할 것입니다. 이 알고리즘은 종종 학교와 대학에서 전달되므로 Pascal 언어를 사용합니다. 그렇다면 정렬이란 무엇일까요? 정렬은 가장 작은 것에서 가장 큰 것(오름차순 정렬) 또는 가장 큰 것에서 가장 작은 것(내림차순)으로 요소를 정렬하는 것입니다. 배열은 일반적으로 정렬됩니다.

다양한 정렬 알고리즘이 있습니다. 일부는 많은 수의 항목을 분류하는 데 능숙하고 다른 일부는 매우 적은 수의 항목에서 더 효율적입니다. 우리의 버블 방식은 다음과 같은 특징이 있습니다.

장점:

• 알고리즘 구현 용이성
• 아름다운 이름

빼기:

• 가장 느린 정렬 방법 중 하나(실행 시간은 배열 n 2의 길이에 2차적으로 종속됨)
• 실생활에서 거의 사용되지 않음(주로 교육용으로 사용됨)

배열이 있다고 가정해 보겠습니다. 3 1 4 2

연산: 배열 요소를 가져와 다음 요소와 비교하고 요소가 다음 요소보다 크면 교환합니다. 전체 배열을 살펴본 후 최대 요소가 "팝업"되고 가장 마지막 요소가 될 것임을 확신할 수 있습니다. 따라서 우리는 이미 그 자리에 정확히 하나의 요소를 가지고 있습니다. 왜냐하면 우리는 그것들을 모두 제자리에 넣어야 하므로 배열 요소에서 1을 뺀 횟수만큼 이 작업을 반복해야 합니다. 나머지 요소가 제자리에 있으면 마지막 요소가 자동으로 나타납니다.

배열로 돌아가자: 3 1 4 2
첫 번째 요소 "3"을 가져와 다음 "1"과 비교합니다. 왜냐하면 "3" > "1", 다음으로 바꿉니다.
1 3 4 2
이제 "3"과 "4"를 비교합니다. 3은 4를 넘지 않으므로 아무 것도 하지 않습니다. 다음으로 "4"와 "2"를 비교합니다. 4는 2보다 크므로 자리를 바꿉니다: 1 3 2 4. 주기가 끝났습니다. 따라서 가장 큰 요소는 이미 그 자리에 있어야 합니다!! 우리는 이것이 일어난 것을 봅니다. "4"(가장 큰 요소)가 있는 곳마다 - 전체 배열을 반복한 후에도 여전히 마지막 요소입니다. 유추 - 공기 방울이 물에 뜨는 것처럼 - 따라서 우리 요소는 배열에 떠 있습니다. 따라서 알고리즘을 "버블 정렬"이라고 합니다. 다음 요소를 배치하려면 주기를 다시 시작해야 하지만 마지막 요소는 제자리에 있기 때문에 더 이상 고려할 수 없습니다.

"1"과 "3"을 비교합니다. 아무것도 변경하지 않습니다.
"3"과 "2" 비교 - 3은 둘 이상이므로 자리를 바꿉니다. 1 2 3 4가 나옵니다. 두 번째 사이클이 완료되었습니다. 우리는 이미 두 개의 사이클을 수행했습니다. 즉, 마지막 두 요소가 이미 정렬되어 있다고 자신 있게 말할 수 있습니다. 세 번째 요소를 정렬하는 것은 우리에게 남아 있으며 네 번째 요소는 자동으로 올바른 위치에 놓입니다. 다시 한 번, 첫 번째 요소와 두 번째 요소를 비교합니다. 이미 모든 것이 제자리에 있음을 알 수 있습니다. 즉, 배열이 요소의 오름차순으로 정렬된 것으로 간주될 수 있습니다.

이제 이 알고리즘을 파스칼로 프로그래밍하는 일만 남았습니다. 상수 n = 4; (상수를 시작하면 배열의 길이가 됩니다.) var i, j, k:integer; (중첩 루프용 변수 2개, 요소 교환용 변수 1개) m: 정수 배열; (배열 생성) begin (키보드에서 배열을 요청할 것입니다:) Writeln("배열을 입력하세요:"); i:=1에서 n에 대해 Writeln(i, " element:")을 시작합니다. readln(m[i]); 끝; (외부 루프는 배열 요소에서 1을 뺀 횟수만큼 내부 루프를 반복해야 한다는 사실에 대한 책임이 있습니다.) for i:=1 to n-1 do begin (내부 루프는 이미 요소를 반복하고 비교합니다. 서로 함께.) for j :=1 to n-i do begin (요소가 다음 것보다 크면 교환합니다.) if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; 끝; 끝; 끝; (출력 결과:) for i:=1 to n do Write(m[i], " "); 끝.
결과는 다음과 같습니다.

그리고 여기 비디오 튜토리얼이 있습니다

데이터 배열로 작업할 때 다음을 수행하는 것은 드문 일이 아닙니다. 오름차순 또는 내림차순 정렬, 즉 합리화. 이는 동일한 배열의 요소가 순서대로 엄격하게 배열되어야 함을 의미합니다. 예를 들어, 오름차순으로 정렬하는 경우 선행 요소는 후속 요소보다 작거나 같아야 합니다.

해결책

많은 정렬 방법이 있습니다. 그들 중 일부는 더 효율적이고 다른 일부는 이해하기 쉽습니다. 이해하기 쉬운 것은 정렬입니다. 버블 방식, 라고도 합니다. 간단한 교환 방법. 그것은 무엇이며 왜 "거품 방법"이라는 이상한 이름을 가지고 있습니까?

아시다시피 공기는 물보다 가볍기 때문에 기포가 떠 있습니다. 그냥 비유입니다. 오름차순 버블 정렬에서 더 가벼운(낮은 값) 요소는 배열의 시작 부분으로 점차 "떠오릅니다". 반면 무거운 요소는 하나씩 아래쪽(배열의 끝으로)으로 가라앉습니다.

이러한 종류의 알고리즘과 기능은 다음과 같습니다.

1. 배열을 통한 첫 번째 통과 동안 요소는 쌍으로 비교됩니다. 첫 번째와 두 번째, 두 번째와 세 번째, 세 번째와 네 번째, 이런 식으로 계속됩니다. 이전 요소가 다음 요소보다 크면 교체됩니다.
2. 점차적으로 가장 큰 숫자가 마지막이라고 추측하는 것은 어렵지 않습니다. 배열의 시작 부분으로 더 낮은 값을 가진 요소의 일부 이동이 있지만 나머지 배열은 정렬되지 않은 상태로 유지됩니다.
3. 두 번째 패스에서는 마지막 요소와 끝에서 두 번째 요소를 비교할 필요가 없습니다. 마지막 요소가 이미 있습니다. 즉, 비교 횟수가 하나 줄어듭니다.
4. 세 번째 패스에서는 끝에서 두 번째 요소와 세 번째 요소를 비교할 필요가 없습니다. 따라서 비교 횟수는 첫 번째 패스보다 2개 적습니다.
5. 결국 배열을 반복할 때 비교할 요소가 두 개뿐일 때 한 번만 비교가 수행됩니다.
6. 그 후 첫 번째 요소는 비교할 대상이 없으므로 배열을 통한 마지막 전달이 필요하지 않습니다. 즉, 배열을 통과하는 횟수는 m-1이며, 여기서 m은 배열 요소의 개수입니다.
7. 각 패스의 비교 횟수는 m-i이며, 여기서 i는 배열 패스 번호(첫 번째, 두 번째, 세 번째 등)입니다.
8. 배열 요소를 교환할 때 일반적으로 요소 중 하나의 값이 임시로 배치되는 "버퍼"(세 번째) 변수가 사용됩니다.

파스칼 프로그램:

상수 m = 10 ; var arr: 정수 배열 [ 1 .. m ] ; i, j, k: 정수 ; 무작위 시작; 쓰다( "소스 배열: ") ; for i : = 1 to m do begin arr[ i] : = random(256 ) ; 쓰기 (arr[ i] : 4 ) ; 끝 ; 쓰기 ; 쓰기 ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] := arr[ j+ 1 ] ; arr[ j+ 1 ] : = k 끝 ; 쓰다( "정렬된 배열: ") ; for i := 1 to m do write (arr[ i] : 4 ) ; 쓰기 ; 읽기 끝 .

배열을 위에서 아래로, 0 요소에서 마지막 요소까지 배열해 보겠습니다.

방법의 아이디어: 정렬 단계는 배열을 통해 아래에서 위로 이동하는 것으로 구성됩니다. 인접한 요소의 쌍은 도중에 살펴봅니다. 어떤 쌍의 요소가 잘못된 순서로 되어 있으면 교환합니다.

배열을 0으로 통과한 후 "가장 가벼운" 요소는 "위"에 있으므로 거품과 유사합니다. 다음 패스는 위에서 두 번째 요소로 구성되므로 두 번째로 큰 요소가 올바른 위치로 들어 올려집니다...

배열의 요소가 하나만 남을 때까지 계속 감소하는 배열의 아래쪽 부분을 따라 이동합니다. 순서가 오름차순으로 정렬되기 때문에 정렬이 끝나는 곳입니다.

주형 void bubbleSort(T a, 긴 크기) ( 긴 i, j; T x; for(i=0; i)< size; i++) { // i - 패스 번호 for(j = 크기-1, j > i, j--) ( // 내부 패스 루프 if (a > a[j]) ( x=a; a=a[j]; a[j]=x; ) ) ) )

평균 비교 및 ​​교환 횟수는 2차 성장 차수를 갖습니다. 즉, Theta(n 2), 따라서 버블 알고리즘이 매우 느리고 비효율적이라는 결론을 내릴 수 있습니다.
그러나 그것은 큰 장점이 있습니다. 간단하고 어떤 식으로든 개선할 수 있습니다. 이젠 어떻게 할거야.

먼저 어떤 패스에서도 교환이 발생하지 않은 상황을 고려하십시오. 무슨 뜻인가요?

이것은 모든 쌍이 올바른 순서로 되어 있으므로 배열이 이미 정렬되어 있음을 의미합니다. 그리고 프로세스를 계속하는 것은 의미가 없습니다(특히 배열이 처음부터 정렬된 경우).

따라서 알고리즘의 첫 번째 개선 사항은 주어진 패스에서 교환이 이루어졌는지 여부를 기억하는 것입니다. 그렇지 않으면 알고리즘이 종료됩니다.

거래소 자체의 사실 뿐만 아니라 지난 거래소의 지수 k를 기억한다면 개선 과정을 계속할 수 있다. 실제로: k보다 작은 인덱스를 가진 모든 인접 요소 쌍은 이미 필요한 순서에 있습니다. 추가 패스는 사전 설정된 상한 i까지 이동하는 대신 인덱스 k에서 끝날 수 있습니다.

알고리즘의 질적으로 다른 개선은 다음 관찰에서 얻을 수 있습니다. 아래에서 가벼운 기포는 한 번에 위로 올라가지만 무거운 기포는 반복당 최소 한 단계의 비율로 하강합니다. 따라서 배열 2 3 4 5 6 1 은 1 패스로 정렬되는 반면 시퀀스 6 1 2 3 4 5 를 정렬하려면 5 패스가 필요합니다.

이 효과를 피하기 위해 연속 패스의 방향을 변경할 수 있습니다. 결과 알고리즘은 때때로 " 셰이커 정렬".

주형 void shakerSort(T a, 긴 크기) ( 긴 j, k = 크기-1, 긴 lb=1, ub = 크기-1, // 배열의 정렬되지 않은 부분의 경계송신; 하다( // 아래에서 위로 전달 for(j=ub; j>0; j--) ( if (a > a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) lb =k+1; // 위에서 아래로 전달(j=1; j에 대해<=ub; j++) { if (a >a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) ub = k-1; ) 동안 (파운드< ub); }

설명된 변경 사항이 방법의 효율성에 어느 정도 영향을 미쳤습니까? 평균 비교 횟수는 감소했지만 여전히 O(n 2)인 반면 교환 횟수는 전혀 변하지 않았습니다. 평균(최악이기도 함) 연산 수는 2차로 유지됩니다.

추가 메모리는 분명히 필요하지 않습니다. 개선된(초기가 아닌) 메서드의 동작은 매우 자연스럽습니다. 거의 정렬된 배열은 임의의 배열보다 훨씬 빠르게 정렬됩니다. 버블 정렬은 안정적이지만 셰이커 정렬은 이 품질을 잃습니다.

실제로, 버블 방법은 개선이 있더라도 불행히도 너무 느립니다. 따라서 거의 사용되지 않습니다.