Sort algorithms have many trade-offs, in-fact even the sorted output sequences might differ. Part 1: Your tasks for this assignment are the following: Identify at least five (5) algorithm differences...

Sort algorithms have many trade-offs, in-fact even the sorted output sequences might differ.

Part 1: Your tasks for this assignment are the following:

1. Identify at least five (5) algorithm differences that might be considered when choosing a sort algorithm.


2. Offer examples of related sorts with the discussion of each difference considered.

Part 2: Rationalize:

You have formed a hypothesis that Big O analysis is not appropriate for comparing different sort algorithms, but rather for comparing the performance of a given sort algorithm as the number of sort keys change. (Hint: consider locality differences among sorts).

Week 3 Deliverables:

• 5 fully documented differences among sorting algorithms.


• Support the differences with Sort algorithms that exemplify the related characteristics.


• Generate a summary of Sort differences.


• Include the Big O critique.


• Name the document "IT265__IP3.doc.

1 IT265 – 2003B Data Structures using Java document shell Demetricus Dixon 8/26/20 Table of Contents Abstract2 Section 1: Lists, Stacks, and Queues3 Implement 2 programs for the following: Stacks and Queues Section 1.1 Stacks 3 Section 1.2 Queues5 Section 2: Heaps and Trees Implement pseudo code for a hash table and resolve collisions with a linked list. Section 3: Sorting Algorithms Compare sort algorithms. Section 4: Searching Implement pseudo code to search for values in a linked list or array. Section 5: Recursion Implement pseudo code to create a factorial of a number using recursion. Abstract Section 1: Lists, Stacks, and Queues Let the linked list node be represented by the ‘Node’. Each ‘Node’ has a data item ‘Data’ of data type T and a ‘NextRef’ attribute pointing to the next node in the linked list. class Node{ T Data;// The data item of a node. Node NextRef;// link to the next Node in the list } We will implement stacks and queues using linked lists. The sub-sections below has the details of the implementations. Section 1.1: Stacks Assume a ‘Head’ Node exists with the NextRef attribute pointing to the first node in the stack or being null if the stack is empty. Given below is the pseudo code for the following 3 stack methods : push(item), pop( ) and display( ). Note that in the Java style pseudocodes given below, the top of the stack is the Node pointed to by ‘head’. void push(T item) { // create a new 'Node' called newnode // with item as the 'Data' and null as its 'NextRef' Node newnode = new Node(item, null); if(head==null) // stack is empty head = newnode;// set the newnode as the ‘head’ else // stack is not empty { // push to the top of the stack newnode.nextRef = head; head = newnode;// the newnode is the new head } } T pop()// Note that the return type is T - the data type of ‘Data’ { if(head==null) // stack is empty return null; // stack non-empty. Return the 'Data' of the head // and set the head to head.nextRef T topData = head.Data; head = head.nextRef; return topData; } void display()// The display function prints the stack from top to bottom { if(head==null) // stack is empty { print("empty stack!"); return; } // Set a pointer 'curr' to the head Node curr = head; while(curr!=null) { print(curr.Data); // print curr's data curr = curr.nextRef; // advance curr to the next Node } } Section 1.2: Queues Assume ‘front’ and ‘rear’ nodes exist with the ‘NextRef’ attributes pointing to the first and last nodes of the queue or being null if the queue is empty. This section describes the Java style pseudo codes for the following 3 queue methods: enqueue(item) dequeue( ) display( ) void enqueue(T item)// T is the datatype of the item { // create a new 'Node' called ‘newnode’ // with item as the 'Data' and null as its 'NextRef' Node newnode = new Node(item, null); if(front==null) // queue is empty. front = rear = null { front = newnode;// set the newnode as the ‘front’ rear = newnode;// set the newnode as the ‘rear’ } else // queue is not empty { rear.nextRef = newnode;// enqueue to the rear of the queue rear = newnode;// the newnode is the new rear } } T dequeue()// Note that the return type is T - the data type of ‘Data’ { if(front==null) // queue is empty return null; // queue non-empty. Return the 'Data' of the head // and set the front to front.nextRef T frontData = front.Data; front = front.nextRef; return frontData; } void display()// The display function prints the queue front to rear { if(front==null) // queue is empty { print("empty queue!"); return; } // Set a pointer 'curr' to the head Node curr = front; while(curr!=null) { print(curr.Data); // print curr's data curr = curr.nextRef; // advance curr to the next Node } } Section 2: Heaps and Trees TBD Section 3: Sorting Algorithms TBD Section 4: Searching TBD Section 5: Recursion TBD Conclusion References “Linked List Data Structure.” GeeksforGeeks, www.geeksforgeeks.org/data-structures/linked-list/. “Linked List Data Structure.” GeeksforGeeks, www.geeksforgeeks.org/data-structures/linked-list/.