TADM2E 1.9 - Revision history

Matt: Undo revision 1060 by FuckMatt (talk)

2020-08-01T01:02:41Z

Undo revision 1060 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:36:35Z

Blanked the page

Matt: Undo revision 798 by EthanGamer (talk)

2020-07-23T13:34:58Z

Undo revision 798 by EthanGamer (talk)

EthanGamer: Replaced content with "''"

2020-07-14T02:00:15Z

Replaced content with "''"

Algowikiadmin: Recovering wiki

2014-09-11T18:13:11Z

Recovering wiki

New page

'''n = 1'''

The single-element List is sorted.

'''Assume''' the algorithm is true for '''n<=k'''

i.e.,
for i from k to 1
for j from 1 to i − 1
if (A[j] > A[j + 1])
swap the values of A[j] and A[j + 1]

produces a sorted list[1...k].

Let '''n = k+1'''

for i from k+1 to 1
for j from 1 to i − 1
if (A[j] > A[j + 1])
swap the values of A[j] and A[j + 1]

Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.

So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.

At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.

After the completion of all the iterations we have :

'''(i)''' A k-element sorted list (ascending order) :

A[1] < A[2] < A[3] <......... < A[k]

'''(ii)''' Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]

From '''(i)''' and '''(ii)''' we get

A[1] < A[2] < A[3] <......... < A[k] < A[k+1]

which is a sorted list[1...(k+1)].

'''QED'''

--[[User:Aroonalok|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok

← Older revision	Revision as of 01:02, 1 August 2020
Line 1:	Line 1:
	+	'''n = 1'''

	+	The single-element List is sorted.
	+
	+
	+	'''Assume''' the algorithm is true for '''n<=k'''
	+
	+	i.e.,
	+	for i from k to 1
	+	for j from 1 to i − 1
	+	if (A[j] > A[j + 1])
	+	swap the values of A[j] and A[j + 1]
	+
	+	produces a sorted list[1...k].
	+
	+
	+	Let '''n = k+1'''
	+
	+	for i from k+1 to 1
	+	for j from 1 to i − 1
	+	if (A[j] > A[j + 1])
	+	swap the values of A[j] and A[j + 1]
	+
	+	Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.
	+
	+	So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.
	+
	+	At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.
	+
	+	After the completion of all the iterations we have :
	+
	+	'''(i)''' A k-element sorted list (ascending order) :
	+
	+	A[1] < A[2] < A[3] <......... < A[k]
	+
	+	'''(ii)''' Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]
	+
	+
	+	From '''(i)''' and '''(ii)''' we get
	+
	+	A[1] < A[2] < A[3] <......... < A[k] < A[k+1]
	+
	+	which is a sorted list[1...(k+1)].
	+
	+	'''QED'''
	+
	+	--[[User:Aroonalok\|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok

← Older revision		Revision as of 09:36, 31 July 2020
Line 1:		Line 1:
−	~~'''n = 1'''~~

−	~~The single-element List is sorted.~~
−
−
−	~~'''Assume''' the algorithm is true for '''n<=k'''~~
−
−	~~i.e.,~~
−	~~for i from k to 1~~
−	~~for j from 1 to i − 1~~
−	~~if (A[j] > A[j + 1])~~
−	~~swap the values of A[j] and A[j + 1]~~
−
−	~~produces a sorted list[1...k].~~
−
−
−	~~Let '''n = k+1'''~~
−
−	~~for i from k+1 to 1~~
−	~~for j from 1 to i − 1~~
−	~~if (A[j] > A[j + 1])~~
−	~~swap the values of A[j] and A[j + 1]~~
−
−	~~Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.~~
−
−	~~So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.~~
−
−	~~At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.~~
−
−	~~After the completion of all the iterations we have :~~
−
−	~~'''(i)''' A k-element sorted list (ascending order) :~~
−
−	~~A[1] < A[2] < A[3] <......... < A[k]~~
−
−	~~'''(ii)''' Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]~~
−
−
−	~~From '''(i)''' and '''(ii)''' we get~~
−
−	~~A[1] < A[2] < A[3] <......... < A[k] < A[k+1]~~
−
−	~~which is a sorted list[1...(k+1)].~~
−
−	~~'''QED'''~~
−
−	~~--[[User:Aroonalok\|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok~~

← Older revision		Revision as of 13:34, 23 July 2020
Line 1:		Line 1:
−	''	+	'''n = 1'''
		+
		+	The single-element List is sorted.
		+
		+
		+	'''Assume''' the algorithm is true for '''n<=k'''
		+
		+	i.e.,
		+	for i from k to 1
		+	for j from 1 to i − 1
		+	if (A[j] > A[j + 1])
		+	swap the values of A[j] and A[j + 1]
		+
		+	produces a sorted list[1...k].
		+
		+
		+	Let '''n = k+1'''
		+
		+	for i from k+1 to 1
		+	for j from 1 to i − 1
		+	if (A[j] > A[j + 1])
		+	swap the values of A[j] and A[j + 1]
		+
		+	Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.
		+
		+	So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.
		+
		+	At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.
		+
		+	After the completion of all the iterations we have :
		+
		+	'''(i)''' A k-element sorted list (ascending order) :
		+
		+	A[1] < A[2] < A[3] <......... < A[k]
		+
		+	'''(ii)''' Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]
		+
		+
		+	From '''(i)''' and '''(ii)''' we get
		+
		+	A[1] < A[2] < A[3] <......... < A[k] < A[k+1]
		+
		+	which is a sorted list[1...(k+1)].
		+
		+	'''QED'''
		+
		+	--[[User:Aroonalok\|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok

← Older revision		Revision as of 02:00, 14 July 2020
Line 1:		Line 1:
−	''~~'n = 1'''~~	+	''
−
−	~~The single-element List is sorted.~~
−
−
−	~~'''Assume''' the algorithm is true for '''n<=k'''~~
−
−	~~i.e.,~~
−	~~for i from k to 1~~
−	~~for j from 1 to i − 1~~
−	~~if (A[j] > A[j + 1])~~
−	~~swap the values of A[j] and A[j + 1]~~
−
−	~~produces a sorted list[1...k].~~
−
−
−	~~Let '''n = k+1'''~~
−
−	~~for i from k+1 to 1~~
−	~~for j from 1 to i − 1~~
−	~~if (A[j] > A[j + 1])~~
−	~~swap the values of A[j] and A[j + 1]~~
−
−	~~Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.~~
−
−	~~So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.~~
−
−	~~At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.~~
−
−	~~After the completion of all the iterations we have :~~
−
−	~~'''(i)''' A k-element sorted list (ascending order) :~~
−
−	~~A[1] < A[2] < A[3] <......... < A[k]~~
−
−	~~'''(ii)''' Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]~~
−
−
−	~~From '''(i)''' and '''(ii)''' we get~~
−
−	~~A[1] < A[2] < A[3] <......... < A[k] < A[k+1]~~
−
−	~~which is a sorted list[1...(k+1)].~~
−
−	~~'''QED'''~~
−
−	~~--[[User:Aroonalok\|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok~~