Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arrays - Coggle Diagram
Arrays
Arrays are Reference Type. The actual data is stored on Managed heap.
It stores address on stack - starting point of Array
on heap
In a jagged array, which is an array of arrays, each inner array can be of a different size.
int[][] jaggedArray = { new int[] {1,2,3,4},new int[] {5,6,7},new int[] {8},new int[] {9}};
In a multidimensional array, each element in each dimension has the same, fixed size as the other elements in that dimension.
int[,] multiDimArray = {{1,2,3,4},{5,6,7,0},{8,0,0,0},{9,0,0,0}};
String array stores address of each string in array which is on Heap.
Integer takes 4 bytes of memory. int* p = arraryObject; This will read the pointer address on memory.
Array also takes - 12 bytes extra storage for its metadata. SyncBlockIndex(4 bytes) + ref to method table (4 bytes) + Length (4 bytes) = 12 bytes. Plus, actual storage data. if int[4], then 4 * 4 bytes = 16 bytes
Array Operations
Access by index - O(1) - Constant,
Search in Unsorted Array - O(n) - linear - for loop,
Add element to full array - O(n) - linear - needs to be resized
Add element to empty array - O(1) - Index based,
Insert/Update/Remove - O(1) - if Index is known, else O(n),
Remove an element by shifting - O(n) - needs resizing
Bubble Sort
Compares neighbouring elements and sorts the items.
Biggest element goes to last index in each iteration
This is in-place algorithm. Uses very small memory for computation and this doesn't depend on n.
This is Stable Algo. O(npow2) - Time Complexity is Quadriatic. Performance degrades quickly.
"i" traveses from start to end of array and swapped evertime when bigger element is found
Stable and Unstable Sorting
Relative order for duplicate items are preserved in Stable Algos whereas relative order between duplicate items isn't preserved in Unstable Algos
This is Problematic when Objects are sorted. Prefer to keep this a Stable Sort.
Selection Sort
This is in-place Algo, uses small memory, performs less number of swaps than Bubble Sort
This is Unstable Algo as relative order b/n similar items can't be preserved
O(npow2) - Quadratic. Degrades performance with large inputs
by default, first index 0 is considered as largest, "i" traverses from 1 to end (till partindex). Swap only once for every iteration of outer loop.
Common code for Bubble and Selection Sort
partIndex
contains max number of items. Length - 1. Controls the OuterLoop
iterator
controls traversing on items inside loop
largest
0 - index of largest element
Insertion Sort
This is in-place Algo. Uses small memory. Stable Algo
finds the lowest item first. in Bubble and Selection bigger item is found first.
O(npow2) - Quadratic complexity
Items are compared and the smallest element is placed at the right spot relative to the compared elements.
Recursion
The process of invoking the same method from being within the method is called Recursion. There should be a base condition to stop the Recursion.
If Recursion goes for long it gives Stack Overflow exception.
Shell Sort
This is in-place Alog and unstable
O(n pow 3/2) - Quadratic - Time Complexity
Compare with gap of 3 first then reduce to 2 and then reduce to 1
In every comparison, swap the elements
In case of gap being 1, Swap is performed backwards till the lowest element is reached.
Merge Sort
Divide and Conquer
Two Phases : splitting and merging
not in-place Algo, it needs much memory space. It's stable Algo
O(nlogn) - Linearithmic Time Complexity