Selection sort - Revision history

Weihe at 11:05, 30 June 2015

2015-06-30T11:05:24Z

← Older revision		Revision as of 11:05, 30 June 2015
Line 46:		Line 46:

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.
	~~== Java Code Reverse Selectionsort ==~~
	~~<syntaxhighlight lang="java">~~


	~~int[] selectionSort(int [] list) {~~

	~~int n = list.length - 1;~~
	~~int left = 0;~~
	~~int min;~~
	~~int tmp;~~

	~~while(left < n) {~~
	~~min = left;~~
	~~for(int i = left + 1; i<=n; i++) {~~
	~~if (list[i] < list[min]) {~~
	~~min = i;~~
	}
	}

	~~tmp = list[min];~~
	~~list[min] = list[left];~~
	~~list[left] = tmp;~~
	~~left = left + 1;~~
	}
	~~return list;~~
	}

	~~</syntaxhighlight>~~

JanR at 12:31, 22 June 2015

2015-06-22T12:31:13Z

← Older revision		Revision as of 12:31, 22 June 2015
Line 46:		Line 46:

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.
	== Java Code ==		== Java Code Reverse Selectionsort ==
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">

JanR: /* Java Code */

2015-06-19T15:48:00Z

Java Code

← Older revision		Revision as of 15:48, 19 June 2015
Line 70:		Line 70:
	left = left + 1;		left = left + 1;
	}		}
			return list;
	}		}

	</syntaxhighlight>		</syntaxhighlight>

JanR: /* Java Code */

2015-06-19T15:47:14Z

Java Code

← Older revision		Revision as of 15:47, 19 June 2015
Line 50:		Line 50:


	int[] selectionSort(int [] list) {		int[] selectionSort(int [] list) {

	int n = list.length - 1;		int n = list.length - 1;

JanR: /* Java Code */

2015-06-19T15:46:53Z

Java Code

← Older revision		Revision as of 15:46, 19 June 2015
Line 48:		Line 48:
	== Java Code ==		== Java Code ==
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	/**

	int[] selectionSort(int [] list) {		int[] selectionSort(int [] list) {

JanR at 15:46, 19 June 2015

2015-06-19T15:46:27Z

← Older revision		Revision as of 15:46, 19 June 2015
Line 46:		Line 46:

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.
			== Java Code ==
			<syntaxhighlight lang="java">
			/**

			int[] selectionSort(int [] list) {

			int n = list.length - 1;
			int left = 0;
			int min;
			int tmp;

			while(left < n) {
			min = left;
			for(int i = left + 1; i<=n; i++) {
			if (list[i] < list[min]) {
			min = i;
			}
			}

			tmp = list[min];
			list[min] = list[left];
			list[left] = tmp;
			left = left + 1;
			}
			}

			</syntaxhighlight>

Weihe: /* Complexity */

2015-05-17T17:22:20Z

Complexity

← Older revision		Revision as of 17:22, 17 May 2015
Line 45:		Line 45:
	'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.		'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\~~cdotn~~^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.

Weihe: /* Complexity */

2015-05-17T17:22:09Z

Complexity

← Older revision		Revision as of 17:22, 17 May 2015
Line 45:		Line 45:
	'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.		'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdotn^2\right)</math>.

Weihe: /* Complexity */

2015-05-17T17:19:46Z

Complexity

← Older revision		Revision as of 17:19, 17 May 2015
Line 43:		Line 43:
	== Complexity ==		== Complexity ==

	'''Statement:''' The asymptotic complexity is in <math>\Theta(n^2)</math> in the best and worst case.		'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.

	'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>.

Weihe: /* Complexity */

2015-05-16T14:36:35Z

Complexity

← Older revision		Revision as of 14:36, 16 May 2015
Line 45:		Line 45:
	'''Statement:''' The asymptotic complexity is in <math>\Theta(n^2)</math> in the best and worst case.		'''Statement:''' The asymptotic complexity is in <math>\Theta(n^2)</math> in the best and worst case.

	'''Proof:''' The asymptotic complexity of ~~the inner loop in~~ the <math>i</math>-th iteration ~~of the outer loop~~ is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>.		'''Proof:''' The asymptotic complexity of the <math>i</math>-th iteration is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>.