Assignment-4 Sorting Algorithms Solution

This assignment consists of six major tasks, the first one involves implementing the heap data structure. Tasks 2-5 involve the implementation of different sorting algorithms while the last one pertains to the application of one of the sorting algorithms. For tasks 2 to 5, we have provided some code in generator.cpp, which generates a sequence of numbers between 1 and n. Based on user input, the sequence will be random, sorted, reverse sorted or almost sorted. For each task, you have to sort this input. You will be required to sort these numbers in arrays, as well as lists for some of the algorithms. Make sure that your algorithm works for negative values as well. 
 
The header file sorts.h has declarations for all the sort functions. You must implement all of these functions in sorts.cpp. You may also define additional functions if it aids you in any way. But you must implement the functions already declared in sorts.h. The generator.cpp file contains functions that generate random input cases so that you can observe your implementation. You are also given a standard implementation of the Linked List data structure in the list.h and list.cpp files. You must write all your code in sorts.cpp. No other file should be altered. After writing your code in sorts.cpp, just compile generator.cpp and run. For final testing you are provided individual test cases for each sorting algorithm. 
 
Every function that you must implement should accept an integer vector as input. The implementations must internally duplicate the vector into an array or linked list (as mandated by each task). Once the sorting is complete, the numbers must be put back into a vector in sorted order and that vector should be returned e.g., for Task 2, in InsertionSort(), you should take all elements present in the input vector, put them into an array and then apply the insertion sort algorithm. After sorting, put all the elements from the array into a vector (you can overwrite into the old vector or store in a new vector) and then return that. 

Task 1: Heap Data Structure 
In this task, you are expected to implement the heap data structure. You are provided the heap.h, heap.cpp and heap_test.cpp files. You are only required to make changes to the “heap.cpp” file and you are expected to implement all the methods in that file. You can test your implementation using the heap_test.cpp file. You will be using this implementation of heap data structure in task 5. 
 
    
Task 2: Insertion Sort (array based)  
For this task, implement the in-place Insertion Sort algorithm using an array. 
 
      
Task 3: Mergesort (using linked lists): 
In this task, you need to implement the Merge sort algorithm using a linked list 
  
 
Task 4: Quicksort (both array and linked lists) 
Implement both the in-place array-based as well as the linked list method of Quicksort. 
 
    I. For the array-based implementation, use the following strategies for selecting a pivot: 
            a. First element of the array as the pivot 
            b. Then use the median-of-three pivot 
            c. Finally, use the last element of the array as pivot Use the strategy with lowest running time in your test. 
 
    II. For the linked list based implementation, use a random pivot. 
 
     Essentially this task includes two sub-tasks: 
        (i) Array based implementation – using the above mentioned 
     techniques 
        (ii) Linked List implementation – using a random pivot. 
     

Task 5: Heapsort (using heaps) 
For this task, implement the array based Heapsort algorithm using the heap implementation in task 1. 
      
Task 6: Queen of all sorts
Your classmate in CS202 claims that he has invented a sorting algorithm Queen of all sorts that is much faster compared to the algorithms taught in class.  He claims that his algorithm can sort a list of integers in O(list size). He also claims that his algorithm if modified a little can maintains all the original duplicate values. Steps for his algorithm are given below.
He creates a very large array arr of some size k;
He iterates over the list to be sorted and put each list element p at index p in array arr.
If p is greater than the size of arr he creates another array arr’ of size p+1, Copy all the elements in new array and put the element p at index p in new array.
After the complete iteration on the list he iterates over  arr’ from left to right and put each element that appears in arr’ in a list queen_of_all_sorts.
He claims that this list is sorted and takes O(n) time .

Your tasks:
Is his claim that his algorithm runs in O(n) true? Explain. If not what is the original time complexity in terms of Big-O?

If it is not true how will you modify the algorithm so that it actually produces a sorted list.

Explain how will you modify it for handling duplicates? If his claim is not true then explain why?

Your classmate presented his sorting algorithm to Dr.Ihsan. He points out that choice of the array arr(in the above part) size is very inefficient. Note: All other problems in above part are also present.
You are required to implement a fully modified version of his algorithm containing these Properties.
    • Your Algorithm produces a sorted list
    • Sorted list contains duplicates as given in input list.
    • It has much better implementation for choice of array size for  arr and arr’. 


The following test cases require flags: 
g++ test_insertion_sort.cpp -pthread –std=c++11 g++ test_merge_sort.cpp -pthread –std=c++11 g++ test_quickarray_sort.cpp -pthread –std=c++11 g++ test_quicklist_sort.cpp -pthread –std=c++11 g++ 
test_heap_sort.cpp -pthread –std=c++11 
test_queen_all_of_sorts.cpp -pthread –std=c++11 
test2_queen_of_all_sorts.cpp -pthread –std=c++11 
 
 
BEST OF LUCK