Sorting

• Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order.
• Sorting is placing data in some specified order,

  typically ascending or descending.
• A sort algorithm is an algorithm used to place

  elements in a data set into a specified order.

  Two classic searching techniques:

  • Selection Sort
  • Bubble Sort

  Note: No matter which algorithm is used, the end result will be the same. Choice of algorithm affects only runtime and memory use. Other more efficient algorithms exist (e.g. Merge sort, Heap sort)
• All of the sorting algorithms we will examine can be implemented as two nested loops:

  • The outer for loop to run the inner loop for each element in to array
  • the inner loop to determine if the element is smaller/larger for new placement in array

  Each completion of the inner loop is called a pass.
• The Selection Sort algorithm creates the sorted sequence one

  element at a time by adding elements to the sorted sequence in order.

  • At each step, the next element to be added to the

  sorted sequence is selected from the remaining

  elements.

  • Because the elements are added to the sorted sequence in order, they are always added at one end.
• How does Selection sort work?

  Array is divided into two parts:

  • sorted one and unsorted one.

  At the beginning:

  • sorted part is empty and unsorted one contains whole array.

  At every step,

  • find minimal element in the unsorted part
  • add it to the end of the sorted one (swap occurs)
  • Algorithm stops when unsorted part becomes empty.
• Selection Sort Characteristics

  • Simple and easy to implement.
  • Inefficient for large lists.
  • List divided into two parts (sorted & unsorted). Select the

  smallest from the unsorted list and add to end of sorted list.

  • After ith iteration, smallest i elements are sorted in increasing

  order in first i positions.

  • For a list of size N, there are a maximum of N-1 swaps.
• What is Bubble Sort?


  The simplest and slowest sort in use.

  The algorithm starts at the beginning of the list and works it way to the end, comparing each element in the list with the one after it. The elements are swapped if they are out of order.

  This process is repeated until a pass is made all the way through the list without swapping any elements.

  This causes larger elements to “sink" to the end of the list and smaller elements “bubble" to the beginning of the list.
• Bubble Sort Characteristics?

  • Larger values “bubble” to the end of the list.
  • On each pass, all adjacent pairs of elements are compared (N-1 pairs).
  • If the pair is in the wrong order, their values are swapped.
  • Maximum of N-1 passes are made for list of N items.
  • If no swaps occurred on a pass then the list is deemed sorted and algorithm can terminate. (Algorithm can stop before N -1 passes are made.)
  • Simple and easy to implement but very inefficient.
  • Not suitable for large lists.
  • After ith pass, largest i elements have “bubbled” to end of list.