SORTING ALGORITHMS

1. process of arranging or ordering a collection of items (either ascending or descending order)

   1. ordering or elements is based on sort key

2. Bubble sort

   1. larger values “bubble” to the top/end of the list

   2. each element is compared and swapped so there are multiple swaps in a single iteration

   3. there will be n - 1 passes where n is the number of elements in the list

   d. Implementation:

   def bubble_sort(arr): 
   	# there will be n - 1 iterations where n is the length of the array
   	for i in range(len(arr) - 1, 0, -1):
   		# inside each iteration there are n - 1 comparisons happening.
   		# after each iteration we cut down 1 comparison since biggest element
   		# would be at the end of the array.
   		for j in range(i):
   			if arr[j] > arr[j + 1]: 
   				arr[j], arr[j + 1] = arr[j + 1], arr[j]
   	return arr
   
   # optimised bubble sort which stops sorting the elements when no swaps occur
   def optimised_bubble_sort(arr): 
   	# there will be n - 1 iterations where n is the length of the array
   	for i in range(len(arr) - 1, 0, -1):
   		swap = False
   		# inside each iteration there are n - 1 comparisons happening.
   		# after each iteration we cut down 1 comparison since biggest element
   		# would be at the end of the array.
   		for j in range(i):
   			if arr[j] > arr[j + 1]: 
   				arr[j], arr[j + 1] = arr[j + 1], arr[j]
   				swap = True
   		if not swap:
   			return arr
   	return arr
   

   e. time complexity = O(n^2)

3. Selection sort

   1. like bubble sort, makes mulitple comparisons over the sequence

   2. makes a single swap after each pass

   3. how it works:

      1. find the smallest element from the array and place it in the beginnning

      2. repeat the process by finding the next smalleset element and so on

      3. process finishes when all the elements are in sorted order

   4. implementation:

      def selection_sort(arr): 
      	# len(arr) - 1 is done since it is assumed that the last element of the
        # array is automatically swapped
      	# number of passes for selection sort is n - 1 where n is length of array
      	for i in range(len(arr) - 1): 
      		min_value = i
      		for j in range(i + 1, len(arr)): 
      			if arr[min_value] > arr[j]:
      				min_value = j
      		
      		if min_value != i: 
      			arr[min_value], arr[i] = arr[i], arr[min_value]
      	return arr
      
      # selection_sort by specifying order, either ascending or descending
      def improved_selection_sort(arr, order):
      	if order.upper() == "ASC":
      		for i in range(len(arr) - 1):
      			min_value = i
      			for j in range(i + 1, len(arr)):
      				if arr[i] > arr[i + 1]:
      					min_value = j
      	
      			if min_value != i: 
      				arr[i], arr[min_value] = arr[min_value], arr[i]
      		return arr
      
      	elif order.upper() == "DESC":
      			for i in range(len(arr) - 1):
      			max_value = i
      			for j in range(i + 1, len(arr)):
      				if arr[i] < arr[i + 1]:
      					max_value = j
      	
      			if max_value != i: 
      				arr[i], arr[max_value] = arr[max_value], arr[i]
      		return arr
      

   5. better than bubble sort since there is only 1 switch needed

   6. more efficient since every time you iterate over the list the number of elements is decreasing

   7. time complexity = O(n ^ 2)

4. Insertion sort

   1. maintains a collection of sorted items and a collection of items to be sorted in the sequence

   2. how it works:

      1. assumes first element is in proper position

      2. compare the current element to the previous element

      3. If the current element is less than the previous element, compare it to the next previous element and so while making the necessary swaps

   3. implementation

      def insertion_sort(arr): 
      	# range starts from 1 since we assume first element is sorted
      	for i in range(1, len(arr)): 
      		while arr[i - 1] > arr[i] and i > 0: 
      			arr[i], arr[i - 1] = arr[i - 1], arr[i]
      			i = i - 1
      	return arr
      
      # insertion sort with values printed out at each step 
      def insertion_sort(arr): 
      	print("INSERTION SORT")
      	print(f"pass 0\t{arr}")
      	# range starts from 1 since we assume first element is sorted
      	counter = 1
      	for i in range(1, len(arr)):
      		while arr[i - 1] > arr[i] and i > 0: 
      			arr[i], arr[i - 1] = arr[i - 1], arr[i]
      			i = i - 1
      			print(f"pass {counter}\t{arr}") 
      		counter += 1
      	return 
      

   4. same complexity as bubble and selection sort but can be a little bit more efficient than those 2 algorithms

   5. time complexity = O(n^2)