Question

Insertion sort, which is one of the other sorting techniques introduced in this chapter. Create an algorithm to implement an insertion sort.

Methods for sorting data files. You should produce a brief report discussing the different sorting options that can be used.

Answer 1

Part 1

Algorithm for Insertion Sort

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Part 2

If the files containing data are small and can be brought to the main memory then we can use any standard sorting algorithms like:

• Selection Sort
• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort

But if the data files are larger than the capacity of the main memory of the system then we can use External Sorting.

Algorithm for sorting data files using External Sorting

1. Read input_file such that at most ‘run_size’ elements are read at a time. Do following for the every run read in an array.

2. Sort the run using MergeSort.

3. Store the sorted array in a file invidually.

4. Merge the sorted files using merge k sorted arrays