Complexities of Basic Sorting Algorithms - Revision history

Arjun Suresh at 15:20, 15 February 2016

2016-02-15T15:20:07Z

Arjun Suresh at 10:48, 10 October 2014

2014-10-10T10:48:26Z

Arjun Suresh at 09:33, 15 July 2014

2014-07-15T09:33:59Z

Arjun Suresh at 09:36, 14 July 2014

2014-07-14T09:36:30Z

Arjun Suresh at 06:08, 5 May 2014

2014-05-05T06:08:44Z

Arjun Suresh at 06:08, 5 May 2014

2014-05-05T06:08:15Z

Arjun Suresh at 15:16, 1 March 2014

2014-03-01T15:16:11Z

Arjun Suresh at 18:23, 23 February 2014

2014-02-23T18:23:33Z

Arjun Suresh at 10:59, 20 February 2014

2014-02-20T10:59:30Z

Arjun Suresh at 10:59, 20 February 2014

2014-02-20T10:59:15Z

@@ Line 13: / Line 13: @@
 ! align = "center"|$\Theta(n^{2})$
 ! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\Theta(n^{2})$
+! align = "center"|$\Theta(n)$
 ! align = "center"|0
 ! align = "center" |$\Theta(n^{2})$

@@ Line 1: / Line 1: @@
 <metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms  </metadesc>
-{{alert|Please don't byheart this table. This is just to check your understanding and you should know how these complexities came|alert-danger}}
 {|class="wikitable" style="color: black; text-align: center; " width="85%"
 !align = "center" |Algorithm

@@ Line 10: / Line 10: @@
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Bubble_sort Bubble]
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
 ! align = "center"|0
-! align = "center" |$\theta(n^{2})$
+! align = "center" |$\Theta(n^{2})$
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Selection_sort Selection]
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
 ! align = "center"|0
-! align = "center"|$\theta(n)$
+! align = "center"|$\Theta(n)$
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Insertion_sort Insertion]
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n)$
+! align = "center"|$\Theta(n)$
 ! align = "center"|0
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Quick_sort Quick]
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
 ! align = "center"|0
-! align = "center"|$\theta(n^{2})$
+! align = "center"|$\Theta(n^{2})$
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Merge_sort Merge]
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
 ! align = "center"|Is not in-place sorting
 ! align = "center"|Is not in-place sorting
 |-
 ! align = "center"|[http://en.wikipedia.org/wiki/Heap_sort Heap]
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
 ! align = "center"|$O(n\lg n)$
-! align = "center"|$\theta(n\lg n)$
+! align = "center"|$\Theta(n\lg n)$
 |}
-The best case for insertion sort happens when the input array is already sorted. Each new element will then be put at the end of the array and the complexity will be $\theta(n)$.
+The best case for insertion sort happens when the input array is already sorted. Each new element will then be put at the end of the array and the complexity will be $\Theta(n)$.
-Interestingly, the worst case for quick sort also happens when the input array is sorted (either ascending or descending). This happens only if we choose the pivot as either the first element or the last element. In either of these case, we split the array across the pivot with n-1 elements on one array and just 1 element on the other array, which makes the complexity go to $\theta(n^2)$
+Interestingly, the worst case for quick sort also happens when the input array is sorted (either ascending or descending). This happens only if we choose the pivot as either the first element or the last element. In either of these case, we split the array across the pivot with n-1 elements on one array and just 1 element on the other array, which makes the complexity go to $\Theta(n^2)$
 ===In-Place Sorting===

@@ Line 63: / Line 63: @@
 {{Template:FBD}}
-[[Category:Notes & Ebooks for GATE Preparation]]
-[[Category: Algorithms & Data Structures]]
+[[Category: Algorithms & Data Structures Notes]]
 [[Category: Compact Notes for Reference of Understanding]]

@@ Line 1: / Line 1: @@
 <metadesc>Complexities of basic sorting algorithms. Minimum no. of swaps required for sorting algorithms  </metadesc>
-{{alert|Please don't byheart this table. This is just to check your understanding and you should know how these complexities came}}
+{{alert|Please don't byheart this table. This is just to check your understanding and you should know how these complexities came|alert-danger}}
 {|class="wikitable" style="color: black; text-align: center; " width="85%"
 !align = "center" |Algorithm

← Older revision		Revision as of 18:23, 23 February 2014
Line 64:		Line 64:
	[[Category:Notes & Ebooks for GATE Preparation]]		[[Category:Notes & Ebooks for GATE Preparation]]
	[[Category: Algorithms & Data Structures]]		[[Category: Algorithms & Data Structures]]
		+
		+	[[Category: Compact Notes for Reference of Understanding]]

@@ Line 53: / Line 53: @@
 The best case for insertion sort happens when the input array is already sorted. Each new element will then be put at the end of the array and the complexity will be $\theta(n)$.
-Interestingly, the worst case for quick sort also happens when the input array is sorted (either ascending or descending). This happens only if we choose the pivot as either the first element or the last element. In either of these case, we split the array across the pivot with n-1 elements on one array and just 1 element on the other array, which makes the complexity go to $\thetan^2$
+Interestingly, the worst case for quick sort also happens when the input array is sorted (either ascending or descending). This happens only if we choose the pivot as either the first element or the last element. In either of these case, we split the array across the pivot with n-1 elements on one array and just 1 element on the other array, which makes the complexity go to $\theta n^2$
 ===In-Place Sorting===