(a) Write insertion sort algorithm. Also discuss its time complexity. (b) What is quick sort technique? Using quick sort arrange the following elements in ascending order: 26, 5, 37, 3, 61, 11, 59, 15, 48, 19

(a) Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages such as simple implementation, efficient for small data sets, more efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort, adaptive, and stable.

Algorithm Steps:

1. Start from the second element of the array (position 1, as the array index starts from 0).
2. Compare the current element with its predecessor.
3. If the current element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Here is the pseudocode for the Insertion Sort algorithm:

for i from 1 to length(A) - 1 do:
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do:
        A[j + 1] = A[j]
        j = j - 1
    end while
    A[j + 1] = key
end for

Time Complexity:

The time complexity of insertion sort is dependent on the input data. In the worst case, which occurs when the array is reverse sorted, every element has to be compared with all the other elements in the sorted sub-array. In the best case, which occurs when the array is already sorted, the algorithm only makes n-1 comparisons and no swaps.

Case	Complexity
Worst-case	O(n^2)
Average-case	O(n^2)
Best-case	O(n)

The space complexity of insertion sort is O(1), as it only requires a single additional memory space for the key element.

(b) Quick Sort Technique

Quick sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Algorithm Steps:

1. Choose a pivot element from the array.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
3. Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.

The base case of the recursion is arrays of size zero or one, which are in order by definition, so they do not need to be sorted.

The efficiency of the algorithm depends largely on the pivot selection strategy. Common strategies include choosing the first element, the last element, the middle element, or a random element as the pivot.

Quick Sort Example:

Let's sort the given array using quick sort:

26, 5, 37, 3, 61, 11, 59, 15, 48, 19

We will choose the last element as the pivot for simplicity.

1. Initial array: 26, 5, 37, 3, 61, 11, 59, 15, 48, 19
2. Choose pivot: 19
3. Partition the array around pivot 19:

Elements less than 19: 5, 3, 11, 15

Elements greater than 19: 26, 37, 61, 59, 48

New array: 5, 3, 11, 15, 19, 26, 37, 61, 59, 48

1. Recursively apply quick sort to the sub-arrays:

• Sort 5, 3, 11, 15:

  • Choose pivot: 15
  • Partition: 5, 3, 11 | 15
  • Recursively sort 5, 3, 11:
    • Choose pivot: 11
    • Partition: 5, 3 | 11
    • Recursively sort 5, 3:
      • Choose pivot: 3
      • Partition: 3 | 5
      • Both sub-arrays are now sorted.
  • Concatenate: 3, 5, 11, 15

• Sort 26, 37, 61, 59, 48:

  • Choose pivot: 48
  • Partition: 26, 37 | 48 | 61, 59
  • Recursively sort 26, 37:
    • Choose pivot: 37
    • Partition: 26 | 37
    • Both sub-arrays are now sorted.
  • Recursively sort 61, 59:
    • Choose pivot: 59
    • Partition: 59 | 61
    • Both sub-arrays are now sorted.
  • Concatenate: 26, 37, 48, 59, 61

1. Concatenate all sorted sub-arrays:

3, 5, 11, 15, 19, 26, 37, 48, 59, 61

The array is now sorted in ascending order.

Time Complexity:

The time complexity of quick sort in the average and best cases is O(n log n), but it degrades to O(n^2) in the worst case, particularly when the smallest or largest element is always chosen as the pivot. However, with good pivot selection methods, the worst-case scenario is less likely to occur, and the algorithm performs well on average.

Case	Complexity
Worst-case	O(n^2)
Average-case	O(n log n)
Best-case	O(n log n)

The space complexity of quick sort is O(log n) due to the recursive function calls.