Sorting Algorithms

Question 1

1. Describe how the bubble sort algorithm works
2. What is its time complexity?

Answer 1

1. Look at com.barca.common.algorithms
2. O(n^2)

Question 2

1. Describe how the select sort algorithm works
2. What is its time complexity?

Answer 2

1. 1. Point to the first element
   2. Scan for the lowest element
   3. Swap the lowest element with the pointer element
   4. Increment the pointer by 1 and repeat 2 - 3
2. O(n^2)

Question 3

Although bubble sort and select sort are both O(n^2), is one more efficient than the other?

Answer 3

Yes. Bubble sort is O(n^2) while select sort is O(n^2/2). In other words, select sort is twice as efficient as bubble sort. This is important to recognize because it asserts the importance of optimizing algorithms within the same Big O class

Question 4

1. Describe how the insertion sort algorithm works
2. What is its time complexity?

Answer 4

1. 1. Point to and “remove” the second element
   2. If the elements to the left are >, shift them to the right
   3. “Insert” the “removed” element in the space created by step 2
   4. Increment pointer and repeat 2 - 4
2. Avergage case: O(n^2)
   Worst case: O(n^2)

Question 5

What is an in-place sorting algorithm?

Answer 5

An in-place sorting algorithm is an algorithm that sorts data without creating any new data structures

Question 6

What is the difference between a stable and unstable sorting algorithm?

Answer 6

A stable algorithm maintains the order of elements that have the same value. An unstable algorithm does not maintain the order of elements that have the same value