버블 정렬이란 무엇인가요?

버블 정렬은 컴퓨터 정렬 방법을 말하며 시간 복잡도는 O(n^2)이지만 힙 정렬이나 빠른 정렬의 O(nlogn, base 2)만큼 좋지는 않습니다. 두 가지 장점이 있습니다: 1. "프로그래밍 복잡도"가 매우 낮고 코드 작성이 쉽습니다. 2. 여기서 안정성이 있다는 것은 원래 시퀀스에서 동일한 요소의 상대적 순서가 여전히 유지된다는 것을 의미합니다. 힙 정렬이나 퀵 정렬 모두 안정적이지 않습니다. 그러나 단방향, 양방향 병합 정렬 및 불균형 이진 트리 정렬은 버블 정렬보다 빠르고 안정적이지만 힙 정렬 및 퀵 정렬만큼 빠르지는 않습니다. n-1개의 하위 정렬을 통해 버블 정렬이 완료됩니다. i번째 하위 정렬은 i번째 숫자가 다음 숫자보다 큰 경우(오름차순, 작은 경우)입니다. , 내림차순), 두 숫자 교환

버블 정렬(BubbleSort)의 기본 개념은 인접한 두 숫자를 순서대로 비교하여 소수점을 앞에 놓고 큰 숫자를 뒤에 두는 것입니다. 즉, 첫 번째 단계에서는 먼저 첫 번째 숫자와 두 번째 숫자를 비교하고 소수점을 먼저 배치하고 큰 숫자를 마지막에 배치합니다. 그런 다음 두 번째 숫자와 세 번째 숫자를 비교하고 소수를 앞에 놓고 큰 숫자를 뒤에 놓고 마지막 두 숫자를 비교할 때까지 이렇게 계속하여 소수를 앞에 놓고 큰 숫자를 뒤에 넣습니다. 이것이 첫 번째 여행의 끝이며, 끝에 가장 큰 숫자가 남습니다. 두 번째 단계에서는 여전히 첫 번째 숫자 쌍에서 비교를 시작합니다(두 번째 숫자와 세 번째 숫자의 교환으로 인해 첫 번째 숫자가 더 이상 두 번째 숫자보다 작지 않기 때문일 수 있음). 소수점을 먼저 입력합니다. , 그리고 큰 숫자를 배치한 후 두 번째에서 마지막 숫자까지 비교가 계속됩니다(첫 번째에서 마지막 위치가 이미 가장 큰 숫자임). 두 번째 패스가 끝나면 두 번째에서 마지막까지 새로운 최대 숫자가 얻어집니다. 위치(실제로는 전체 시퀀스에서 두 번째로 큰 숫자입니다). 이렇게 계속해서 정렬이 최종적으로 완료될 때까지 위의 과정을 반복하세요. 정렬 과정에서는 항상 작은 숫자가 앞쪽에 배치되고 큰 숫자가 뒤쪽에 배치되는데, 이는 거품이 떠오르는 것과 동일하므로 이를 버블 정렬이라고 합니다. 이중 루프로 구현되면 외부 루프 변수는 i로 설정되고 내부 루프 변수는 j로 설정됩니다. 외부 루프는 9번 반복되고, 내부 루프는 9, 8,..., 1번 순서대로 반복됩니다. 매번 비교되는 두 요소는 내부 루프 j와 관련되어 있으며 각각 a[j] 및 a[j 1]로 식별할 수 있습니다. i의 값은 1, 2,..., 9입니다. 각각에 대해 i와 j의 값은 1, 2,...10-i입니다.

생성

많은 프로그래밍에서 통계를 용이하게 하기 위해 순서를 정렬해야 하는데, 버블 정렬은 간결한 사고 방식으로 인해 항상 인기가 있었습니다.

정렬 과정

정렬된 배열 R[1..N]이 수직으로 세워지고 각 데이터 요소가 가벼운 버블에 따라 가중치가 부여된 버블로 간주된다고 상상해 보세요. 무거운 버블에서는 아래 원리에 따라 배열 R이 아래에서 위로 스캔됩니다. 이 원리를 위반하는 가벼운 버블이 스캔될 때마다 이는 마지막 두 개의 버블이 위로 떠오를 때까지 반복됩니다. 다음 번에는 위쪽이 더 가볍고 더 무겁습니다.