https://msdn.microsoft.com/en-us/library/aa249676(v=vs.60).aspx
Tuesday 12 April 2016
Thursday 11 February 2016
windows cpp
http://portal.aauj.edu/portal_resources/downloads/programming/learn_visual_c_plus_plus_6.pdf
https://www.packtpub.com/sites/default/files/microsoft-visual-c++-windows-applications-by-example-sample-chapter-6-the-tetris-application.pdf
https://msdn.microsoft.com/en-us/library/windows/desktop/aa365574(v=vs.85).aspx
https://www.packtpub.com/sites/default/files/microsoft-visual-c++-windows-applications-by-example-sample-chapter-6-the-tetris-application.pdf
https://msdn.microsoft.com/en-us/library/windows/desktop/aa365574(v=vs.85).aspx
Monday 8 February 2016
suman microsoft sorting
/// <summary> /// select min value index /// Time Complexity : O(n2) /// because of selection sort algo we can't reduce the time complexity even though the list is already sorted it will take O(n2) time. It does not have any method in algo to pre-find if list is already sorted.hence in all cases Best/Average/Worst it will take O(n2) time /// </summary> public static void SelectionSort() { int[] a = { 3, 6, 34, 2, 4, 56 }; int min, j; int temp; for (int i = 0; i < a.Length - 1; i++) { //Consider first element as Min Index min = i; for (j = i + 1; j < a.Length; j++) { if (a[j] < a[min]) { //if find any other element value less than first index update index min = j; } } //Swap min index position with first element temp = a[i]; a[i] = a[min]; a[min] = temp; } for (int i = 0; i < a.Length; i++) Console.WriteLine(a[i]); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// Bubble Sort /// in Bubble sort algo we arrange (bubble) the maximum number at last. This algo also takes O(n2) time like selection sort but adding few condition we can reduce the time in Best case. /// for eg: if list is already sorted then there will be no swap at all and after one pass we can find it using a bool variable so in Best case our algo will take O(n) time. /// and one more thing that second loop should run less than one pass because last element has sorted after one pass and so on. /// </summary> public static void BubbleSort() { int[] a = { 3, 4, 6, 8, 10, 9 }; int temp; for (int i = 0; i < a.Length - 1; i++) { bool unsorted = false; for (int j = 0; j < a.Length - i - 1; j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; unsorted = true; } } // if no swap made in this pass it means Array is sorted if (!unsorted) break; } for (int i = 0; i < a.Length; i++) Console.WriteLine(a[i]); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// Cocktail Sort /// Cocktail sort is similar to bubble sort but here we move largest element in right side (bubble sort) and smallest element in left side (selection sort) so basically when you move forward you will arrange the largest element in right side and when you back you will move smallest element in left side. /// This approach will make your sorting faster than bubble sort but time complexity will remain O(n2) because you have to made n comparison n times. /// In short this algo is efficient but time complexity can't be reduce /// </summary> public static void CocktailSort() { int[] a = { 2, 7, 6, 4, 1, 8, 5, 3 }; int temp; for (int i = 0; i < a.Length - 1; i++) { bool unsorted = false; //Move largest element in right side for (int j = i; j < a.Length - i - 1; j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; unsorted = true; } } // if no swap made in this pass it means Array is sorted if (!unsorted) break; else { //Move smallest elemnt in left side for (int k = a.Length - i - 2; k > i; k--) { if (a[k] < a[k - 1]) { temp = a[k]; a[k] = a[k - 1]; a[k - 1] = temp; unsorted = true; } } // if no swap made in this pass it means Array is sorted if (!unsorted) break; } } for (int i = 0; i < a.Length; i++) Console.WriteLine(a[i]); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// It has O(n2) time complaxity same as bubble sort but again it has best case O(n2) if list is already sorted /// </summary> public static void InsertionSort() { int[] a = { 2, 7, 6, 4, 1, 8, 5, 3 }; for (int i = 1; i < a.Length; i++) { // Current element value for comparison (Element may swap so need to save this value for comparison) int temp = a[i]; int j = i - 1; while ((j >= 0) && (temp < a[j])) { int tempo = a[j + 1]; a[j + 1] = a[j]; a[j] = tempo; j = j - 1; } } for (int i = 0; i < a.Length; i++) Console.WriteLine(a[i]); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Input:
int[] A = new int[] {10, 7, 4, 8, 9, 12, 3 }; QuickSort(ref A, 0, 6);
/// <summary> /// Quick Sort /// Best Case : O(n log n) i.e less than O(n2) /// Average Case : O(n log n) /// Worst Case : O(n2) /// </summary> /// <param name="a"></param> /// <param name="left"></param> /// <param name="right"></param> /// <returns></returns> public static void QuickSort(ref int[] a, int left, int right) { if (left < right) { int pIndex = Partition(ref a, left, right); QuickSort(ref a, left, pIndex - 1); QuickSort(ref a, pIndex + 1, right); } } public static int Partition(ref int[] a, int start, int end) { //We are considering last element as Pivot int pivot = a[end]; //Starting index as Pivot index int pIndex = start; //Now arrange all values smaller than Pivot before the PivotIndex and //all values greater than Pivot will be in right side of the PivotIndex for (int i = start; i < end; i++) { if (a[i] <= pivot) { int temp = a[i]; a[i] = a[pIndex]; a[pIndex] = temp; pIndex++; } } int t = a[pIndex]; a[pIndex] = pivot; a[end] = t; return pIndex; }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
int[] A = new int[] {10, 7, 4, 8, 9, 12, 3 }; MergeSort(A); /// <summary> /// complexity : O(n log n) in all cases but it will create auxilary arrays. /// This algo is not In-place sorting algo /// </summary> /// <param name="arr"></param> /// <param name="low"></param> /// <param name="high"></param> public static void MergeSort(int[] arr) { int n = arr.Length; if (n < 2) return; int mid = n / 2; int[] left = new int[mid]; int[] right = new int[n - mid]; for (int i = 0; i < mid; i++) left[i] = arr[i]; for (int i = mid; i < n; i++) right[i - mid] = arr[i]; MergeSort(left); MergeSort(right); Merge(left, right, arr); } private static void Merge(int[] left, int[] right, int[] arr) { int leftLength = left.Length; int rightLength = right.Length; int i = 0, j = 0, k = 0; while (i < leftLength && j < rightLength) { if (left[i] < right[j]) arr[k++] = left[i++]; else arr[k++] = right[j++]; } while (i < leftLength) arr[k++] = left[i++]; while (j < rightLength) arr[k++] = right[j++]; }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// Binary Search (Iterative Method) /// Complexity : O(Log n) /// </summary> /// <param name="number"></param> /// <param name="findFirstOccurance"></param> public static void BinarySearch(int number) { int[] a = new int[] { 2, 3, 5, 5, 5, 6, 8, 10, 12 }; int low = 0; int high = 9; int result = -1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] == number) { result = mid; break; } else { if (a[mid] > number) high = mid - 1; else low = mid + 1; } } if (result == -1) Console.WriteLine("Number does not exist"); else Console.WriteLine(result); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// Binary Search function to serach first or last occurance of number /// for Number=5 , FirstOccurenceIndex = 2, LastOccurenceIndex = 4 /// </summary> /// <param name="number">Number to search</param> /// <param name="findFirstOccurance"></param> public static void BinarySearchFirstLastOccurence(int number, bool findFirstOccurance) { int[] a = new int[] { 2, 3, 5, 5, 5, 6, 8, 10, 12 }; int low = 0; int high = 9; int result = -1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] == number) { result = mid; if (findFirstOccurance) high = mid - 1; else low = mid + 1; } else { if (a[mid] > number) high = mid - 1; else low = mid + 1; } } if (result == -1) Console.WriteLine("Number does not exist"); else Console.WriteLine("Number exists at {0} Index", result); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Count occurrence of a number in sorted array using binary search
public static void CountOccurenceOfNumber() { int[] a = new int[] { 2, 3, 5, 5, 5, 6, 8, 10, 12 }; int num = 5; int firstOccurence = BinarySearchFirstLastOccurence(a, num, true); int lastOccurence = BinarySearchFirstLastOccurence(a, num, false); int result = (lastOccurence - firstOccurence) + 1; Console.WriteLine(result); }
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/// <summary> /// Recursive method for Binary Search /// Time Coplexity : O(Log n) /// </summary> /// <param name="a">Array</param> /// <param name="low">Start index</param> /// <param name="high">End index</param> /// <param name="num">Number to Search</param> /// <returns></returns> public static int BinarySearchRecursion(int []a, int low, int high, int num) { if (low > high) return -1; int mid = (low + high) / 2; if (a[mid] == num) return mid; else { if (num < a[mid]) return BinarySearchRecursion(a, low, mid - 1, num); else return BinarySearchRecursion(a, mid + 1, high, num); } }
Sorting is the main component of data structure algorithm. There are number of scenario where you have to sort/arrange your data in ascending or descending order to perform some operation to make your algorithm fast and efficient like : Binary Search.
We have so many algorithm to sort the numeric values, every sorting algo has pron/cons and we can use those as per our requirements:
1- Selection Sort
2- Bubble Sort
3- Insertion Sort
4- Quick Sort
5- Merge Sort
6- Heap Sort
7- Cocktail Sort
8- Bucket Sort (Its not a separate algo but the different method to use any other algo)
Reference Link :
Array Sorting Algorithms
|
Subscribe to:
Posts (Atom)