Why is a swap usually more expensive than a comparison?

A swap writes to memory three times while a comparison only reads two values. Writing is slower than reading on most storage.

How many assignments does one exchange of two array elements require?

One exchange requires three assignments using a temporary variable. The temporary holds the first value while the second is copied over it.

How does the number of passes affect the efficiency of a sorting algorithm?

Each pass costs a full sweep of comparisons, so fewer passes means less work. An algorithm that finishes in one pass over sorted data is far more efficient.

Eduqas A-Level Computer Science A500QS

Data Structures: Arrays, Records and Hash Tables

Topic overview One-dimensional arrays and indexing Two- and three-dimensional arrays Manipulating arrays: insertion, deletion and searching Records and fields Arrays of records and record manipulation Hash tables, hashing and collisions Choosing and justifying a data structure

Stacks, Queues, Linked Lists and Trees

Topic overview Stacks: push, pop and the stack pointer Implementing a stack in an array Queues: enqueue, dequeue and pointers Circular queues and priority queues Linked lists: nodes, pointers and the free list Binary trees: nodes, roots and leaves Traversing linked lists and trees

Boolean Logic and Simplification

Topic overview AND, OR and NOT truth tables XOR, NAND and NOR truth tables Truth tables for combined Boolean expressions Boolean identities and rules De Morgan's laws Simplifying Boolean expressions Logical operators in programs, masking and encryption

Algorithms, Pseudo-Code and Programming Constructs

Topic overview Algorithms and how they are defined Pseudo-code conventions Flowcharts and flowchart symbols Sequence and selection Repetition: count-controlled and condition-controlled loops Counts, totals and rogue values Tracing, altering and writing algorithms

Variables, Scope, Parameters and Identifiers

Topic overview Variables and constants Self-documenting identifiers Annotation and program layout Scope of variables: local and global Lifetime of variables Procedure calling, parameters and return values Call by value and call by reference

Recursion and Modular Programming

Topic overview Recursion and the base case How recursive calls use the stack Recursive algorithms: factorial and Fibonacci Recursion compared with iteration Integer division with DIV and MOD Standard functions and standard modules User defined subprograms and modular design

Sorting Algorithms

Topic overview Why a variety of sorting algorithms is needed Bubble sort Insertion sort Quicksort Comparisons, exchanges and passes Storage space and sorting efficiency Writing and altering sort algorithms

Searching and Shortest-Path Algorithms

Topic overview Linear search Binary search Comparing linear and binary search Graphs, weights and the shortest-path problem Dijkstra's shortest-path algorithm Tracing a shortest-path algorithm by hand Choosing the right searching technique

Big O Notation and Algorithm Efficiency

Topic overview What Big O notation measures The common complexity classes Time complexity of the sorting algorithms Space complexity and sorting in place Time complexity of linear and binary search Deriving the complexity of a given algorithm Comparing algorithms that do the same task

Validation, Verification and Testing

Topic overview Validation and verification compared Types of validation check Implementing validation in an algorithm Verification techniques Validation and verification of data in databases Choosing test data Dry running, trace tables and identifying errors

Data Compression

Topic overview What data compression is and why it is used Lossless compression Lossy compression Run-length encoding Dictionary and Huffman coding Measuring compression: ratio and saving percentage Choosing a compression method

Programming Paradigms and Computer Languages

Topic overview Programming paradigms and where each is used Procedural programming Event-driven and visual programming Mark-up languages Object-oriented programming: objects, classes and methods Ambiguity in natural language and the standardisation of languages Backus-Naur form and syntax diagrams High-level and low-level languages, and choosing one

Systems Analysis, Maintenance and Documentation

Topic overview Waterfall, Agile and approaches to systems development The feasibility study, budgets and time scales Methods of investigation Abstraction, decomposition and data flow diagrams Selecting suitable hardware and software Acceptance testing and methods of changeover Perfective, adaptive and corrective maintenance Backup and recovery procedures User and maintenance documentation

System Design and Human-Computer Interaction

Topic overview Approaches to communicating with a computer Types of user interface Natural language interfaces Ambiguity in spoken input Designing an interface for its users The design review Evaluating a computer-based solution

Software Engineering Tools and Translators

Topic overview Software tools for the software engineering process Software packages in analysis, specification, design and testing Integrated development environments Debugging tools Program version management Compilers, interpreters and assemblers The stages of compilation Translation errors and execution errors

Computing, Society and the Law

Topic overview Social and economic change from computing Moral and ethical consequences Cultural change and the digital divide Codes of conduct and professional behaviour The effect of computers on employment Data protection and privacy law Computer misuse, copyright and freedom of information

Computer Architecture, the Processor and Assembly Language

Topic overview Hardware elements and how they are connected Von Neumann architecture and the stored program concept The processor: control unit, ALU and registers Types of memory: RAM, ROM and virtual memory Cache memory and locality of reference The fetch-execute cycle and its registers Parallel processing and the limits to parallelisation Assembly language and executing a program

Input, Output and Secondary Storage

Topic overview Input devices and how data is captured Output devices and how results are presented Choosing input and output devices for a situation Voice input, dictation and voice print recognition Magnetic, optical and solid state storage Comparing secondary storage for a purpose Disc organisation, fragmentation and defragmentation

Networks, Protocols and the Internet

Topic overview Networks, LANs and WANs Network topologies and connection hardware Networking standards and the layered model IP addressing, TCP and UDP Application protocols: HTTP, FTP, SMTP, IMAP and DHCP Handshaking and establishing a connection Wireless hardware and wireless technologies The internet and connected mobile devices

Data Transmission and Network Performance

Topic overview Serial and parallel transmission Simplex, half duplex and full duplex Multiplexing and sharing a channel Circuit, message and packet switching Packets, headers and packet contents Network collisions and collision detection Routing traffic on a network Calculating transfer rates and lowest cost routes

Number Systems and Binary Arithmetic

Topic overview Bits, bytes and words Binary and denary place value Hexadecimal notation Storing characters and numbers in binary Binary addition and subtraction Two's complement and sign and magnitude Logical and arithmetic shifts Overflow and underflow

Data Types, Characters and Floating Point

Topic overview Primitive data types Storage requirements for each data type ASCII and standardised character sets Unicode and multilingual encoding Floating point form: mantissa and exponent Converting between real numbers and floating point Integer and floating point compared Truncation, rounding and accuracy

Files, Records and File Organisation

Topic overview The purpose of files in data processing Files, records and fields Fixed and variable length fields and records Master files and transaction files Serial and sequential file access Indexed sequential access and multi-level indexes Direct access and hashing algorithms Overflow handling and file reorganisation File security, backups, generations and archiving

Databases, Normalisation and Entity Modelling

Topic overview Data consistency, redundancy and independence Relational databases and other database models Primary keys, foreign keys and indexes First normal form Second normal form Third normal form Entity relationship modelling User views and turning data into information

SQL, Big Data and Distributed Systems

Topic overview Query languages and the purpose of SQL Creating tables: CREATE TABLE, data types and keys Retrieving data with SELECT, FROM and WHERE Comparison operators, IN, AND, OR and sub-queries Sorting, grouping and aggregate functions Inserting, updating, deleting and joining data The DBMS, the data dictionary and distributed databases Big Data, data warehousing, data mining and predictive analytics

The Operating System and Its Modes

Topic overview The need for an operating system and the role of the kernel Managing peripherals, processes and memory protection The user interface and the layers between user and hardware Directory structures and file attributes Utility software Batch processing, real time control and real time transaction systems Types of operating system: single-user, multi-user, multi-tasking and multi-programming Designing an interface for different users and environments

Interrupts, Memory Management and Scheduling

Topic overview What causes an interrupt Interrupt handling and the interrupt service routine Interrupt priorities and how they are allocated Partitioning main memory Methods of data transfer between processor and devices Buffers and double buffering High level scheduling, processor and device allocation Process states, time-slicing, polling and threading

Types of Software System

Topic overview Open source, bespoke and off-the-shelf software Safety-critical systems Computers in weather forecasting Computer aided design and computer generated graphics Robotics and automation Control systems Expert systems The internet, intranets and search engines

Data Security, Cryptography and Attack

Topic overview Online updating and the integrity of shared files Dangers of holding personal data Clerical procedures, access levels, passwords and write protection Cryptography: its purpose, and symmetric and asymmetric keys Hashing, digital signatures and certificates Caesar and Vernam ciphers and comparing cipher strength Biometric technologies and their limitations Threats, damage and contingency planning Malicious software, hacking and penetration testing

Sorting Algorithms

Comparisons, exchanges and passes

3 things to know
Component 1

Overview

Comparison in a sorting algorithm, exchange in a sorting algorithm and pass through the data.

What you need to know

Answer each one before you reveal it.

Your recallNot started

Key term

What is a comparison in a sorting algorithm?

Key term

What is an exchange in a sorting algorithm?

Key term

What is a pass through the data?

Questions from this subtopic

Each one with the model answer underneath.

1
What is a comparison in a sorting algorithm?
Model answer
A comparison is a single test of one data item against another to decide their order. The count of comparisons is a common measure of sorting effort.
2
What is an exchange in a sorting algorithm?
Model answer
An exchange is a swap of two data items into each other's positions. Each exchange normally needs three assignments and a temporary variable.
3
What is a pass through the data?
Model answer
A pass is one complete sweep through the list being sorted. A bubble sort makes repeated passes until no swaps occur.
4
Why is a swap usually more expensive than a comparison?
Model answer
A swap writes to memory three times while a comparison only reads two values. Writing is slower than reading on most storage.
5
How many assignments does one exchange of two array elements require?
Model answer
One exchange requires three assignments using a temporary variable. The temporary holds the first value while the second is copied over it.
6
How does the number of passes affect the efficiency of a sorting algorithm?
Model answer
Each pass costs a full sweep of comparisons, so fewer passes means less work. An algorithm that finishes in one pass over sorted data is far more efficient.

See the rest and revise

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.

1Closed book

2Open book

3Closed book

The 3-step method, run for you

Answer cold, learn it, then prove it stuck. Levo tracks the jump between your first attempt and your last.

Data Structures: Arrays, Records and Hash Tables

Stacks, Queues, Linked Lists and Trees

Boolean Logic and Simplification

Algorithms, Pseudo-Code and Programming Constructs

Cram a whole paper in one sitting

Sort every topic into what you know and what you do not, then drill only the weak ones.

KDW to HAT.

decryptsencryptscompresses

Blank Blitz makes facts automatic

Rapid timed gap-fills on the terms and numbers you need to recall without thinking.

AThe two are not the same.

BOpen source refers to the availability of the code.

CMuch open source software is free of charge.

Build It gets the exam shape right

Assemble a full-mark answer from its marking points, in the order an examiner wants them.

Backup means the copy of the data.

TrueFalse

Test It catches misconceptions

Spot the fault in a statement. The traps are the mistakes students actually make.

721941163128510

Brain Breaks between sessions

Short focus games to reset attention, so the next set lands better than the last.

Every question in Sorting Algorithms, on a schedule.

Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.

Start revising, £5 a month See how the method works

Or £46 a year, about £3.83 a month. Cancel anytime.