Data Structure & Algorithm
A data structure is a method of organizing data in a virtual system. Think of sequences of numbers, or tables of data: these are both well-defined data structures. An algorithm is a sequence of steps executed by a computer that takes an input and transforms it into a target output.
Together, data structures and algorithms combine and allow programmers to build whatever computer programs they’d like. Deep study into data structures and algorithms ensures well-optimized and efficient code.
Common Data Structures
- Linked lists
- Stacks
- Queues
- Sets
- Maps
- Hash tables
- Search trees
Algorithms :
- Searching
- LinearSearching
- BinarySearching
- Searching : Searching is used to search the given element or number in the array .The most popular way to search in array is through Linear search and BinarySearch
LinearSearch: LinearSearch is a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.
Time Complexity : O(n)
Space Complexity : O(1)
BInarySearch : BinarySearching is spliting the array into half thats is finding the middle of the array and searching the element in left if the element is present in the left or right if the element is in right .The time taken by the BinarySearch is less than the LinearSearch.
Time Complexity : O(log n) : O(1)
Space Complexity : O(1)
-
Sorting
- BubbleSort
- SelectionSort
- InsertionSort
- CyclicSort
- Sorting : Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items.Sorting can be done on names, numbers and records. Sorting reduces the For example, it is relatively easy to look up the phone number of a friend from a telephone dictionary because the names in the phone book have been sorted into alphabetical order.
BubbleSorting :It1 compares last element with the preceding element. If the last element is less than that of preceding element swapping takes place. Then the preceding element is compared with that previous element. This process continuous until the II and I elements are compared with each other.
Time Complexity : O(n^2)
Space Complexity : O(1)
SelectionSorting : Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
Time Complexity : O(n^2)
space Complexity : O(1)
InsertionSorting : To sort an array of size N in ascending order iterate over the array and compare the current element (key) to its predecessor, if the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Time Complexity : O(n^2)
Space Complexity : O(1)
CyclicSorting: Cycle sort is a comparison sorting algorithm that forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array.Best to use when array is from (0/1 to N) and should be continous.
Time Complexity : O(n)
Space Complexity : O(1)