GCSE Computer Science Sorting Algorithms Revision Notes

Computational Thinking Fundamentals

Ever wondered how programmers tackle massive problems without getting overwhelmed? It all starts with computational thinking - basically breaking down complex challenges into manageable chunks.

An algorithm is simply a set of instructions for solving a problem, like a recipe for your favourite dish. You can write these down using flowcharts (visual diagrams with symbols and arrows) or pseudocode (simplified English that looks a bit like real programming code).

Algorithmic thinking helps you approach problems logically so you can reuse solutions later. Abstraction means stripping away unnecessary details - think of the London Underground map that shows tube lines but ignores roads and rivers. Decomposition involves breaking big problems into smaller, manageable pieces that you can tackle one at a time.

Quick Tip: When facing a complex problem, always ask yourself: "What details can I ignore?" and "How can I split this into smaller parts?"

The beauty of these methods is that once you solve a sub-problem, you can often reuse that solution in other projects, saving you loads of time later on.

Search and Sort Algorithms

Finding stuff quickly in lists is crucial for programming, and there are two main search methods you need to know. Linear search checks every item one by one until it finds what you're looking for - imagine flipping through every page of a dictionary. It's simple but painfully slow for large lists.

Binary search is much cleverer and faster, but only works on sorted lists. It starts in the middle, decides whether to look left or right, then repeats this process, halving the search area each time. Think of it like the "higher or lower" guessing game.

For sorting, bubble sort compares neighbouring items and swaps them if they're in the wrong order, repeating until everything's sorted. The largest values "bubble up" to the end. Insertion sort works faster by sorting one item at a time into its correct position.

Merge sort is the speed champion - it splits lists in half repeatedly until each piece has one item, then merges everything back together in the correct order. It's more complex but much more efficient for large datasets.

Exam Tip: Always explain HOW each sorting algorithm works step-by-step, not just what it does!

Flowcharts and Pseudocode

Flowcharts use specific symbols that every programmer recognises. Terminal symbols (ovals) mark start and stop points, process boxes (rectangles) handle calculations, decision diamonds ask yes/no questions, and input/output shapes (parallelograms) deal with data coming in or going out.

Pseudocode lets you focus on the logic without worrying about exact programming syntax. It's like writing instructions in structured English that any programmer can understand and convert to real code later.

Variables are temporary storage boxes in memory where you can keep values like numbers or text. You name them using snake_case (words separated by underscores, like MIN_AGE). Constants are values that never change during the program and are usually written in UPPERCASE.

Why use constants instead of variables? They prevent accidental changes to important values and clearly show other programmers that this value should stay the same. Remember though - constants can be changed by programmers before the program runs, just not while it's running.

Remember: Good variable names make your code much easier to understand later!

Data Types and Operations

Every piece of data has a specific type that determines what you can do with it. Integers are whole numbers, floats (or real numbers) have decimal points, characters are single letters or symbols, strings are sequences of characters, and booleans are simply true or false.

Mathematical operations follow BIDMAS order: Brackets, Indices (powers), Division, Multiplication, Addition, Subtraction. MOD finds remainders $17 MOD 3 = 2$, whilst DIV does integer division without decimals $17 DIV 3 = 5$.

Comparison operators let you test relationships: > (greater than), >= (greater than or equal), < (less than), <= (less than or equal), == (equal to), and != (not equal to). These return boolean values.

Subprograms are reusable chunks of code that appear as boxes with lines on both sides in flowcharts. They make programs easier to debug and maintain because you can fix problems in smaller, isolated sections rather than hunting through massive blocks of code.

Key Point: Understanding data types prevents errors - you can't do maths with text unless you convert it first!

Programming Constructs and Casting

All programs are built from three fundamental constructs. Sequence means instructions execute one after another in order. Selection uses IF statements to choose different paths based on conditions - like choosing whether to take an umbrella based on weather forecasts.

Iteration means repetition, and there are three types you'll use constantly. FOR loops repeat a specific number of times, WHILE loops continue as long as a condition stays true (checked at the start), and DO-UNTIL loops keep going until a condition becomes true (checked at the end).

Nested IF statements are IF statements inside other IF statements, allowing complex decision-making. Think of them as asking follow-up questions based on previous answers.

Casting (or type conversion) changes data from one type to another using special functions. int() converts strings to integers, float() creates decimal numbers, str() turns numbers into text, and bool() creates true/false values. ASC() and CHR() convert between characters and their ASCII number codes.

Pro Tip: Always cast user inputs before using them in calculations - inputs are always strings initially!

String Manipulation and Control Structures

User inputs always start as strings, so you'll need to convert them before doing calculations. String functions are incredibly powerful for text processing. str.length tells you how many characters are in a string, str.substring(start, end) grabs specific portions, whilst str.left$n$ and str.right$n$ extract characters from either end.

The concatenation operator (+) joins strings together. You can change case using .upper and .lower functions. Remember that spaces count as characters too!

Switch/case statements handle multiple options more elegantly than long chains of IF statements. They test one variable against several possible values and execute different code for each case, with a default option for unexpected inputs.

Random numbers require importing special libraries. In pseudocode you might write random(0, 100), whilst Python uses random.randint(0, 100) after importing the random library.

Comments (marked with # in Python) explain your code to other programmers and your future self. They're ignored when the program runs but are essential for maintaining and understanding code later.

Remember: Good comments explain WHY you're doing something, not just what you're doing!

Debugging with Trace Tables

Trace tables are your best friend for finding sneaky logic errors in programs. You create columns for each variable and track their values line by line as the program executes. It's like being a detective following clues through your code.

These tables help you determine what a program will output, spot errors in your logic, and understand how algorithms work. Make columns for variables in the order they appear, and only fill in values when they actually change.

Syntax errors break the rules of the programming language (like missing quotation marks) and stop your program from running at all. The compiler will catch these and give you error messages.

Logical errors are trickier - your code follows the syntax rules but doesn't do what you intended. For example, dividing by 3 instead of 2 when calculating an average of two numbers.

Modern IDEs (Integrated Development Environments) can automate trace table functionality with breakpoints and variable watching, but understanding the manual process helps you think like a programmer.

Debug Like a Pro: When stuck, add print statements throughout your code to see what's actually happening with your variables!

Working with Arrays

Arrays are like storage containers that hold multiple items of the same data type under one name. Think of them as numbered boxes where you can store related information like usernames or scores.

Array indexes start at 0, not 1 - this catches many beginners out! To access the first item, you use arrayName[0]. The .length property tells you how many items are stored.

Arrays have fixed lengths - if you need more space, you must create a new larger array and copy everything across. Python sidesteps this limitation by using lists instead, which can grow and shrink as needed.

You can loop through arrays easily using FOR loops to process every item. This makes tasks like searching through usernames or calculating averages much simpler than creating separate variables for each piece of data.

Arrays make linear searches straightforward - just loop through each index comparing values until you find what you're looking for. They're also essential for implementing sorting algorithms effectively.

Array Advantage: Instead of creating username1, username2, username3... you can store everything in one array and access it with a simple loop!

Subroutines and Scope

Subroutines break large programs into manageable, reusable chunks - they're like mini-programs within your main program. Functions return values after processing (like calculating a square root), whilst procedures execute code but don't return anything.

The main advantages are enormous: you can test each piece separately, multiple programmers can work simultaneously, code can be reused across projects, and maintenance becomes much easier. Instead of hunting through thousands of lines, you just fix the specific subroutine that's causing problems.

Scope defines where variables can be used. Global variables are accessible anywhere in your program, like public information everyone can see. Local variables only exist within their specific subroutine and disappear when that subroutine finishes.

Think of functions as houses with one-way windows - you can see global variables from inside, but outsiders can't see your local variables. This prevents naming conflicts and keeps subroutines self-contained.

Parameters are the inputs you pass to functions - they're listed in the brackets when you define or call the function. They act like local variables within that subroutine.

Best Practice: Use local variables whenever possible to keep your subroutines independent and reusable!

Advanced Subroutine Concepts

The power of subroutines really shines in large projects where many programmers collaborate simultaneously. Each person can work on different subroutines without interfering with others, dramatically reducing development time.

Local variables are your secret weapon for creating truly portable subroutines. Since they only exist within their function, you never have to worry about variable name conflicts when reusing code in different projects.

When you write something like sum(a, b), the a and b are called parameters - they define what inputs your function expects. These parameters behave like local variables inside the function.

Global variables can be seen and used from within functions, but good programming practice suggests you shouldn't change them directly from inside subroutines. Use the global keyword in pseudocode when you need to explicitly work with global variables.

Subroutine libraries let you build collections of useful functions that you can import into any project. This is how professional programmers avoid reinventing the wheel - they build up toolkits of proven, tested code over time.

Professional Tip: Treat each subroutine like a black box - if you know what goes in and what comes out, you shouldn't need to worry about the internal details!

Program maintenance becomes infinitely easier when problems are isolated to specific subroutines rather than scattered throughout massive files.