Lab Demo#2

Question 1

What makes a sorting algorithm stable?

Answer 1

-if it preserves the order of duplicate keys

Question 2

How can a sorting algorithm be made stable?

Answer 2

-can be made stable by considering the “index” as a comparison parameter

Question 3

Is bubble sort stable or unstable?

Answer 3

Stable

Question 4

is insertion sort stable or unstable?

Answer 4

Stable

Question 5

Is selection sort stable or unstable?

Answer 5

Unstable
-but it can be coded to be stable

Question 6

Is shell sort stable or unstable?

Answer 6

-unstable

Question 7

List the advanced sorting algorithms

Answer 7

-Merge Sort
-Quick Sort
-Radix Sort/Bucket Sort
-Heap Sort

Question 8

Is merge sort stable or unstable?

Answer 8

-Stable

Question 9

-Is quick sort stable or unstable?

Answer 9

-Unstable
can be made stable using the Partition Algorithm

Question 10

Is Radix Sort/Bucket Sort stable or unstable?

Answer 10

-Unstable

Question 11

Is Heap Sort stable or unstable?

Answer 11

Unstable

Question 12

What is the best time complexity of Bubble Sort?

Answer 12

O(n)

Question 13

What is the worst time complexity of Bubble Sort?

Answer 13

O(n^2)

Question 14

What is “natural order”?

Answer 14

It is the default order in which elements are arranged when sorted
ex. integers are sorted in ascending numerical order
ex.

Question 15

How to define natural order of a class?

Answer 15

by implementing the Comparable<> interface

Question 16

What is “order by comparator”?

Answer 16

sorting based on custom order defined by a Comparator<T> implementation
-differs from natural order</T>

Question 17

How do you implement “order by comparator”?

Answer 17

1. Implement the comparator<T> interface</T>
2. Override the compare(T o1, T o2) method

Question 18

What do you need to do to sort instantiated objects of a class MyClass using natural order?

Answer 18

1. Implement the Comparable<MyClass> interface in MyClass</MyClass>
2. Override the compareTo(MyClass other) to define the natural order

Question 19

What is the stability of a sorting algorithm?

Answer 19

Depends on how it treats equal elements in a dataset
-its stable if it preserves the relative order of equal elements in a dataset

Question 20

How is the stability of a sorting algorithm ensured?

Answer 20

Ensured by:
1. comparing elements carefully
2. avoid unnecessary swaps of equal elements

Question 21

Can any sorting algorithm be made stable?

Answer 21

Yes
-but you would need to add extra information to the data or change how comparisons and swaps are performed

Question 22

What are the inherently stable sorting algorithms?

Answer 22

-Bubble Sort
-Insertion Sort
-Merge Sort

Question 23

Can Radix sort be used to sort the instantiated objects of a class called MyClass?

Answer 23

Yes
-only if the sorting criteria for MyClass can be broken into keys that Radix Sort can handle (like integers and strings)

Question 24

If you sort an array with the same dataset, same algorithm, and same machine twice, will the execution time be the same?

Answer 24

The execution time will slightly vary
-for an example, a randomly selected pivot in a Quick Sort

Question 25

How have you picked the pivot in the Quick Sort algorithm? What is the justification?

Answer 25

Lab 6, but common pivot positions are: -First element -Last element -Median of the first, middle, and last elements -random element

Question 26

What happens if Quick Sort is called on an already sorted array?

Answer 26

-The partitions would be highly unbalanced if the first or last element is chosen (worst time complexity = On^2

Question 27

What is the space complexity of a Quick Sort being called on already sorted array?

Answer 27

O(n) as recursive calls add overhead

Question 28

Modify any algorithm to do the sorting in descending order

Answer 28

Practice using Bubble Sort

Question 29

Generate a random number between min and max inclusive using Math.random().

Answer 29

Practice int randomNumber = (int)(Math.random() * (max - min + 1)) + min;

Question 30

For a small dataset (50 elements), which algorithm would you choose and why?

Answer 30

Insertion Sort -low overhead -has a best time complexity of On Bubble Sort would also be good

Question 31

If you create a class MyClass that implements Comparable interface, would you prefer choosing primitive datatype (when needed) over Wrapper class object reference. What is the basis of your response?

Answer 31

Primitives are usually more memory efficient and faster -However, if I wanted to use ArrayList and Collection.sort(), I would need to use wrapper classes

Question 32

If you would like to do Bucket-search Strings that use alphabetical characters, how many buckets would you need to accomplish this? Why?

Answer 32

26 buckets for each letter -for ex. all names with A go into the A bucket

Question 33

What would be your preference between Merge and quick sort? Why?

Answer 33

small datasets where stability is required = Merge Sort. large datasets with no stability requirement = Quick Sort due to its faster average-case performance.

Question 34

What are the advantages of Merge Sort?

Answer 34

-Stable -Time complexity is always Onlogn -really good for linked lists

Question 35

What are the disadvantages of Merge Sort?

Answer 35

-requires additional space for merging -slower for small datasets due to overhead

Question 36

What are the advantages of Quick Sort?

Answer 36

-It is in-place with O(logn) O(logn) space complexity. -Generally faster in practice due to fewer memory operations. -Can be optimized using pivot selection techniques.

Question 37

If you are sorting integer data set, what would be your sorting algorithm choice? Why?

Answer 37

-Radix Sort: If integers have a limited range and dataset size is large. -Quick Sort: For general-purpose sorting with in-place requirements.