Page 238 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 4<6, no swap occurs Notes
(0 1 2 4 6 9) -> (0 1 2 4 6 9): 6<9, no swap occurs
The algorithm now knows that the list is sorted.
The implementation of bubble sort in c is shown as below:
#include < iostream >
using namespace std;
int main()
{
int a[100]; // The sorting array
int n; // The number of elements
cout << “Please insert the number of elements to be sorted:”;
cin >> n; // The total number of elements
for(int i=0; i<n; i++)
{
cout << “Input” << i << “element:”;
cin >>a[i]; // Adding the elements to the array
}
cout << “Unsorted list:” << endl; // Displaying the
unsorted array
for(int i=0; i<n; i++)
{
cout << a[i] << “ ”;
}
int flag=-1; // The flag is necessary to verify is the array
is sorted, 0 represents sorted array
int k=n; // Another variable is required to hold
the total number of elements
while(flag!=0 && k>=0) // Conditions to check if the
array is already sorted
{
k=k-1;
flag=0;
for (int i=0; i<k; i++)
{
if(a[i]>a[i+1]) // Check if the two
adjacent values are in the proper order, if not, swap them
{
int aux=a[i]; // The swap procedure
a[i]=a[i+1];
a[i+1]=aux;
flag=1; // A swap has taken
place, this means a new run of the algorithm must take place
} // to determine if the array is sorted.

LOVELY PROFESSIONAL UNIVERSITY 231