C++의 버블 정렬 구현

Question

아래 코드는 버블 정렬을 구현하는 데 사용됩니다. 이 경우 템플릿이 사용되는 이유는 무엇입니까? 그리고 swapped variabe의 목적은 무엇입니까? 내가 루프 코드에서 변수 swapped 및 swapped condition를 제거하더라도 여전히 잘

#include <algorithm> 
#include <iostream> 
#include <iterator> 

template <typename RandomAccessIterator> 
void bubble_sort(RandomAccessIterator begin, RandomAccessIterator end) { 
    bool swapped = true; 
    while (begin != end-- && swapped) { 
    swapped = false; 
    for (auto i = begin; i != end; ++i) { 
     if (*(i + 1) < *i) { 
     std::iter_swap(i, i + 1); 
     swapped = true; 
     } 
    } 
    } 
} 

int main() { 
    int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199}; 
    bubble_sort(std::begin(a), std::end(a)); 
    copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
} 

다른 구현을 작동합니다

template<typename Iterator> 
void bubbleSort(Iterator first, Iterator last) 
{ 
    Iterator i, j; 
    for (i = first; i != last; i++) 
     for (j = first; j < i; j++) 
      if (*i < *j) 
       std::iter_swap(i, j); // or std::swap(*i, *j); 
} 

Answer 1

다른 컨테이너에는 고유 한 반복기 유형이 있습니다. 예를 들어 1 차원 배열의 경우 포인터를 반복자로 사용하고 std :: vector 유형의 객체의 경우이 템플릿 클래스에 정의 된 반복자를 사용합니다.

변수가 이미 정렬되어 있는지 여부를 기준으로 변수 swapped이 사용됩니다. 순회 중의 요소의 교환이 없었던 경우, 순서가 벌써 소트되고있는 것을 의미합니다. 범위가 비어있을 때 마지막 반복자를 감소하려는 시도가 있기 때문에

때문에이 문장

while (begin != end-- && swapped) { 
       ^^^^ 

에 당신이 보여준 구현 행동을 정의되지 않은 것을 고려. 따라서 구현이 잘못되었습니다.

또한 알고리즘이 효율적이지 않습니다. 예를 들어 배열의 꼬리는 이미 내부 루프의 반복 후에 정렬 될 수 있습니다. 그러나 외부 루프에서는 마지막 반복기가 한 위치에서만 왼쪽으로 이동합니다.

버블 정렬에 포워드 이터레이터를 사용하면 충분합니다. 이 경우 std::forward_list 및 임의 액세스 반복기가없는 다른 컨테이너와 함께 알고리즘을 사용할 수 있습니다.

다음은 순방향 반복기를 사용하여 알고리즘을 구현하는 방법을 보여주는 데모 프로그램입니다.

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <forward_list> 

template <typename ForwardIterator> 
void bubble_sort(ForwardIterator first, ForwardIterator last) 
{ 
    for (ForwardIterator sorted = first; first != last; last = sorted) 
    { 
     sorted = first; 
     for (ForwardIterator current = first, prev = first; ++current != last; ++prev) 
     { 
      if (*current < *prev) 
      { 
       std::iter_swap(current, prev); 
       sorted = current; 
      } 
     } 
    } 
} 

int main() 
{ 
    int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 }; 

    bubble_sort(std::begin(a), std::end(a)); 
    std::copy(std::begin(a), std::end(a), 
       std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 

    std::forward_list<int> lst = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 }; 

    bubble_sort(std::begin(lst), std::end(lst)); 
    std::copy(std::begin(lst), std::end(lst), 
       std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
} 

프로그램 출력 프로그램 배열 및 유형 std::forward_list의 개체가 사용되며, 알고리즘은 두 용기에 적용 할 수

-199 -52 2 3 33 56 99 100 177 200 
-199 -52 2 3 33 56 99 100 177 200 

여기에있다.

Answer 2

템플릿은 서로 다른 유형의 기능을 사용 편의를 위해 단순히있다. 간단한 배열이 아닌 반복자를 사용하는 함수를 구현하면 포인터와 크기에 많은 문제가 발생하지 않습니다.

swapped 변수는 begin에서 end까지의 마지막 실행이 스왑을 초래하지 않았다는 것을 알고리즘에 알립니다. 이것은 배열이 이미이 범위로 정렬되어 있다는 것을 의미하며 (이전 패스에서 처리 된 것이기 때문에 end 이후로 정렬 됨) 반복자가 begin과 end 반복자가 동일 할 때까지 반복 할 필요가 없습니다. 이 검사를 제거하면 알고리즘이 작동하지만 부분 정렬 된 배열의 경우 시간 낭비가 발생할 수 있습니다. 당신은 0: 후 배열이 이미 정렬되어 있음을 알 수

0: {1 2 5 3 4} (begin = 0, end = 4) 
1: {1 2 3 4 5} (begin = 0, end = 3) 
2: {1 2 3 4 5} (begin = 0, end = 2) 
3: {1 2 3 4 5} (begin = 0, end = 1) 
4: {1 2 3 4 5} (begin = 0, end = 0) 

을하지만, swapped 플래그없이 알고리즘은 휴식과 검사를 계속할 것 :

의이 예를 살펴 보자. 1: 다음에 플래그가 있으면 swapped 플래그가 false이고 알고리즘이 종료됩니다.