How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the Io programming language

Published on 12 May 2024 09:40 PM
#Io

How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the Io programming language

Table of Contents

Problem Statement

An O(n2) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part. Although insertion sort is an O(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases:

The algorithm is as follows (from wikipedia): Writing the algorithm for integers will suffice.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the Io programming language

Source code in the io programming language

List do(
  insertionSortInPlace := method(
    for(j, 1, size - 1,
      key := at(j)
      i := j - 1

      while(i >= 0 and at(i) > key,
        atPut(i + 1, at(i))
        i = i - 1
      )
      atPut(i + 1, key)
    )
  )
)

lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)


List do(
    insertionSortInPlace := method(
        # In fact, we could've done slice(1, size - 1) foreach(...)
        # but creating a new list in memory can only make it worse.
        foreach(idx, key,
            newidx := slice(0, idx) map(x, x > key) indexOf(true)
            if(newidx, insertAt(removeAt(idx), newidx))
        )
    self)
)

lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)
lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

You may also check:How to resolve the algorithm Copy a string step by step in the EasyLang programming language
You may also check:How to resolve the algorithm Special characters step by step in the HTML programming language
You may also check:How to resolve the algorithm Run-length encoding step by step in the C# programming language
You may also check:How to resolve the algorithm Empty program step by step in the 8051 Assembly programming language
You may also check:How to resolve the algorithm Sorting algorithms/Sleep sort step by step in the C# programming language