Sorting

Sorting

1. Bubble sort

   • 1. Take the first element and second element from the list 2.compare them 3. IF element 1> element 2 THEN -swap them, ELSE do nothing. This is if you are sorting in ascending order
     • At the end of one pass through the list, the largest item is at the end of the list​
       • This is repeated until the items are sorted
   • to work out the number of comparisons. In a list of 10 items there will be 100 comparisons- to find the number of comparisons it is n squared, where n is the number of items in the list
   • Comparing bubble sort and merge sort
     • Merge sort is more efficient
     • Bubble sort is slow and inefficient for more than a few items - a list of n items takes,rougly speaking nsquared comparisons
     • The merge sort requires more memory to store the sublists, and with a very large number of items this can be a disadvantage

2. Merge sort

   • A list is split into two individual lists, these are then combined (2 lists at a time)
     • split all elements into individual lists
       • compare the first element in both lists
         • put the smallest into a new list
           • Compare the next element of the 1st with the second elment of the 2nd list
             • Put the smallest into a new list
               • repeat until merged
   • Recurisve

Bilder und Dateien der Mindmap