Searches and sorts

• How does the inner while loop function in the bubble sort algorithm?

  It iterates through the array and swaps adjacent elements if they are out of order
• def bs (array):

  moreswaps =TrueDef bs (array):

  while….

  the purpose of this code is to set up a function and to set up a Boolean flag to determine if more swaps are needed ,which then tells the while loop whater to do another pass
• While moreswaps == True :

  moreswaps are needed= False

  the purpose of this code is to determine if it needs another pass, and then to reset the Boolean flag so it can get out of the loop if no more passes are needed
• ptr =0

  while ptr < end:

  comp += 1


  the purpose of this code is to assign ptr a value of 0, and check if there needs to be a comparison, it also increments the comp counter by one to keep track of the number of comparisons
• If array[ptr]>array[ptr+1]:


  The purpose of this is to compare the two values to check if it needs to switch
• Temp = array[ptr+1]

  array[ptr+1] =array[ptr]

  array[ptr] =temp

  moreswaps =True

  swaps+= 1


  The purpose of this is to actually switch the values by using a temporary variable to keep one of the values,as well as changing the Boolean flag to make such the program loops again, it also increments swaps by one.
• End if

  ptr +=1

  This is outside the if but inside the inner while loop to increment the pointer
• End while

  end-=1

  this is outside of the inner while but in the outer while and it decrements the end variable by 1 to optimise the amount of swaps that actually need to take place
• End while

  print (“comp:”, comp)

  print(“swap:”, swaps)

  return array

  The purpose of this is to output the comparisons and swaps we did and to return the sorted array to output later on
• Def main():

  array = [25,23,7,10]

  sortedarray= bs(array)

  print(”sorted array:”,sortedarray)

  The purpose of this is to define main as a function

  and to store the unsorted array, the sorted array from the bubble sort function and then it outputs the sorted array
• Def Is(array):

  this is to simply define the function is IS
• for i in range(1, len (array)):

  CV = array [i]

  pos = i

  Th purpose of this code is to start the outer loop. The outer loop makes sure each value in the array is checked
• while pos>0 and array[pos-1]>cv:

  the purpose of this code is to only drop into the inner loop if there is a value before array[pos] and if so is It the bigger number
• while pos >0 and array[pos-1] > CV:

  array[pos] = array[pos-1]

  pos -= 1

  {end of while}

  the purpose of this code is to check if the value needs moving by the condition of the while loop, then if it drops into the loop to simply move the other value up.then the pos decrements. this will repeat until its compared all the value its needs.
• {end of for}

  return array


  the purpose of this is simply to return the array after is sorted
• main():

  array=[17,21,4,12]

  sorted = IS (array)

  print(“sorted array:”,sorted)

  the purpose of this code is to simply set up what array is being sorted and then it gets sorted and outputed
• how does a binary search work?

  Uses divide and conquer algorithm
• how does a binary search work?

  goes from left to right checking each piece of data until SV is found
• which search uses a pointer

  only a linear
• what search uses Boolean flags


  both
• how does a insertion sort work?

  it inserts a value in a temp variable and then it compares the value to the left and moves it based on the result
• how does a bubble sort work:

  the largest value “bubbles” to the top of until all data is in order
• what sort uses a Boolean flag?


  bubble
• which sort inserts the value into its position

  insertion
• which sort can be optimised with the end changing by 1 each pass

  bubble
• which sort is this:

  def sort (array):

  -for i in range(1,len(array)):

  —CV = array [i]

  —pos = i

  —while pos>0 and array[pos-1]>CV:

  —-array[pos] = array[pos-1]

  —-pos-=1

  —array[pos]=CV

  -return array

  insertion
• what sort is this:

  def sort(array):

  -moreSwaps = True

  —while moreSwaps == “True”:

  —-moreSwaps =False

  —-for i in range (0,len(array)-1):

  ——if array[i]>array[i+1]:

  ——temp = array[i]

  ——array[i]=array[i+1]

  ——array[i+1] =temp

  ——moreSwaps = True

  -return array

  bubble