If you find any error please comment. I will try to update this post. Array is a collection of homogeneous data elements. It is a very simple data structure. The elements of an array are stored in successive memory location. Array is refered by a name and index number. Array is nice because of their simplicity and well suited for situations where the number is known. Array operation : Traverse Insert Delete Sort Search There are two types of array. One dimensional array and multi dimensional array.One dimensional array This type of array of array represent and strore in linear form. Array index start with zero. Declaration : datatype arrayname[size]; int arr[10]; Input array : for(int i=0; i<10; i++) cin>>arr[i]; We can use store integer type of data to the array arr using above segment. ---------- Traverse : Traversing can easy in linera array. Algorithm: C++ implement : void traverse(int arr[]) { for(int i=0; i<10; i++) cout<<arr[i]; } ---------- Insertion : Inserting an element at the end of a linear array can be easily done provided the memory space space allocated for the array is large enough to accommodate the additional element. Inserting an element in the middle . . Algorithm : Insertion(arr[], n, k, item) here arr is a linear array with n elements and k is index we item insert. This algorithm inserts an item to kth in index in arr. Step 1:Start Step 2: Repeat for i=n-1 down to k(index) Shift the element dawn by one position] arr[i+1]=arr[i]; [End of the loop] Step 3: set arr[k] = item Step 4: n++; Step 5 : Exit. C++ implement : void insert(int arr[], int n, int k, int item) { for(int i=n-1; i>=k; i--) { arr[i]=arr[i+1]; } arr[k] = item; n++; } ---------- Deletion : Deletion is very easy on linear array. Algorithm : Deletion(arr, n, k) Here arr is a linear array with n number of items. K is position of elememt which can be deleted. Step 1:Start Step 2: Repeat for i=k upto n [Move the element upword] arr[i]=arr[i+1]; [End of the loop] Step 3: n--; Step 4 : Exit. C++ implementation : void deletion(int arr[], int n, int k) { for(int i=k; i<n; i++) { arr[i] = arr[i+1]; } n--; } ---------- Searching : Searching means find out a particular element in linear array. Linear seach and binary search are common algorithm for linear array. We discuss linear search and binary search. Linear search Algorithm : Linear search is a simple search algorithm that checks every record until it finds the target value Algorithm: LinearSeach(arr, n, item) Step 1:Start. Step 2: Initialize loc=0; Step 3: Repeat for i=0 upto n-1 if(arr[i]==item) loc++; [End of the loop] Step 4: if loc is not zero then print found otherwise print not found. Step 5 : Exit. C++ implementation : void linear search(int arr[], int n, item) { for(int i=0; i<n-1; i++) { if(arr[i]==item) loc++; } if(loc) cout<<"Found"<<endl; else cout<<"Not found"<<endl } ---------- Binary search : Binary search is available for sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. Algorithm : BinarySeach(arr, n, item) Step 1:Start Step 2: Initialize low = 0 and high = n-1; Step 3: While loop low<=high mid = (low + high)/2; if (a[mid] == item) return mid; else if (a[mid] < item) low = mid + 1; else high = mid - 1; Step 4: If item is not found in array return -1. Step 5: End. C++ implementation : int binarySearch(int[] a, int n, int item) { int low = 0; int high = n - 1; while(low<=high){ { int mid = (low + high)/2; if (a[mid] == item) return mid; else if (a[mid] < item) low = mid + 1; else high = mid - 1; } return -1; } -------------------- Sorting : There are various sorting algorithm in linear array. We discuss bubble sort and quick sort in this post. Bubble Sort: Bubble sort is a example of sorting algorithm . In this method we at first compare the data element in the first position with the second position and arrange them in desired order.Then we compare the data element with with third data element and arrange them in desired order. The same process continuous until the data element at second last and last position. Algorithm : BubbleSort(arr,n) Step 1:Start Step 2: Repeats i=0 to n Step 3: Repeats j=0 to n if(arr[j]>arr[j+1]) then interchange arr[j] and arr[j+1] [End of inner loop] [End of outer loop] Step 4: Exit. C++ implement : void BubbleSort(int arr, int n) { for(int i=0; i<n-1; i++) { for(int j=0; j<n-1; j++) { if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]); } } } Quick Sort: Quick sort is a divide and conquer paradism. In this paradism one element is to be chosen as partitining element . We divide the whole list array into two parts with respect to the partitiong elemnt . The data which are similar than or equal to the partitining element remain in the first part and data data which are greater than the partitioning element remain in the second part. If we find any data which is greater than the partitioning value that will be transfered to the second part., If we find any data whichis smaller than the partitioning element that will be transferred to first part. Transferring the data have been done by exchanging the position of the the data found in first and second part. By repeating this process , we can sort the whole list of data. Algorithm: QUICKSORT(arr, l, h) if l<h then pi ā PARTITION(A, l, h) QUICKSORT(A, l, piā1) QUICKSORT(A, pi+1, h) C++ implementation : int partition(int arr[], int start, int end) { int pivotValue = arr[start]; int pivotPosition = start; for (int i=start+1; i<=end; i++) { if (pivotValue > arr[i]) { swap(arr[pivotPosition+1], arr[i]); swap(arr[pivotPosition] , arr[pivotPosition+1]); pivotPosition++; } } return pivotPosition; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } C++ example for simple sorting program with stl function: Ā #include <bits/stdc++.h> using namespace std; int main() { int n, arr[100]; cin >> n; for(int i=0; i<n; i++) { cin>>arr[i]; } sort(arr, arr + n); for (int i=0; i<n; i++) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
Codechef Problem : SMPAIR, Ups and Downs, KTTABLE, TLG ,FORESTGA
Spoj Problem : AGGRCOW - Aggressive cows
Hackerrank Problem : Arrays - DS, Quicksort 1 - Partition, Quicksort 2 - Sorting