less than a minute
The Java collections framework provides interfaces corresponding to some of the most commonly used abstract data types: List, Map, Set, etc. One abstract data type that is not included is the Multiset, which you will implement in this project.
The Double Ended Queue, or Deque, pronounced “deck”, is an abstract data type that allows elements to be appended and removed from either end of a sequence. The Java collections framework includes a [Deque] (https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html) interface along with several implementing classes. These include the ArrayDeque, implemented using a circular dynamic array, and LinkedList, implemented using a doubly-linked list.
There is no single best sorting algorithm. Quicksort is the fastest known comparison-based sorting algorithm when applied to large, unordered, sequences. It also has the advantage of being an in-place (or nearly in-place) sort. Unfortunately, quicksort has some weaknesses: its worst-case performance is \(\Theta(n^2) \), and it is not stable. Merge sort shares neither of these disadvantages: it is stable and it requires \(n log n \) steps in the worst case. Unfortunately, merge sort requires \(\Theta(n) \) additional space and it runs more slowly than quick sort on most inputs. The objective of this assignment is to write modified versions of merge and quicksort that exhibit better performance than the standard versions described in our textbook. You will implement three improvements (two for merge sort and one for quicksort) that should improve some aspect of the algorithm’s performance without requiring a great deal of additional code. You will also experimentally evaluate the impact of your improvements.
The goal for this project is to develop a file compression utility to compete with applications like 7-Zip, gzip, WinZip etc.