Sorting Flashcards
What is a Bobble Sort
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
How would you sort this numbers
5,4,3,2,1
start with the first number(5) and compare it to the second (4). Move the larger number to the right until it is less then the number on the right
Describe the code for a bubble sort
It is two for loops
1) for loop on the outside (Traverse through all array elements)
2) For loop on inside (Last i elements are already in place)\
Conditional if statement (if arr[j] > arr[j+1] : )
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
What is the runtime characteristics of a bubble sort
Notice the nested for loops O(n^2)
Describe a merge sort
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
It splits the array into it’s smallest elements and slowly combines them unit there are two sorted arrays, and than it sorts the last two array by comparison
Merge sort sudo code
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
Merge sort image
https://www.geeksforgeeks.org/merge-sort/
What is the runtime characteristics of a Merge sort
O(n log n)
Explain how a quick sort works
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1) Always pick first element as pivot.
2) Always pick last element as pivot (implemented below)
3) Pick a random element as pivot.
4) Pick median as pivot.
What is the fastest sort?
quick sort O(n log n)
What is the slowest sort
Bobble Sort O(2^2)
Merge sort B-O number
O(n log n)
