3.1 Insertion Sort

Insertion Sort

Insertion sort is a simple sorting algorithm that works by sequentially traversing a list, while splitting it into two subarrays. As the list is being traversed, the current element (the key) is iteratively compared to the element before it, and “exchanges” indices with that element until there are no more elements that are smaller than the key. The Python code of insertion sort is given as

def insertionSort(l):  
   for i in range(1, len(l)):  
       key = l[i]  
       j = i
       while j > 0 and l[j - 1] > key:  
           l[j], l[j - 1] = l[j - 1], l[j]  
           j -= 1  
       l[j] = key  
   return l

A visual interpretation of insertion sort can be seen in the following figure:

\usetikzlibrary{animations}
\begin{document}
\begin{tikzpicture}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "true", 1s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {5};
  \node at (1.5, 0.5) {2};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {3};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[teal, opacity=0.25] (1, 0) rectangle (2, 1);
 
  % Variables
  \node at (1.5, -0.25)[below] {$i$};
  \node at (1.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 1s = "true", 2s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {5};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {3};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[teal, opacity=0.25] (0, 0) rectangle (1, 1);
 
  % Variables
  \node at (1.5, -0.25)[below] {$i$};
  \node at (0.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 2s = "true", 3s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {5};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {3};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[teal, opacity=0.25] (2, 0) rectangle (3, 1);
 
  % Variables
  \node at (2.5, -0.25)[below] {$i$};
  \node at (2.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 3s = "true", 4s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {4};
  \node at (2.5, 0.5) {5};
  \node at (3.5, 0.5) {3};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[teal, opacity=0.25] (1, 0) rectangle (2, 1);
 
  % Variables
  \node at (2.5, -0.25)[below] {$i$};
  \node at (1.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 4s = "true", 5s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {4};
  \node at (2.5, 0.5) {5};
  \node at (3.5, 0.5) {3};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[teal, opacity=0.25] (3, 0) rectangle (4, 1);
 
  % Variables
  \node at (3.5, -0.25)[below] {$i$};
  \node at (3.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 5s = "true", 6s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {4};
  \node at (2.5, 0.5) {3};
  \node at (3.5, 0.5) {5};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[teal, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
 
  % Variables
  \node at (3.5, -0.25)[below] {$i$};
  \node at (2.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 6s = "true", 7s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {3};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {5};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[teal, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  % Variables
  \node at (3.5, -0.25)[below] {$i$};
  \node at (1.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 7s = "true", 8s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {3};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {5};
  \node at (4.5, 0.5) {1};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[teal, opacity=0.25] (4, 0) rectangle (5, 1);
 
  % Variables
  \node at (4.5, -0.25)[below] {$i$};
  \node at (4.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 8s = "true", 9s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {3};
  \node at (2.5, 0.5) {4};
  \node at (3.5, 0.5) {1};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[teal, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
 
  % Variables
  \node at (4.5, -0.25)[below] {$i$};
  \node at (3.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 9s = "true", 10s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {3};
  \node at (2.5, 0.5) {1};
  \node at (3.5, 0.5) {4};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[teal, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
 
  % Variables
  \node at (4.5, -0.25)[below] {$i$};
  \node at (2.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 10s = "true", 11s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {2};
  \node at (1.5, 0.5) {1};
  \node at (2.5, 0.5) {3};
  \node at (3.5, 0.5) {4};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[teal, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
 
  % Variables
  \node at (4.5, -0.25)[below] {$i$};
  \node at (1.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 11s = "true", 12s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {1};
  \node at (1.5, 0.5) {2};
  \node at (2.5, 0.5) {3};
  \node at (3.5, 0.5) {4};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[teal, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
 
  % Variables
  \node at (4.5, -0.25)[below] {$i$};
  \node at (0.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 12s = "true", 13s = "false", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {1};
  \node at (1.5, 0.5) {2};
  \node at (2.5, 0.5) {3};
  \node at (3.5, 0.5) {4};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
  \fill[teal, opacity=0.25] (5, 0) rectangle (6, 1);
 
  % Variables
  \node at (5.5, -0.25)[below] {$i$};
  \node at (5.5, -0.75)[below] {$j$};
\end{scope}
\begin{scope}[animate = {myself: = 
  						{:visible = { 0s = "false", 13s = "true", 18s = "false", repeats }}}]
  % Draw the squares and indices above them
  \foreach \i in {0, 1, 2, 3, 4, 5} {
      % Draw square
      \draw[thick] (\i, 0) rectangle (\i+1, 1) node[midway, above=0.5cm] {\i};
      \coordinate (L\i) at (\i+0.25, 0);
      \coordinate (R\i) at (\i+0.75, 0);
  }
  % Label content.
  \node at (0.5, 0.5) {1};
  \node at (1.5, 0.5) {2};
  \node at (2.5, 0.5) {3};
  \node at (3.5, 0.5) {4};
  \node at (4.5, 0.5) {5};
  \node at (5.5, 0.5) {6};
  
  % Fills
  \fill[orange, opacity=0.25] (0, 0) rectangle (1, 1);
  \fill[orange, opacity=0.25] (1, 0) rectangle (2, 1);
  \fill[orange, opacity=0.25] (2, 0) rectangle (3, 1);
  \fill[orange, opacity=0.25] (3, 0) rectangle (4, 1);
  \fill[orange, opacity=0.25] (4, 0) rectangle (5, 1);
  \fill[orange, opacity=0.25] (5, 0) rectangle (6, 1);
\end{scope}
 
\end{tikzpicture}
\end{document}

Insertion sort runs in

Analysis