Methodological Instructions

Theme: Sorting methods

Aim: Implementation of Insertion and Bubble sorting algorithms

Assessment criteria

Knowledge

·     Know the complexity of sorting algorithms.

Comprehension

·     Understand the time and space complexities of algorithm

Analysis

·     Compare the insertion and bubble sort algorithms

Language objectives

Learners able to …

• State what the complexity of sorting algorithm is

• Describe the processes of insertion and bubble sorting

Vocabulary and terminology specific to the subject:

Ordered list, unordered list, entry, iteration

Useful expressions for dialogs and letters:

Well, the complexity of an algorithm represented by … .

For example, the logic of swops has its own   … .

Obviously, the sorted data of great convenience for  … . ….. .

Theory

Big O Notation (also known as Big-O Notation) is a mathematical way of describing the limiting behaviours of a function. In other words, it is a way of defining how efficient an algorithm is by how "fast" it will run.

You can work out the time that an algorithm takes to run by timing it:

Dim timer As New Stopwatch()

timer.Start()

For x = 1 to 1000000000

   'count to one billion!

Next

timer.Stop()

' Get the elapsed time as a TimeSpan value. 

Dim el As TimeSpan = stopWatch.Elapsed

' Format and display the TimeSpan value. 

Dim formattedTime As String = String.Format("{0}:{1}:{2}.{3}", el.Hours, el.Minutes, el.Seconds, el.Milliseconds / 10)

Console.WriteLine( "Time Elapsed: " + formattedTime)

   Code Output

Time Elapsed: 0:0:21:3249

However, this isn't always suitable. What happens if you run some code on a 33 MHz processor, and some code on a 3.4 GHz processor. Timing a function tells you a lot about the speed of a computer and very little about the speed of an algorithm.

dim N as integer = 7483647

dim sum as double= 0

for i = 1 to N

   sum = sum + i

loop

console.writeline(sum)

optimised version

dim N as integer = 7483647

dim sum as double =  N * (1 + N) / 2

console.writeline(sum)

П. Questions for self-assessment.

Which is faster: Insertion sort or Bubble sort? Why?

Visual Aids and Materials links.

1.      Slides

2.      https://en.wikibooks.org/wiki/A-level_Computing_2009/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Problem_Solving/Big_O_Notation

Students' Practical Activities:

Students must be able:

·     Compare the insertion and bubble sort algorithms

Скачано с www.znanio.ru