Sorting Algorithms (Bubble and Shuttle)

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

 

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)

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.

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. 

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.

 Generally recursive the algorithm will stop when a value is 0 or 1 in the list.