Sorting Algorithms

Question 1

What is the Bubble Sort Algorithm

Answer 1

• The algorithm starts at the first element in an array and compares it to the second
• If they are in the wrong order, the algorithm swaps the pair. Otherwise, the algorithm moves on
• The process is then repeated for every adjacent pair of elements in the array until the end of the array is reached (at which point the largest element is in the last position of the array).

Question 2

Describe the psudocode for a Bubble Sort Algorithm

Answer 2

Function BubbleSort (int[] data)

numItems = data.length - 1

For i = 0 to numItems - 2

For j = 0 to numItems - i - 2

If data[j] > data[j + 1]

temp = data[j]

data[j] = data[j + 1]

data[j + 1] = temp

end if

next j

next i

end fucntion

Question 3

Describe the pseudocode for a Improved Bubble Sort Algorithm

Answer 3

Function BubbleSort (int[] data)

numItems = data.length - 1

Swapped = true

WHILE numItems > 0 AND swapped

Swapped = False

numItem = numItems – 1

FOR count = 0 to numItems – 1

IF data[count] > data[count + 1] THEN

temp = data[count + 1]

data[count + 1] = data[count]

data[count] = temp

Swapped = True

END IF

NEXT Count

END WHILE

return data

END FUNCTION

Question 4

Why do we use an Improved Bubble Sort Algorithm

Answer 4

• Oridnary Bubble Sort could make many pointless comparisons which waste time
• Improved Bubble Sort has a flag recording whether a swap has occurred. If a full pass is made without any swaps, then the algorithm terminates earlier than it would have done originally saving time
• Improved Bubble Sort has the inclusion of j​ in the second for​ loop. This means that as j increases, fewer comparisons are made. This works because the largest element is always in place at the end of the first pass, and the second largest element is in place at the end of the second pass and so on. There is no need to check these elements as we know they’re in the right place

Question 5

What is the Time Complexity and Space Complexity of the Bubble Sort

Answer 5

Best Case Time Complexity- O (n)

Wosrt Case Time Complexity - O (n​²​)​

Space Complexity - 0 (n)

Question 6

What is the Insertion Sort Algorithm

Answer 6

• Insertion sort starts at the second element in the input, and compares it to the element to its left
• If the two elements are in the wrong order, the smaller element is placed in the lowest position
• The third element in the input is then selected, it is inserted into the correct position in the sorted portion of the input to its left
• This continues until the last element is inserted into the correct position

Question 7

Describe the pseudocode for a Insertion Sort

Answer 7

Function insertionSort(int[] data)

For count = 1 to data.length

currentdata = data[count]

While (count > 0 AND data[count –1] > currentdata

temp = data[count]

data[count] = data[count - 1]

data[count - 1] = temp

count = count - 1

End while

data[count] = currentdata

NEXT COUNT

END FUNCTION

return A

Question 8

What is the Time Complexity of an Insertion Sort

Answer 8

Worst Time Complexity - O (n​²)

Best Time Complexity - O (n)

Space Complexity - O (k)

Question 9

What is a Merge Sort Algorithm

Answer 9

• Merge sort is formed from two functions
• One called MergeSort​ and another called Merge​
• MergeSort​ divides its input into two parts and recursively calls MergeSort​ on each of those two parts until they are of length 1 at which point Merge​ is called
• Merge puts groups of elements back together in a special way, ensuring that the final group produced is sorted

Question 10

What is the Time Complexity and Space Complexity of a Merge Sort

Answer 10

Best and Worst Time Complexity - O(n logn)

Space Complexity - O (n) because the merge sort needs extra space for the left and right sublists that are created whenever items is split, if the original list has n items, then the sublists will also need to hold n items in total

Question 11

What is a Quick Sort Algorithm

Answer 11

• Quick sort works by selecting an element, often the central element (called a pivot), and dividing the input around it
• Elements smaller than the pivot are placed in a list to the left of the pivot and others are placed in a list to the right
• This process is then repeated recursively on each new list until all elements in the input are old pivots themselves or form a list of length 1

Question 12

What is the Time Complexity of a Quick Sort Algorithm

Answer 12

O (n log n​)