Scribd
Upload
3 views1 page

Bubble Sort Pseudo Code Lab

This document provides instructions for Lab #1, which involves sorting array data using bubble sort. Students are asked to write pseudo code to implement bubble sort on an array, assuming the array holds values and pointers. They must also state and prove the complexity of bubble sort. The tasks are to be completed in class and outside of class, with some code and results to be uploaded before the next class. Bubble sort is used because of its simplicity, though it is not the most efficient sorting algorithm.

Uploaded by

AnassKiass
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
3 views1 page

Bubble Sort Pseudo Code Lab

This document provides instructions for Lab #1, which involves sorting array data using bubble sort. Students are asked to write pseudo code to implement bubble sort on an array, assuming the array holds values and pointers. They must also state and prove the complexity of bubble sort. The tasks are to be completed in class and outside of class, with some code and results to be uploaded before the next class. Bubble sort is used because of its simplicity, though it is not the most efficient sorting algorithm.

Uploaded by

AnassKiass
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

CSE382 – Algorithms and Data Structures Fall 2008

Lab #1 – Sorting array data in Pseudo Code then code

Prologue:
This lab is concerned with sorting data in arrays. In this lab we will use a simple
algorithm for sorting, e.g., bubble sort1.

Starting Condition:
For the first three tasks of this lab you are required to put all your possessions,
including any laptops, on the floor, keeping only paper and pencils, erasers, and
pens on your desktop.

Tasks to be completed in class:


1. Write pseudo code that implements the application of bubble sort to put an array
of values into ascending order.
2. Repeat Task #1, but assume that the array holds pointers to its values.
3. State the complexity of this process, then prove your assertion.

Tasks to be completed outside of class:


4. If you find your pseudo code to be defective in any of the steps below, correct it.
5. Convert your pseudo code into C++ code that implements bubble sort for an
array of values. Write a test driver that times the execution of bubble sort 2 for
random integer values filling arrays of sizes n i = { 10, 100, 1000, 10000 }.
Compare Ti/T0 for i=1, 2, 3 with the complexity you asserted in class.
6. Repeat Task #4 for arrays holding pointers to integer values stored on the heap.
7. Repeat Task #4 using C#.
8. Repeat Task #5 using C# where the arrays hold references to boxed integers.
9. Upload your code and a, possibly corrected, word file containing your cleanup
pseudo code to the college server.

Note:
You must hand in whatever you have completed in class at the end of that class.
You must upload the results of Tasks #4 - #8 before you come to class on Wednesday.

Bubble sort is not a useful algorithm as there are several fairly simple sorting algorithms
with much better performance. We use it here only because its simplicity allows you to
effectively write, what may be your first, pseudo code and proof. Though widely
disparaged, for collections of only a few elements, bubble sort may be faster, due to its
simplicity. We will explore this in a later lab.

1
Bubble sort is a simple process. You iterate through a container and if the ith and (i+1)th
values are out of order you swap them. You keep iterating through the entire array using this
process until the entire array is sorted.
2
Please use the high resolution timers I’ve put in the code folder.

You might also like