다른 버블 정렬 알고리즘 코드 - 차이점은 무엇입니까? C++

Question

저는 C++에서 버블 정렬 알고리즘의 많은 다른 구현을 접했습니다. 다른 사람이 나에게 차이점을 말할 수 있도록 몇 가지를 나열 할 것입니다. 나는 while 루프를 사용하는 것을 보았습니다.하지만 약간 다릅니다.하지만 배열을 통과하는 라인은 여전히 ​​동일합니다.

코드의 이러한 예는 for 루프를 사용하여 배열을 통과하는 코드의 예입니다.

예 1 :

for (int i=0; i<size-1); i++) 
    for (int j=i+1; j<size; j++) 
    //swap lines 

예 2 :

for (int j=0; j<(size-1); j++) 
    //swap lines 

그래서 차이점은 무엇입니까? 두 번째 것은 매번 전체 배열을 통과하며, 첫 번째 배열은 매번 1보다 작아집니다. 알고리즘이 배열을 통과하여 배열을 교체하고 배열의 첫 번째 요소로 다시 돌아갈 필요가 없다는 것을 알고 있으므로 첫 번째 요소가 더 낫다고 추측하고 있습니다.

또한 C++에서 Bubble 정렬을 가장 잘 구현하는 방법은 무엇입니까? 가능한 경우 코드를 포함 시키십시오.

Answer 1

버블 정렬은 O (n^2)이므로 예제 1과 같이 항상 중첩 루프가 있거나 이와 동등한 다른 루프가 있습니다. 예제 2는 동일한 목적을 달성하기 위해 다른 재구성, 아마도 재귀를 사용합니다.

최선의 구현이 하나도 없을 것입니다. 서로 다른 구현은 다른 방식으로 더 좋습니다. 버블 정렬은 정렬 된 순서에 가까운 목록에서 빠르게 실행되는 정렬을 사용하기도합니다. 이 속성을 이용하는 버전은 순서가 지정된 목록에서 훨씬 빠르게 실행되지만 완전히 무작위 인 목록에서 조금 느리게 실행됩니다.