Page 239 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes }
}
cout << “nSorted list:” << endl; // Display the sorted
array
for(int i=0;i < n;i++)
{
cout << a[i] << “ ”;
}
return 0;
}
The output is shown as below:

Source: http://www.exforsys.com/tutorials/c-algorithms/bubble-sort.html
A flag is required to check if any swaps have occurred at a run of the algorithm. If a swap has
taken place, the flag becomes 1, and the while loop gets at least one more pass. When the flag is
0, it means that no swap has taken place so the arrays has been sorted and the while loop gets
ignored.

Also, the k must be greater or equal to 0, this represents the number of elements of the list, and
at each pass it decrements its value by 1. If this condition and the previous one are both true at
the same time, then the array isn’t sorted, and the program enters the while loop. If one of the
conditions is false, then the array has been sorted out.

There is a for loop embedded inside a while loop (n–1)+(n–2)+(n–3)+ ... +1 which results in
O(n^2), Swaps - Best Case 0, or O(1) and on Worst Case (n–1)+(n–2)+(n–3) + ... +1 , or O(n^2).
Some of the advantages of bubble sort are:

it is easy to learn;
few lines of code;
works very well on already sorted lists, or lists with just a few permutations.
Some of the disadvantages of bubble sort are:

not effective for large numbers of sorting elements;
complexity is O(n^2).

13.6.2 Quick Sort

Quick sort is a comparison sort developed by Tony Hoare. Also, like merge sort, it is a divide
and conquer algorithm, and just like merge sort, it uses recursion to sort the lists. It uses a pivot
chosen by the programmer, and passes through the sorting list and on a certain condition, it
sorts the data set.

232 LOVELY PROFESSIONAL UNIVERSITY