Standard sorting algorithms

Data in a computer program needs to be sorted.

Describe the steps a bubble sort will take to sort items into ascending order.

Darcie and Felix have both written a program that will perform a bubble sort to put these numbers into ascending order.

Darcie’s version will complete six passes. However, Felix’s version will only need to complete two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

A third type of sorting algorithm is a quick sort.

The following quick sort algorithm is made up of two functions called partition() and quickSort(). The algorithm will sort an integer array into ascending numerical order.

Identify which of the two functions is recursive and give all of the line numbers where recursive calls are made.

Recursive function name........

Recursive call line numbers........

Identify the type of iteration used in the function partition().

Describe the role of the function partition() in the quick sort algorithm.

The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Amended line of code........

The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

The following strings are stored in an array.

Explain how a linear search would search the array for the index that stores "clouds".

State why a binary search cannot be used in this example.

Show how an insertion sort will sort the given data into ascending alphabetical order.

A sorting algorithm has a best time complexity of O(n).

Describe what is meant by the best time complexity O(n) for a sorting algorithm.

Another sorting algorithm has a worst space complexity of O(log(n)).

Describe what is meant by the worst space complexity O(log(n)) for a sorting algorithm.

Identify the time complexity that means the time will not change even when the number of items increases.

Identify the space complexity that means the amount of memory (space) used will double each time a new item is included.

7* (a) A program designer needs to decide on an algorithm to use from a choice of three. The table shows the worst-case Big O complexities for each algorithm.

The program will be used to analyse data that can range from 2 items to 2 billion items.

Compare the use of all three algorithms and suggest which the programmer should use.

You should include the following in your answer:

• the meaning of constant, logarithmic, linear and exponential complexity

• how well each algorithm scales as the amount of data increases

• which algorithm is the most suitable for the given task.

The program designer is investigating the use of concurrent processing.

Describe what is meant by the term ‘concurrent processing’.

Give two benefits of using concurrent processing.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Describe how a merge sort works.

Give one benefit and one drawback of the programmer using a merge sort instead of a bubble sort.

The programmer uses an Integrated Development Environment (IDE).

Complete the table by identifying and describing three IDE features that can help the programmer to develop, or debug a program.

A bubble sort will sort an array of 50 integer values called numberArray.

State why the integer values are stored in an array instead of separate variables.

This bubble sort algorithm is written to sort numberArray into ascending numerical order.

Complete this bubble sort algorithm.

One section of numberArray is shown here.

A second sorting algorithm that could be used to sort this data is a merge sort.

Show how a merge sort will sort this section of the array numberArray into ascending numerical order.

* Another sorting algorithm is insertion sort.

The number of values stored in the array numberArray has been reduced to 10.

Compare the use of bubble, merge and insertion sorts on the array numberArray.

You should include the following in your answer:

• how each algorithm works

• the Big O complexities for each algorithm

• the suitability of each algorithm for sorting the 10 values.

A one dimensional array holds data that needs to be sorted.

Describe how a quicksort would sort data into ascending order.

Explain why a quicksort is known as a divide and conquer algorithm.

The following pseudocode procedure performs an insertion sort on the array parameter.

Explain why dataArray is passed by reference and not by value.

State whether the procedure insertionSort sorts the data into ascending or descending order and explain your choice.

* Two other sorting algorithms are merge sort and quick sort.

Compare the use of merge sort, quick sort and insertion sort on an array with a small number of elements, and on an array with a very large number of elements.

You should make reference to the time complexities of each algorithm using the Big O notation in your answer.

A fourth sorting algorithm is a bubble sort.

Describe how a bubble sort will sort an array of 10 elements.

The temperatures of an ocean are input into a computer system. They are recorded, and will be accessed, in the order in which they arrive. The data for one week is shown:

5, 5.5, 5, 6, 7, 6.5, 6

The data is to be stored in a data structure. The programmer stores the data in a queue.

Explain why a queue is used instead of a stack.

The data is processed. After processing, the value for the first day is stored as 0. The value for each following day is stored as an increase, or decrease, from the first day.

For example: if the first day was 7, the second was 6 and the third was 9, after processing it would be stored as 0, –1, 2.

The queue uses dequeue() to return the first element of the queue.

dequeue() is a function.

Explain why dequeue() is a function, not a procedure.

The contents of processedData are shown.

The data needs to be sorted into ascending order.

Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation.

A 1-dimensional array stores the following data:

The array needs sorting into descending order.

Describe how a merge sort would sort the given array into descending order.

An insertion sort can be used to sort the array instead of a merge sort.

Explain why an insertion sort might use less memory than a merge sort.

A computer program stores data input on a stack named dataItems. The stack has two sub-programs to add and remove data items from the stack. The stack is implemented as a 1D array, dataArray.

The current contents of dataItems are shown:

The main program asks a user to push or pop an item from the stack. If the user chooses ‘push’, the data item is added to the stack. If the user chooses “pop”, the next item is removed from the stack, multiplied by 3 and output.

The main program is shown:

Before the sub-programs, push() and pop(), can add or remove items from the stack, a selection statement is used to decide if each action is possible.

Describe the decision that needs to be made in each sub-program and how this impacts the next process.

The algorithm does not work when the user enters "PUSH" or "Push". The algorithm needs to be changed in order to accept these inputs.

Identify the line number to be changed and state the change that should be made.

The stack is implemented as a 1D array, dataArray.

Describe how a 1D array can be set up and used to push and pop items as a stack.

As an array, the data in dataArray is sorted and then searched for a specific value.

The data in dataArray is sorted into ascending order using an insertion sort.

The current contents of dataArray are shown:

Show the steps of an insertion sort on the current contents of the array dataArray.

The array dataArray can now be searched using a binary search.

Describe the stages of a binary search on an array of size n.

The array has 50 items.

The function, searchItem(), performs a linear search for a data item.

Rewrite the function using a while loop.

A programmer needs to sort an array of numeric data using an insertion sort.

The following, incomplete, algorithm performs an insertion sort.

Complete the algorithm.

Show how an insertion sort would sort the following data:

Using Big-O notation state the best case complexity of insertion sort.

Explain what your answer to part (b)(i) means.

(c*) The number of data items in the array is continually increasing.

Insertion sort has a worst case time complexity of O(n²) and space complexity of O(1).

An alternative sorting algorithm that could be used is bubble sort which also has a worst case time complexity of O(n²) and space complexity of O(1).

Briefly outline how the bubble sort algorithm works. Discuss the relationship between the complexities and the two sorting algorithms and justify which of the two algorithms is best

suited to sorting the array.