The following algorithm is known as bubble sort. The following structure shows t

Question

The following algorithm is known as bubble sort. The following structure shows the indention structure of this algorithm. Ensure to implement your code following this structure While the list is not sorted For each adjacent pair of elements Ifthe pair is not sorted Swap its elements Now, implement this bubble sort algorithm and test its performance. You should submit two files. The first is the implementation of this algorithm and the second file is the performance of measurement of this algorithm. You could check Lab 12 in class practice 1 and 2 about how we could test the performance of one algorithm. Once you have your performance measurement of bubble sort algorithm available (i.e., executing your file 2), compare to performance measurement of selections°rt algorithm (Lab 12 in class practice 1) and let me know which algorithm is more effective. (Tips: in your algorithm implementation file, you should have two functions. The first function implements the bubble sort algorithm. The second function is the place to hold the temporary space to swap two unsorted adjacent pair of elements)

Explanation / Answer

Answer:

Using Python:BUBBLE SORT

-----------------------------------

def bubbleSort(ary):

n = len(ary)

# Traverse through all array elements

for i in range(n):

# Last i elements are already in place

for j in range(0, n-i-1):

# traverse the array from 0 to n-i-1

# Swap if the element found is greater

# than the next element

if ary[j] > ary[j+1] :

ary[j], ary[j+1] = ary[j+1], ary[j]

# Driver code to test above

ary = [1, 5, 7, 8, 4, 2, 3, 0, 9, 6]

bubbleSort(ary)

print ("Sorted array is:")

for i in range(len(ary)):

print ("%d" %ary[i]),

OUTPUT:

PERFORMANCE TEST:

// header

using namespace std;

long length = 1000;
const long max_length = 300000;

int list[max_length];

void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}

void bubbleSort() //write the bubble sort program
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list[j] > list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
// void selection sort (write the algorithm for selection sort)

long partition(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;

while (left < right)
{
while(list[left] <= pivot_element)
left++;
while(list[right] > pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}

int main()
{
double t1, t2;

for (length = 1000; length <= max_length; )
{
cout << " Length : " << length << ' ';

read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";

read();
t1 = clock();
selectionSort();
t2 = clock();
cout << "Selection Sort : " << (t2 - t1)/CLK_TCK << " sec ";

read();

switch (length)
{
case 1000 :
length = 5000;
break;
case 5000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
case 100000 :
length = 200000;
break;
case 200000 :
length = 300000;
break;
case 300000 :
length = 300001;
break;
}
}

return 0;
}

Once the data is retrived we will find that the

Bubble sort is a stable algorithm while the selection sort is not. On the other hand the worst case complexity is same as O(n2) while the best case complexity of bubble sort is better as it takes n times while selection sort takes n2 time for the same case to sort an array.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.