- 0-Introduction
- 1-Chatbot Variables
- 2-Password IF Statements
- 3-Create Main Menu functions
- 4-Complete Quiz 3 Questions
- 5-Adding Score variable global
- 6-Debug this code
- 7-Introducing While loops Boolean flags
- 8-Introducing Validation password creation
- 9a-For Loop Guess the number
- 9b-For Loop Password Challenge
- 9c-For Loop Times table challenge
- FINAL CHALLENGE
- Skills Consolidation Task 1
- Test 1
- 0-Introduction
- 1-Introducing Lists
- 2-Personality Predictor Lists app
- 3-Players assigned weapons lists
- 3a-Nested List Matrix Snakes and Ladders game
- 3b Nested List Super Extension Complete game
- 4-String Manipulation Username Creator
- 5-StringManipulation Email Creator based on Validated username
- 6-Strip characters from password app
- 7-Create registration feature using lists
- 8-Introducing Dictionaries registration with dicts
- 8a-Course teacher finder program with dicts
- 9a-Football Club app Create and Learn
- 9b-Online Shopping Basket Checkout Program Create and Learn
- Test 1
- 0-Introduction
- 1-Introducing File Handling
- 2-READ from fake facebook file
- 3-SEARCH for username return no of friends
- 4-SEARCH by ID return full record listing
- 5-ADD WRITE a new user to file
- 6-SORT file by USER ID and Last Name
- 7-Bingo game store scores
- 8-Modulo Magic Program
- 9-Create Maths Quiz Program Tutorial
- 9a-How-to-DELETE user record row from file
- 9b-How to EDIT a field in a file
- Test 1

- 00 Intro
- 01 Main Menu Start Screen
- 02 Registration Feature Part1
- 03 Secure Password Creator
- 04 Login Functionality
- 05 MainFilms Menu Members
- 06 Allow Users to View films
- 07 Store Viewed Films by user
- 08 Allow users to like films
- 09 Search by Title
- 10 Search by Rating
- 11 Recommendations based on viewing FinalSolutions

- 00 Overview Start Here
- 01 Connect Create table
- 02 Add records to table
- 03 Fetch Display records
- 04 Update database records
- 05 Delete records
- 06 Search by condition where clause
- 07 Search for key phrase word
- 08 Sorting in SQLite
- 09 Search return selected fields
- 10 Count no rows
- 11 Find Max Value in column
- 12 Calculate Average
- 13 Calculate SUM total
- 14 Login username password sqlite

- 00-Introduction to OOP and Classes
- 01-Setup Game Canvas
- 02-Create a Ball Class
- 03-Setup main animation loop
- 04-Make the ball move up
- 05-Create bouncing ball movement
- 06-Change Starting Direction
- 07-Right left wall collision detection
- 08-Add Pong bat paddle class
- 09-Bat movement
- 10 Bat Ball collision detection
- 11 End Game Feature if ball hits bottom
- 12 Display text game over

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is a comparison-based algorithm that builds a final sorted array one element at a time. It iterates through an input array and removes one element per iteration, finds the place the element belongs in the array, and then places it there.It is generally considered much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort although it does has its own advantages - see additional information below.

#1 Write a Python program to sort a list of elements using the Insertion sort algorithm

#2 Comment each line of the python solution below to show your understanding of the algorithm

def insertionSort(nlist): for index in range(1,len(nlist)): currentvalue = nlist[index] position = index while position>0 and nlist[position-1]>currentvalue: nlist[position]=nlist[position-1] position = position-1 nlist[position]=currentvalue nlist = [14,46,43,27,57,41,45,21,70] insertionSort(nlist) print(nlist)

Insertion sort provides several advantages:

- Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(
*n*^{2})) algorithms such as selection sort or bubble sort - Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is
*O*(*nk*) when each element in the input is no more than k places away from its sorted position - Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it

When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

The resulting array after *k* iterations has the property where the first *k* + 1 entries are sorted ("+1" because the first entry is skipped). In each iteration the first remaining entry of the input is removed, and inserted into the result at the correct position, thus extending the result:

becomes

with each element greater than *x* copied to the right as it is compared against *x*.

The most common variant of insertion sort, which operates on arrays, can be described as follows:

- Suppose there exists a function called
*Insert*designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array. - To perform an insertion sort, begin at the left-most element of the array and invoke
*Insert*to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

Pseudocode of the complete algorithm follows, where the arrays are zero-based

i ← 1whilei < length(A) j ← iwhilej > 0andA[j-1] > A[j]swapA[j] and A[j-1] j ← j - 1end whilei ← i + 1end while

- Animated Sorting Algorithms: Insertion Sort at the Wayback Machine (archived 8 March 2015) – graphical demonstration
- Adamovsky, John Paul,
*Binary Insertion Sort – Scoreboard – Complete Investigation and C Implementation*, Pathcom. *Insertion Sort in C with demo*, Electrofriends.*Insertion Sort – a comparison with other O(n^2) sorting algorithms*, UK: Core war.*Category:Insertion Sort*(wiki), LiteratePrograms – implementations of insertion sort in various programming languages*InsertionSort*, Code raptors – colored, graphical Java applet that allows experimentation with the initial input and provides statistics- Harrison,
*Sorting Algorithms Demo*, CA: UBC – visual demonstrations of sorting algorithms (implemented in Java) *Insertion sort*(illustrated explanation), Algo list. Java and C++ implementations

.