추천, 2024

에디터의 선택

버블 정렬과 선택 정렬의 차이점

정렬은 배열의 요소가 특정 순서로 배열되는 컴퓨터 프로그램의 주요 작업 중 하나입니다. 정렬을하면 검색이 쉬워집니다. 버블 정렬 및 선택 정렬은 정렬에 사용되는 메서드를 통해 구분할 수있는 정렬 알고리즘입니다. 버블 정렬은 기본적으로 요소를 교환하지만 선택 정렬은 요소를 선택하여 정렬을 수행합니다.

둘 사이의 또 다른 중요한 차이점은 버블 정렬은 안정적인 알고리즘이고 선택 정렬은 불안정한 알고리즘이라는 것입니다. 알고리즘은 목록이나 배열에서 정렬하기 전에 발생하는 동일한 순서로 동일한 키가있는 요소가 안정적이라고 간주됩니다. 일반적으로 가장 안정적이고 빠른 알고리즘은 추가 메모리를 사용합니다.

비교 차트

비교 근거버블 정렬
선택 정렬
기본인접한 요소를 비교하고 바꿉니다.가장 큰 요소가 선택되고 마지막 요소와 교환됩니다 (오름차순의 경우).
최상의 케이스 시간 복잡성에)O (n2)
능률무능한버블 정렬에 비해 향상된 효율성
안정된아니
방법교환선택
속도느린버블 정렬에 비해 빠름

버블 정렬의 정의

버블 정렬 은 각 항목 또는 요소를 옆에있는 항목과 비교하고 필요할 경우 바꾸는 간단한 반복 알고리즘입니다. 간단히 말해 목록의 첫 번째 요소와 두 번째 요소를 비교하고 특정 순서를 벗어나지 않는 한이를 바꿉니다. 마찬가지로, 두 번째와 세 번째 요소가 비교되고 교체되며, 이 비교 및 ​​교체는 목록의 끝으로 이동합니다. 첫 번째 반복의 비교 횟수는 n-1입니다. 여기서 n은 배열의 숫자 요소입니다. 가장 큰 요소는 첫 번째 반복 이후 n 번째 위치에 있습니다. 그리고 매 반복 후에, 비교의 수는 감소하고 마지막 반복에서 단지 하나의 비교가 일어난다.

이 알고리즘은 가장 느린 정렬 알고리즘입니다. Bubble 정렬의 가장 좋은 경우 복잡성 (순서가 순서 인 경우)은 순서 n ( O (n) )이고 최악 경우 복잡도는 O (n2) 입니다. 가장 좋은 경우에는 요소를 비교하고이를 교환하지 않기 때문에 순서가 n입니다. 이 기술은 또한 임시 변수를 저장하기위한 추가 공간이 필요합니다.

선택의 정의 정렬

선택 정렬 은 약간 더 나은 성능을 달성했으며 버블 정렬 알고리즘보다 효율적입니다. 오름차순으로 배열을 배열하고, 가장 큰 요소를 찾아서 마지막 요소와 교환하고 전체 목록이 정렬 될 때까지 하위 배열에서 다음 프로세스를 반복하여 기능을한다고 가정 해보십시오.

선택 정렬에서 정렬 및 정렬되지 않은 배열은 차이를 만들지 않으며 최상 및 최악의 경우 모두 n2 ( O (n2) )의 차수를 사용합니다. 선택 정렬은 거품 정렬보다 빠릅니다.

버블 정렬과 선택 정렬의 주요 차이점

  1. 버블 정렬에서 각 요소와 그 인접 요소는 필요한 경우 비교되고 교체됩니다. 반면에 선택 정렬은 요소를 선택하고 해당 요소를 마지막 요소와 바꿔서 작동합니다. 선택한 요소는 오름차순 또는 내림차순에 따라 최대 또는 최소가 될 수 있습니다.
  2. 최악의 경우의 복잡도는 두 알고리즘 모두에서 동일합니다 (예 : O (n2)). 그러나 가장 좋은 복잡성은 다릅니다. 버블 정렬은 n 시간의 순서를 취하고 선택 정렬은 n2 시간의 순서를 소비합니다.
  3. 버블 정렬은 안정적인 알고리즘이지만, 선택 정렬은 불안정합니다.
  4. 선택 정렬 알고리즘은 매우 느리고 비효율적 인 버블 정렬과 비교하여 빠르고 효율적입니다.

결론

버블 정렬 알고리즘은 가장 간단하고 비효율적 인 알고리즘으로 간주되지만 선택 정렬 알고리즘은 버블 정렬에 비해 효율적입니다. 버블 정렬은 임시 변수를 저장하기위한 추가 공간을 소비하므로 더 많은 스왑이 필요합니다.

Top