버블 정렬 알고리즘

버블 정렬은 주어진 요소는 n 개수의 요소가있는 배열 형식으로 제공됩니다. 버블 정렬은 모든 요소를 하나씩 비교하고 해당 값을 기준으로 정렬합니다.

주어진 배열을 오름차순으로 정렬해야하는 경우 배열의 첫 번째 요소를 비교하여 버블 정렬이 시작됩니다. 두 번째 요소, 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 교체 한 다음 두 번째 요소와 세 번째 요소를 비교하는 식으로 진행됩니다.

총계가있는 경우 n 요소가있는 경우이 프로세스를 n-1 번 반복해야합니다.

버블 정렬이라고합니다. 모든 완전한 반복을 수행 할 때마다 주어진 배열에서 가장 큰 요소가 마지막 위치 또는 가장 높은 인덱스를 향해 거품이 발생하기 때문입니다. 마치 물 거품이 수면 위로 올라 오는 것처럼 정렬이 이루어집니다.

모두를 단계별로 실행하여 정렬합니다. 요소를 하나씩 비교하고 인접 요소와 비교하고 필요한 경우 교체합니다.

참고 : 데이터 구조의 정렬에 익숙하지 않은 경우 먼저 정렬의 기본 사항을 알기 위해 정렬이 무엇인지 알아 봅니다.

버블 정렬 알고리즘 구현

다음은 버블 정렬과 관련된 단계입니다 (주어진 배열을 오름차순으로 정렬).

값 {5, 1, 6, 2, 4, 3}

아래에는 버블 정렬이 주어진 배열을 정렬하는 방법에 대한 그림 표현.

위 표현에서 볼 수 있듯이 첫 번째 반복에서는 6가 올바른 위치 인 마지막 색인에 배치됩니다.

두 번째 반복 이후와 유사하게 5는 마지막 두 번째 인덱스에 위치합니다.

코드 작성 시간 버블 정렬의 경우 :

위의 로직이 정렬되지 않은 배열을 정렬하지만 위의 로직에 따라 외부 for 루프는 두 번째 반복 후에 배열이 정렬 되더라도 6 개의 반복 동안 계속 실행됩니다.

따라서 알고리즘을 명확하게 최적화 할 수 있습니다.

버브 최적화 정렬 알고리즘을 사용하면 flag를 도입하여 요소가 내부 for 루프 내부에서 교체되는지 여부를 모니터링 할 수 있습니다.

따라서 내부 for 루프에서 매번 요소 교체가 발생하는지 여부를 확인합니다.

특정 반복에 대해 교체가 필요하지 않은 경우 여기서는 배열이 정렬되었고 모든 반복을 실행하는 대신 for 루프에서 벗어날 수 있음을 의미합니다.

배열을 고려해 보겠습니다. 값 {11, 17, 18, 26, 23}

아래에는 최적화 된 버블 정렬이 주어진 배열을 정렬하는 방법에 대한 그림 표현이 있습니다.

보시다시피 첫 번째 반복에서 스왑이 발생 했으므로 flag 값을 1 결과적으로 실행은 다시 for 루프에 들어갑니다. 그러나 두 번째 반복에서는 스왑이 발생하지 않으므로 flag의 값은 0로 유지되고 실행이 루프를 벗어납니다.

위 코드에서 bubbleSort 함수에서 j 반복의 단일 전체주기 (내부 for 루프), 스왑이 발생하지 않은 다음 flag는 0로 유지되고 배열이 이미 정렬되었으므로 for 루프에서 나갑니다.

버블 정렬에서 n-1 비교는 첫 번째 패스 인 n-2 두 번째 패스, n-3 세 번째 패스 등입니다. 따라서 총 비교 수는

(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)

따라서 버블 정렬의 시간 복잡도는 O (n2)입니다.

버블 정렬의 가장 큰 장점은 알고리즘의 단순성입니다.

버블 정렬의 공간 복잡성은 O (1)입니다. 그 이유는 temp 변수에 대해 하나의 추가 메모리 공간 만 필요하기 때문입니다.

또한 최상의 경우 시간 복잡도는 O (n)이며 목록이 이미 정렬 된 경우입니다.

다음은 버블 정렬 알고리즘의 시간 및 공간 복잡도입니다.

버블 정렬 알고리즘을 배웠으므로 이제 이러한 정렬 알고리즘과 그 응용 프로그램을 확인할 수 있습니다.