DSA (MIDTERMS)

Bubble Sort

Is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Selection Sort

• An array by repeatedly finding the minimum element considering ascending order.

•  is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end.

• This algorithm is not suitable for large data sets as it is average and worst-case complexities are of Ο(n2), where n is the number of items.

Insertion Sort

• is an in-place comparison-based sorting algorithm.  Here, a sub-list is maintained, which is always sorted.

• This algorithm is not suitable for large data sets as its average and worst-case complexity are of Ο(n2), where n is the number of items.

Shell Sort

•  is a highly efficient sorting algorithm and is based on the insertion sort algorithm.  This algorithm avoids large shifts as in the case of insertion sort if the smaller value is to the far right and has to be moved to the far left

• This algorithm is quite efficient for medium-sized data sets as its average and worst-case complexity of this algorithm depends on the gap sequence the best known is Ο(n), where n is the number of items. And the worst-case space complexity is O(n).

• It uses insertion sort on widely spread elements, first to sort them and then sorts the less widely spaced elements. The spacing is termed as an interval.  The interval is calculated based on Knuth's formula as 

Heap Sort

• is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort.  Like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. 

• Although somewhat slower in practice on most machines than quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime.

Merge Sort 

• is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. 

• The time complexity of Merge Sort is O(nLogn) in all 3 cases; worst, average, and best as merge sort always divides the array into two halves and takes linear time to merge two halves.

Quick Sort

• is a divide and conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. 

Bucket Sort

Bin, also referred to as Bucket Sort runs in linear time on average. Like Counting Sort, bucket Sort is fast because it considers something about the input.

Radix Sort

• is one of the sorting algorithms used to sort a list of integer numbers in order.  In the radix sort algorithm, a list of integer numbers is sorted based on the digits of individual numbers.  Sorting is performed from the least significant digit to the most significant digit.

QUEUE

is an n ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front.  It is an example of a linear data structure.

First-in, First-Out (FIFO)

Has (BLANK) structure where elements can only be added to the rear of the queue and removed from the front of the queue.

• Enqueue

• For insertions

• Dequeue 

•  For deletion

• Adds an item onto the end of the queue. 

enqueue(new-item:item-type)

•  Removes the item from the front of the queue

dequeue()

• Returns the item at the front of the queue

front():item-type

• Returns the item at the front of the queue

back()

• True if no more items can be dequeued and there is no front item.

is-empty()Boolean

 True if no more items can

Is-full(): Boolean

 Pushes a new element to the end of the queue.

push(newElement)

•  Removes but does not return the element at the front of the queue

pop()

• Returns the number of elements in the queue

get-sizer():integer

LINKEDLIST

• is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.  A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

SINGLY LINKED LIST
DOUBLY LINKED LIST

CIRCULAR LINKED LIST

3 Types of LinkedList

Singly Linked List

• is the most common form of a Linked List where each node contains a data field and a single pointer to the next node in the list.

• The reference to the first node in the list is called the HEAD of the list. The pointer/reference/link field contained in the node is used to traverse to the next node and to its next node and so on till we reach a node that points to NULL. This is the last node in the list.  Also, a singly linked list can only be traversed in one and only one direction i.e. from head to the last node. There is no way to traverse from the last node back to the head.

Doubly Linked List

• is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

Circular Linked List

• is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.