I had an argument with a friend about the real bubble sort of the following two algorithms, and about which one is better, no mention which one is mine, I just want to hear your answers on these two questions about those two algorithms (written in c++)
1-which one is the real bubble sort?
2-which one is better?
here are the two algorithms :
// Number one :
void BubbleSort(int Arr[], int size)
{ for (int i=0;i<size-1;i++)
for (int j=i+1;j<size;j++)
if (Arr[i]>Arr[j])
{ int temp = Arr[i];
Arr[i] = Arr[j];
Arr[j] = temp;
} }
// Number two :
void BubbleSort(int Arr[], int size)
{ for (int i=0;i<size-1;i++)
for (int j=0;j<size-1;j++)
if (Arr[j]>Arr[j+1])
{ int temp = Arr[j];
Arr[j] = Arr[j+1];
Arr[j+1] = temp;
} }
Selection sort performs a smaller number of swaps compared to bubble sort; therefore, even though both sorting methods are of O(N2), selection sort performs faster and more efficiently!
Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
What is the best case efficiency of bubble sort in the improvised version? Explanation: Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n). 10.
Given that average case for Bubble Sort is the worst case for Quick Sort, it is safe to say that Quick Sort is the superior sorting algorithm. For short arrays (under 1,000 elements), the benefits of Quick Sort are minimal, and might be outweighed by it's complexity, if the goal is readability.
Number Two is closer to the real one. All comparisons should be between adjacent elements.
But the real bubble sort would take a while
loop instead of an outer for
loop, and the while
loop would execute again only if elements had to be swapped on the last pass, like this:
void BubbleSort(int Arr[], int size)
{
bool swapped;
do {
swapped = false;
for (int j=0;j<size-1;j++)
if (Arr[j]>Arr[j+1]) {
int temp = Arr[j];
Arr[j] = Arr[j+1];
Arr[j+1] = temp;
swapped = true;
}
} while (swapped);
}
The pseudocode for the nested loop bubble sort is:
procedure bubbleSort( A : list of sortable items )
n := length(A)-1
for(i=0; i<= n; i++)
for(j=n; j>i; j--)
if A[j-1] > A[j] then
swap (A[j-1], A[j])
end if
end for
end for
end procedure
This means that the first is closest because the inner loop only iterates over elements after i. The second method you showed has an inner loop which iterates over all elements, even though elements before i have already been sorted, so there's no need to waste time on them.
That means the first method is also better.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With