버블 정렬 인접한 요소의 순서가 잘못된 경우 반복적으로 교체하여 작동하는 가장 간단한 정렬 알고리즘 중 하나로 간주됩니다. 버블 정렬 알고리즘을 사용하면 가장 큰 요소 (가장 작은 요소에서 가장 큰 요소로 정렬한다고 가정)가 목록 또는 배열의 맨 위로 “버블 링”되는 것을 확인할 수 있습니다.

예 :
오름차순 (가장 작은 것부터 가장 큰 것까지)으로 목록 또는 요소 배열을 정렬하려고한다고 가정합니다. List = (3,1,2)

스왑 핑이 발생하지 않았으므로 배열이 이미 오름차순으로 정렬되었습니다!

Best Case

이제 동일한 알고리즘을 다시 시도해 보겠습니다.하지만 이번에는 요소가 이미 순서대로 정렬 된 최상의 시나리오 시나리오를 사용합니다. 오름차순) 우리는 원합니다.

스왑이 발생하지 않았으므로 알고리즘은 2 개의 비교 만 수행하고 배열의 요소 수를 n = 3이라고합니다. 따라서 n에 대해 알 수 있습니다. 이 알고리즘이 가장 좋은 요소는 n-1 비교 만 취합니다. n-1 = O (n)

우리가 사용한 절차 또는 알고리즘은 다음과 같습니다.

이 알고리즘은 플래그를 사용합니다. 요소가 교체되었는지 여부를 알려줍니다. , 버블 정렬의 다른 구현과 마찬가지로 버블 정렬 알고리즘이 O (n²) 대신 O (n)이 될 수 있습니다.

위의 알고리즘
Worst Case = O (n²)
Best Case = O (n)

버블 정렬 알고리즘의 다른 구현을 살펴 보겠습니다.

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

위 알고리즘
최악 사례 = O (n²)
최상 사례 = O (n²)

최악 사례

배열 또는 목록을 정렬합시다 = (3,2,1) 위의 알고리즘을 사용하여 목록이 원하는 순서 (오름차순)와 완전히 반대되는 최악의 경우입니다.

첫 번째 패스 :
(3,2,1)-> 요소 비교 3 & 2
(2,3 , 1)-> 2 개 이후 3 개 & 2 개 < 3 개
( 2,3,1)-> 요소 비교 3 & 1
(2,1,3)-> 1 교체 & 3 개 이후 1 개 < 3 개

두 번째 패스 :
(2,1,3)-> 요소 비교 2 & 1
(1,2,3)-> 2 교체 & 1 이후 1 < 2
(1,2,3)-> 요소 2 & 3
(1,2,3)-> 2 개 이후 스왑 필요 없음 < 3

이제 두 루프를 모두 반복하여 배열을 오름차순으로 정렬해야합니다.

위의 두 번째 예에서 4 번의 비교를 수행했습니다. 배열의 요소 수는 ‘n’= 3이므로 비교 횟수는 (n-1) ²이고 (n-1) ² = O (n²)

또한 코딩 / 프로그래밍 인터뷰를 준비 할 수있는 훌륭한 책을 코딩 인터뷰 크래킹이라고합니다. 정렬 알고리즘과 문제 해결에 익숙해지는 데 도움이되므로 반드시 확인하십시오!

이 기사를 읽어 주셔서 감사합니다. 여러분 모두에게 도움이 되었기를 바랍니다. 계속 학습하고 더 많은 알고리즘 분석 동영상을 원하시면 내 YouTube 채널 (randerson112358 & compsci112358)을 방문하여 구독하세요.

다음을 확인하세요. 알고리즘 분석 및 프로그래밍에 대한 추가 콘텐츠 / 동영상 :

YouTube 채널 :
randerson112358 : https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358 :

웹 사이트 :

재발 관계에 대한 비디오 자습서 :

알고리즘 분석에 대한 비디오 자습서 :

트위터 :