버블정렬

버블 정렬은 배열을 여러 단계로 정렬합니다. 각 패스는 요소의 순서가 맞지 않으면 인접 요소를 연속적으로 교체합니다. 버블 정렬 알고리즘은 배열을 여러 번 통과합니다. 각 패스에서 연속적인 이웃 쌍이 비교됩니다. 쌍이 내림차순이면 해당 값이 교환됩니다. 그렇지 않으면 값이 변경되지 않고 유지됩니다. 이 기술을 버블 정렬 또는 싱킹 정렬이라고 합니다. 작은 값은 점차적으로 위로 올라가고 큰 값은 아래로 가라앉기 때문입니다. 첫 번째 패스 후에는 마지막 요소가 배열에서 가장 큰 요소가 됩니다. 두 번째 패스 후에는 마지막에서 두 번째 요소가 배열에서 두 번째로 큰 요소가 됩니다. 이 과정은 모든 요소가 정렬될 때까지 계속됩니다.

아래 그림(a)은 6개 요소 배열(2 9 5 4 8 1)에 대한 버블 정렬의 첫 번째 단계를 보여줍니다. 첫 번째 쌍(2와 9)의 요소를 비교하면 이미 순서가 있으므로 교체가 필요하지 않습니다. 두 번째 쌍(9와 5)의 요소를 비교하고 9가 5보다 크므로 9를 5로 바꿉니다. 세 번째 쌍(9와 4)의 요소를 비교하고 9를 4로 바꿉니다. 네 번째 쌍의 요소를 비교합니다. 쌍(9와 8), 그리고 9를 8로 바꿉니다. 다섯 번째 쌍(9와 1)의 요소를 비교하고 9를 1로 바꿉니다. 비교되는 쌍은 강조 표시되고 이미 정렬된 숫자는 아래 그림에서 이탤릭체로 표시됩니다.

첫 번째 패스에서는 가장 큰 숫자(9)를 배열의 마지막으로 배치합니다. 두 번째 단계에서는 아래 그림 (b)에 표시된 대로 요소 쌍을 순차적으로 비교하고 순서를 지정합니다. 배열의 마지막 요소가 이미 가장 크기 때문에 마지막 쌍을 고려할 필요가 없습니다. 세 번째 단계에서는 아래 그림(c)에 표시된 대로 마지막 두 요소를 제외하고 요소 쌍을 순차적으로 비교하고 순서를 지정합니다. 왜냐하면 요소 쌍이 이미 순서대로 되어 있기 때문입니다. 따라서 k번째 패스에서는 마지막 k - 1개 요소가 이미 주문되어 있으므로 고려할 필요가 없습니다.

버블 정렬 알고리즘은 아래 코드에 설명되어 있습니다.

for (int k = 1; k // k번째 패스 수행
for (int i = 0; i < list.length - k; i++) {
if (목록[i] > 목록[i + 1])
목록[i]을 목록[i + 1]로 교체;
}
}

패스에서 스왑이 발생하지 않으면 모든 요소가 이미 정렬되어 있으므로 다음 패스를 수행할 필요가 없습니다. 이 속성을 사용하면 아래 코드에서와 같이 위 코드의 알고리즘을 개선할 수 있습니다.

부울 needNextPass = true;
for (int k = 1; k // 배열이 정렬될 수 있으며 다음 패스가 필요하지 않습니다
needNextPass = false;
// k번째 패스 수행
for (int i = 0; i < list.length – k; i++) {
if (목록[i] > 목록[i + 1]) {
목록[i]을 목록[i + 1]로 교체;
needNextPass = true; // 다음 패스가 여전히 필요합니다
}
}
}

알고리즘은 아래 코드로 구현 가능합니다

가장 좋은 경우 버블 정렬 알고리즘은 배열이 이미 정렬되었는지 확인하기 위해 첫 번째 패스만 필요하며 다음 패스는 필요하지 않습니다. 첫 번째 패스에서 비교 횟수는 n – 1이므로 버블 정렬의 최적 사례 시간은 O(n)입니다.

최악의 경우 버블 정렬 알고리즘에는 n - 1번의 통과가 필요합니다. 첫 번째 패스에서는 n - 1번의 비교를 수행합니다. 두 번째 패스에서는 n - 2번의 비교를 수행합니다. 등; 마지막 패스에서는 1번의 비교가 이루어집니다. 따라서 총 비교 횟수는 다음과 같습니다.

따라서 버블 정렬의 최악의 경우 시간은 O(n^2)입니다.

위 내용은 버블정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!