Scribd
Upload
143 views4 pages

2.3.3. Sorting Algorithms-3

The document discusses two standard sorting algorithms: bubble sort and insertion sort. It provides details on how each algorithm works, including pseudocode examples. Bubble sort compares adjacent elements and swaps them if in the wrong order, repeating for all pairs until sorted, taking O(n^2) time. Insertion sort inserts each element into the sorted portion of the array, taking the same O(n^2) time complexity as bubble sort.

Uploaded by

Christine
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
143 views4 pages

2.3.3. Sorting Algorithms-3

The document discusses two standard sorting algorithms: bubble sort and insertion sort. It provides details on how each algorithm works, including pseudocode examples. Bubble sort compares adjacent elements and swaps them if in the wrong order, repeating for all pairs until sorted, taking O(n^2) time. Insertion sort inserts each element into the sorted portion of the array, taking the same O(n^2) time complexity as bubble sort.

Uploaded by

Christine
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

OCR Computer Science AS Level

2.3.1 Sorting Algorithms


Concise Notes

www.pmt.education
Specification:

● Standard algorithms
○ Bubble sort
○ Insertion sort

www.pmt.education
Sorting Algorithms

● Take a number of elements in​ any order ​and output them in a​ logical order
● This is usually ​numerical ​or ​lexicographic ​(phonebook style ordering)
● Most output elements in ​ascending ​order, but can typically be slightly ​altered ​or
their output ​reversed ​in order to produce an output in descending order

Bubble Sort
● Makes ​comparisons and swaps ​between pairs of elements
● The largest element in the unsorted part of the input is said to “bubble” to the top of
the data with each iteration of the algorithm
○ Starts at the first element in an array and compares it to the second
○ If they are in the wrong order, the algorithm ​swaps ​the pair
○ The process is then repeated for every adjacent pair of elements in the array,
until the end of the array is reached
● This is one ​pass ​of the algorithm
● For an array with n elements, the algorithm will perform n passes through the data
● After n passes, the input is sorted and can be returned

A = A
​ rray of data
 
for i = 0 to A.length - 1: 
for j = 0 to A.length - 2: 
if A[j] > A[j+1]: 
swap A[j] and A[j+1] 
return A 
 

● Can be modified to improve efficiency


● A ​flag ​recording ​whether a swap has occurred​ is introduced
● If a full pass is made ​without any swaps​, then the algorithm ​terminates
● With each pass, one​ fewer element needs comparing ​as the n largest elements are
in position ​after the n​th​ pass
● Bubble sort is a​ fairly slow ​sorting algorithm, with a time complexity of ​O(n​)
2​

www.pmt.education
Insertion Sort
● Places elements ​into a sorted sequence
● In the ​ith​
​ iteration of the algorithm the first ​i​elements of the array are sorted
○ Warning: although the ​i​elements are ​sorted​, they are not the ​i​​smallest
elements ​in the input!
● Stars at the​ second element ​in the input, and compares it to the element ​to its left
● When compared, elements are​ inserted into the correct position ​in the sorted
portion of the input to their left
● This continues until the last element is inserted into the correct position, resulting in
a fully sorted array
● Has the same time complexity as bubble sort, ​O(n​ )
2​

A = A
​ rray of data

for i = 1 to A.length - 1: 


elem = A[i] 
j = i - 1 
while j > 0 and A[j] > elem: 
A[j+1] = A[j] 
j = j - 1 
A[j+1] = elem 

www.pmt.education

You might also like