Keywords: Bubble Sort | C# Programming | Algorithm Optimization
Abstract: This paper provides an in-depth analysis of the bubble sort algorithm implementation in C#, examining common output placement errors through specific code examples. It details the algorithm's time complexity, space complexity, and optimization strategies while offering complete correct implementation code. The article thoroughly explains the loop output errors frequently made by beginners and provides detailed correction solutions to help readers deeply understand the core mechanisms of sorting algorithms.
Algorithm Principles and Implementation Analysis
Bubble sort is a fundamental comparison-based sorting algorithm whose core concept involves comparing and swapping adjacent elements to gradually "bubble" larger elements to the end of the array. When implementing bubble sort in C#, special attention must be paid to loop structure and output timing selection.
Original Code Problem Diagnosis
The original code provided by the user contains a critical logical error: the output statement is incorrectly placed inside the outer loop. Specifically:
for (int write = 0; write < arr.Length; write++)
{
for (int sort = 0; sort < arr.Length - 1; sort++)
{
if (arr[sort] > arr[sort + 1])
{
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
Console.Write("{0} ", arr[write]);
}This implementation causes the element at the current index position to be output immediately at the end of each outer loop iteration, while the array hasn't been fully sorted yet. Particularly during the sorting process of array <span style="font-family: monospace;">{800,11,50,771,649,770,240,9}</span>, intermediate results are incorrectly output.
Correct Implementation Solution
The corrected code completely separates output operations from sorting operations:
int[] arr = { 800, 11, 50, 771, 649, 770, 240, 9 };
int temp = 0;
for (int write = 0; write < arr.Length; write++) {
for (int sort = 0; sort < arr.Length - 1; sort++) {
if (arr[sort] > arr[sort + 1]) {
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
}
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " ");
Console.ReadKey();This implementation ensures that output operations only occur after the entire sorting process is complete, thereby guaranteeing the correctness of the output results.
Algorithm Complexity Analysis
Bubble sort has a time complexity of O(n²), where n represents the length of the array. In the worst-case scenario (completely reverse-ordered array), n(n-1)/2 comparisons and swaps are required. The space complexity is O(1) since the algorithm only uses a fixed number of additional variables.
Optimization Strategy Discussion
Although basic bubble sort has low efficiency, it can be optimized through the following strategies:
- Add flags to detect whether swaps occurred, allowing early termination if no swaps occur in a round
- Record the position of the last swap to reduce the comparison range in subsequent rounds
- Combine with other sorting algorithms to form hybrid sorting strategies
Practical Application Recommendations
In practical development, bubble sort still has certain application value for small datasets or nearly ordered data. However, for large-scale data sorting, more efficient algorithms such as quicksort or merge sort are recommended. Understanding the core principles of bubble sort is significant for learning more complex sorting algorithms.