Time Complexity: Empirically test the assertion that the execution times of sele

Question

Time Complexity:

Empirically test the assertion that the execution times of selection sort, bubble sort, and insertion sort algorithms are in O(n2). To do this, implement and execute each algorithm using vectors of different sizes and record the execution times. If an algorithm is indeed in O(n2), there must exist a constant c such that for any n the execution time is c * n2. Implement each algorithm and first make sure the corresponding program works correctly. Then for each n determine the execution time and the value of n2. Now working your way backward you could compute the value of c by dividing the execution time by n2. If the values of c are roughly equal for each n then the algorithm is indeed in O(n2).

You could use the time command to measure how much time your program takes for a given value of n. Run your program as follows:

where the user enters n and the program generates a vector (of size n) of random integers in the range [0-1,000,000). The program then proceeds to sort and output the numbers into output file. It is important to make sure that n is a user input and the above output redirection is used. Otherwise, the typescript of the sample runs would get unmanageably too large! After the program terminates, the time command prints real, user, and system times. You are interested in user time. Type

to learn more about this command.
Run each program 10 times starting with n = 1,000 and incrementing n each time by 1,000.
Hand in a printout of each program, the typescript of all 10 runs for each program, and the following completed table for each program/algorithm:

Use STL vector v to implement all three functions where n is the size of the vector. The algorithms for the functions follow:

n n2 Exec Time (sec) c = Time / n2 1,000 1,000,000 ... ... 2,000 4,000,000 ... ... ... ... ... ... 10,000 100,000,000 ... ...

Explanation / Answer

selection sort almost always outperforms bubble sort and gnome sort."

Worst case time complexity: O(n 2 ) O(n2)

Number of comparisons: O(n 2 ) O(n2)

Best case time complexity :

Average case time complexity :

Run each program 10 times starting with n = 1,000 and incrementing n each time by 1,000.
Hand in a printout of each program, the typescript of all 10 runs for each program, and the following completed table for each program/algorithm:

Execution Times of Sort Algorithms

In this recitation, you will write implementations for Selection, Insertion, and Bubble Sort algorithms, apply them to lists of different lengths, keep track of execution times, and plot the results.

Sort Algorithms

The three sort algorithms are summarized here.

Bubble Sort

Compare pairs of values from left to right, swapping if out of order. Largest value bubbles to the right.

Set n to size of list.

Set sorted to false.

Repeat for pass from 0 through n-1

Set sorted to true

Repeat for i from 0 through n-pass-1

if data[i] and data[i+1] are out of order, swap them and set sorted to false.

if sorted is still true, return.

Selection Sort

Find largest item and swap it with value at end of list. Find largest item in remaining sublist (all but last element), and swap it with value at end of sublist. Continue in this fashion.

Set n to size of list.

Repeat for destinationIndex from n-1 through 1.

Find maxValue and maxValueIndex over indices 0 through destinationIndex.

Swap data[maxValueIndex] and data[destinationIndex].

Insertion Sort

List is partitioned into sorted part followed by unsorted part, with the sorted part initially containing just one value, the first element in the list. For each iteration, insert first value in unsorted part into correct place in sorted part. Do this by stepping right to left through sorted part, shifting values one position to the right, until correct position is found.

Set n to size of list.

Repeat for firstUnsortedIndex from 1 through n-1

the execution times of all sorting algorithms and the n 2   and nlog 2 n lines.

Set valueToInsert to data[firstUnsortedIndex].

Repeat for i from firstUnsortedIndex down through 1 while valueToInsert < data[i-1]

Set data[i] to data[i-1].

Set data[i] to valueToInsert.

n n2 Exec Time (sec) c = Time / n2 1,000 1,000,000 ... 2,000 4,000,000 ... ... ... ... ... ... 10,000 100,000,000 ... ...

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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