Table Of Contents
* 🤓 INTRODUCTION
* 👉🏻 ABOUT INSERTION SORT ALGORITHM
* 🃏 PLAYING CARDS ANALOGY
* 🖖🏻 PSEUDOCODE
* 🛠 IMPLEMENTATION
* 👩🏻💻 CODE
* 🙏 THANK YOU
The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. - Donald Knuth
Let's dive in! 🤿
👉🏻 ABOUT INSERTION SORT ALGORITHM
Insertion sort algorithm solves the sorting problem:
Input: A sequence of n numbers
Output: A permutation (reordering) of the input sequence
The numbers that we want to sort, are also known as keys. Input is usually an array of n elements.
Insertion sort algorithm is an efficient algorithm for sorting a small number of elements.
🃏 PLAYING CARDS ANALOGY
Insertion sort works the way many people sort a hand of playing cards.
- We start with an empty left hand and the cards face down on the table.
- We remove one card at a time from the table and insert it into the correct position in the left hand.
- To find the correct position for a card, we compare it with each of the cards already in the hand (right to left)
- At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table
In this chapter, I will also introduce you to pseudocode. Pseudocode is an artificial and informal language that helps us programmers develop algorithms. Pseudocode is a "text-based" detail (algorithmic) design tool. The rules of Pseudocode are reasonably straightforward.
We will call this pseudocode (procedure) INSERTION-SORT-ALGO. It will take an array A[1...n], that contains a sequence of length n that is to be sorted. This procedure will rearrange the numbers within array A, with at most a constant number of them stored outside the array at any time.
INSERTION-SORT-ALGO(A: array) 1 for j = 2 to A.length 2 key = A[j] 3 //Insert A[j] into the sorted sequence A[1...j-1] 4 i = j - 1 5 while i > 0 and A[i] > key 6 A[i+1] = A[i] 7 i = i - 1 8 A[i+1] = key
Let's say that our array A looks like this: [9, 5, 6, 12];
The iteration of the loop starting at 1 and ending at 8, in each iteration, the black rectangle holds the key taken from A[j] which is compared to its left-hand side elements.
Let's see an implementation, but we will work with a larger dataset. For example, let our array be: [5, 9, 6, 12, 1, 2, 34, 15, 7]
Play with the code! 🕺🏻
🙏 THANK YOU FOR READING!
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
☕ SUPPORT ME AND KEEP ME FOCUSED!
Have a nice time hacking! 😊
Top comments (0)