Insertion sort - Revision history

Savoundg at 06:31, 7 June 2018

2018-06-07T06:31:58Z

← Older revision		Revision as of 06:31, 7 June 2018
Line 1:		Line 1:
	Insertion sort is a in-place sorting algorithm that goes one element at a time.		Insertion sort is an in-place sorting algorithm that goes one element at a time.

	In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the ~~next~~ element. If the ~~next~~ element is not bigger than the ~~current element~~, the algorithm just ~~shifts~~ downward that element ~~before~~ the ~~current~~ element until it is in the right position and mark it as "sorted", and so on.		In the insertion sort algorithm, we call the first element of the array "sorted" and the other elements are called "unsorted". Then, we look for the first "unsorted" element. If the first "unsorted" element is not bigger than the rightmost "sorted" elements, the algorithm just swaps downward that element with the rightmost "sorted" element until it is in the right position and mark it as "sorted", and so on.

	To implement the insertion sort algorithm efficiently, the array should implemented using a linked list.		To implement the insertion sort algorithm efficiently, the array should implemented using a linked list.
Line 14:		Line 14:
	\|-		\|-
	\|https://www.youtube.com/watch?v=kU9M51eKSX8		\|https://www.youtube.com/watch?v=kU9M51eKSX8
			\|-
			\|https://www.youtube.com/watch?v=OGzPmgsI-pQ
	\|}		\|}

2018-06-05T06:15:20Z

← Older revision		Revision as of 06:15, 5 June 2018
Line 3:		Line 3:
	In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current element until it is in the right position and mark it as "sorted", and so on.		In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current element until it is in the right position and mark it as "sorted", and so on.

	To implement the insertion sort algorithm efficiently, the array should implemented ~~with link~~ linked.		To implement the insertion sort algorithm efficiently, the array should implemented using a linked list.

	The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n<sup>2</sup>).		The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n<sup>2</sup>).

2018-06-03T07:21:04Z

← Older revision		Revision as of 07:21, 3 June 2018
Line 8:		Line 8:

	The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.		The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.

			== Resources ==
			{\| class="wikitable"
			!
			\|-
			\|https://www.youtube.com/watch?v=kU9M51eKSX8
			\|}

2018-06-03T07:20:34Z

← Older revision		Revision as of 07:20, 3 June 2018
Line 5:		Line 5:
	To implement the insertion sort algorithm efficiently, the array should implemented with link linked.		To implement the insertion sort algorithm efficiently, the array should implemented with link linked.

	The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n2).		The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n<sup>2</sup>).

	The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.		The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.

2018-06-03T07:20:26Z

← Older revision		Revision as of 07:20, 3 June 2018
Line 1:		Line 1:
	Insertion sort is a in-place sorting algorithm that goes one element at a time.		Insertion sort is a in-place sorting algorithm that goes one element at a time.

			In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current element until it is in the right position and mark it as "sorted", and so on.

			To implement the insertion sort algorithm efficiently, the array should implemented with link linked.

			The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n2).

			The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.

2018-06-03T07:13:48Z

Created page with "Insertion sort is a in-place sorting algorithm that goes one element at a time."

New page

Insertion sort is a in-place sorting algorithm that goes one element at a time.