Sorting Algorithms

Click to see the rest of the Algorithms section :

Sorting algorithms in computer science range from very simple, to very complex and there are two main sorting algorithms taught at GCSE. Sorting is the term applied to taking the items in an array and arranging them in either ascending (alpha / numerical order) or descending (reverse) order. It’s useful at this stage to make sure that you know what the terms data set, array, and items are.

GCSE computer science

The first of these sorting algorithms to be discovered was Bubble Sort*.

In this, items are looks at in pairs and swapped in a ‘pass’ of the array which then repeats until no swaps have been made in a full pass. The algorithm for this looks like:

 

Swaps <-- 1

 

WHILE Swaps >0 DO

  Swaps <– 0

  FOR i <– 0 TO LENGTH(myList)-1 DO

     IF myList[i] > myList[i+1] THEN

           Swaps <– Swaps +1

           Temp <– MyList[i]

           MyList[i] <– MyList[i+1]

           MyList[i+1] <– Temp

      END IF

   END FOR

 

*It’s really useful to know how this works, not just for Computer Science, but also for maths!

The second of these sorting algorithms is Insertion Sort. This sorting algorithm is likely to be one that you have seen a number of times before, but haven’t thought about the steps that you have used to implement it.

Imagine that you have a stack of exam papers that you need to put in order of Surname:

  • You hold the unsorted stack (the unsorted portion

  • and put a single paper down (the sorted portion)

  • You take the next paper and compare it to the sorted paper

  • and place (insert) it into the correct place in the sorted pile

  • You continue doing this until no more papers are left unsorted

Exactly the same happens in Insertion Sort, except we need to add in some logic of how to compare each item from highest to lowest in the sorted portion of the list and move them up one at a time to make room.

 

You’ll notice that in each of the algorithms, there is additional logic for moving items around in the array – if you simply moved the item up one you would overwrite another item. Understanding that we use temporary variables to move items around in a list is a large part of the Arrays section in the Programming topic.

Find this page helpful? Share the love on your social media mentioning @TeachAllAboutIT and we’ll enter you in our monthly draw to win a gift voucher for any product on the site!

Share on facebook
Share on google
Share on twitter
Share on linkedin
Share on pinterest
Share on reddit

More For Members

Lesson Plan

Coming Soon!

Presentation

Coming Soon!

Homework

Coming Soon!

Students

Click to revise!

Not a member yet? Sign Up Here

Sign Up For Membership Today

Computer Science Student

Individual Site License
Topic Introduction Pages
Additional Revision Resources
Revision Videos
Exam Question Walkthroughs
Discounted Group Lessons
£2.50 per Month. After your initial payment, your first payment is Free.

Whole School

Whole School Site License (teacher access)
Up to 50 student accounts (£3 per student, per annum for additional students)
Online Topic Lesson Plans
Differentiated Homework Tasks
Monthly Bundle of Downloadable Resources
Discounted Live Lessons
£12.50 per Month.
Number of courses10
iGCSE Computer Science (0984) – Distance Learning
GET IT NOW GET IT NOW