Describe, interpret and manipulate data structures including arrays (up to three dimensions), stacks, queues, trees, linked lists and hash tables.
Describe the manipulation of arrays (up to three dimensions).
Represent the operation of stacks and queues using pointers and arrays.
Represent the operation of linked lists and trees using pointers and arrays
Make sure your recap your knowledge on Searching and Sorting from AS first. Click on these buttons to go directly to the Searching and Sorting pages for AS.
Sorting:
Explain the need for a variety of sorting algorithms both recursive and non-recursive
Describe the characteristics of sorting algorithms (bubble sort and insertion sort learnt at AS), plus quicksort
Explain the effect of storage space required, number of comparisons of data items, number of exchanges needed and number of passes through the data on the efficiency of a sorting algorithm.
Use Big O notation to determine the efficiency of different sorting algorithms in terms of their time and space requirements and to compare the efficiency of different sorting algorithms.
Searching:
Explain & apply a shortest path algorithm
Use Big O notation to determine the efficiency of linear and binary searches in terms of execution time and space requirements and to compare the efficiency of different searching algorithms.
For both Sorting & Searching:
Follow Search (Linear, Binary) and Sort (Bubble Sort, Insertion Sort, Quick Sort) algorithms and programs and make alterations to such algorithms.
Write search and sort algorithms and programs.
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(n2), respectively.
WJEC 2019 Unit 4 Question
a) Describe the purpose of this algorithm [2]
b) Describe the characteristics of this type of algorithm [3]
c) Describe the advantages arising from the elegance of this algorithm [3]
This question shows a good example of a Quick Sort algorithm.
Lets look at the answers to the questions above:
a) Describe the purpose of this algorithm [2]
The algorithm is a Quick Sort algorithm, which sorts an array (1 mark) into ascending order (1 mark)
b) Describe the characteristics of this type of algorithm [3]
This is a recursive (1 mark) algorithm, that calls itself (1 mark), and has a stopping condition (or base case) (1 mark)
c) Describe the advantages arising from the elegance of this algorithm [3]
(Any 3 of the 4 points):
Recursion has allowed for simpler design and for the original complex problem of sorting an array to be solved in a shorter timespan than a non-recursive sorting algorithm.
The algorithm is very compact.
The algorithm uses a divide and conquer design where the main problem is recursively broken into sub-problems.
The solutions of the sub-problems are then combined to produce a solution for the original problem.
What are the differences between a Bubble Sort and a Quick Sort?
Key Difference: Bubble sort is the simplest form of sorting algorithm technique that involves swapping of two adjacent elements in order to put them in right place, where as Quick sort works on split and win algorithm technique into which a pivotal element becomes the focal point of division around the given array.
Usefulness: During large arrays sorting, Bubble Sort performs poorly due to the time it takes. However, it is still a useful sort for small sets of items. Quick Sort is considered to be more useful in sorting in the real world, since its has quicker results.