Sorting algorithms are needed in order to produce a list in numerical order. this improves efficiency for searching the algorithm
Google sorts webpages by page links (this is how many references a page gets on websites and social media). This process allows webpages to be stored by relevancy.
Bubble Sort
Google sorts webpages by page links (this is how many references a page gets on websites and social media). This process allows webpages to be stored by relevancy.
Bubble Sort
Summary
It works by repeatedly stepping through the
list to be sorted, comparing each pair of adjacent items and swapping them if
they are in the wrong order. The algorithm gets its name from the way smaller
elements “bubble” to the top of the list. This is the least useful sorting algorithm
One final sweep is needed of the whole list so that the list can be checked to see if it is in the right order.
- Has a quadratic order - this is for time complexity of O(n^2)
One final sweep is needed of the whole list so that the list can be checked to see if it is in the right order.
- Has a quadratic order - this is for time complexity of O(n^2)
Advantage – simple to implement.
Disadvantage – inefficient for large lists. The big O time complexity for bubble sort is n^2, this means it is extremely slow.
Description of how a bubble sort works
·
Start from the first element to the last
·
Compare each pair of elements and swap their positions if necessary
·
This process is repeated as many times as necessary, until the array
is sorted (We know when the array is sorted
because there will have been no swaps in the last comparison of all pairs of
elements.)
·
After the first pass the last element of the list is sorted so no need
to compare again.
·
After the
second pass - last two elements sorted, third pass – last three etc…
The larger value will always end up at the end of the list, they will be moved there individually
One final sweep is needed of the whole list so that the list can be checked to see if it is in the right order.
Algorithm for Bubble sort:
Subprogram BubbleSort(aList)
exchanges = True
passnum = length of aList – 1
while passnum > 0 and exchanges == True
exchanges = False
for index = 0 to passnum
if aList[index] > aList[index+1]
exchanges = True
temp = aList[index]
aList[index] = aList[index+1]
aList[index+1] = temp
passnum = passnum – 1
Insertion Sort
Summary
We can divide a list into a sorted part and
unsorted part. Initially the first element is the only
element
in the sorted part then as you work through sorting the second to the last element
the sorted part grows. An insertion sort works by taking elements from the
unsorted part and inserting them in their correct position into the sorted
part. It is similar to the bubble sort however we do not mover step by step, you gather one element and then sort it to its exact place through swapping if needs be.
Advantages – Insertion sort is a simple
sorting algorithm and relatively efficient for small lists and mostly-sorted
lists. It is faster than the bubble sort. It’s relatively fast for adding
a small number of new items periodically. Large saving compared to the bubble sort.
Reasonably simple code. Good for smaller lists. Works very well when the lists is nearly sorted
Very memory efficient - it only needs one extra storage location to make room for the moving items.
Very memory efficient - it only needs one extra storage location to make room for the moving items.
Disadvantage – inefficient for large lists.
The Big O time complexity of insertion sort is O(n^2)
Description of how an insertion sort works:
It works the way you might sort a hand of
playing cards:
·
We start with an empty left hand [sorted list] and the cards face down on the
table [unsorted list].
·
Then remove one card [element] at a time from the
table [unsorted list], and insert it into the correct
position in the left hand [sorted list].
·
To find the correct position for the card, we
compare it with each of the cards already in the hand,
from right to left.
Note that at all times, the cards held in the
left hand are sorted, and these cards were originally the top cards of the pile
on the table.
Quicksort
Summary
A quicksort is a recursive sorting algorithm.
The idea behind quicksort is to divide and conquer. First split the list into
two parts, one part containing values less than a pivot value, the other containing
values greater than this pivot value. In the algorithm below the first item in
the unordered list is used as the pivot value. The same process is now applied
to each part list, repeatedly, until the parts contain just one value. Joining
the part lists back together produces the ordered list. This is a divide and conquer algorithm!
Works by repeated partitioning the list, it chops up the list based on a pivot (a element/ point in the list)
The best pivot is the middle value however that takes a very long time so usually in quick sort it is a random value.
When the pivot is selected all the elements on the left will be less than the pivot and all the elements on the right will be greater than the pivot.
Work in from each end of the list to put the numbers on the correct side of the pivot.
Works by repeated partitioning the list, it chops up the list based on a pivot (a element/ point in the list)
The best pivot is the middle value however that takes a very long time so usually in quick sort it is a random value.
When the pivot is selected all the elements on the left will be less than the pivot and all the elements on the right will be greater than the pivot.
Work in from each end of the list to put the numbers on the correct side of the pivot.
Advantages – can be much faster than bubble sort and insertion sort.
Can work well on sorting through large lists.
Disadvantage – This process is inefficient in terms of memory
for very large lists due to recursion (the stack can grow large with all the
return addresses, variables etc. that have to be stored for each recursive
call). Sometimes it can grow too large causing a stack overflow (out of stack
memory) error.
Time complexity of Big O is O(nlogn)
Description of how a quicksort works:
·
If the first
pointer is less than the last pointer (if there are elements in the list) then:
·
Pick an item
within the list to act as a ‘pivot’. The left-most item is a popular choice.
·
Split the
list into two parts – one list with items equal to or larger than the pivot item
and the other list contains items smaller than the pivot.
·
Repeat this
process of splitting each list into two parts until all the parts contain just
one value.
This is where recursion is used to quicksort
until there is only one element left in the list.
