Insertion sort: Difference between revisions

Jump to navigation Jump to search
Browse history interactively
VisualWikitext
→Variants: clarification about linked list weakness
 
→Implmentation: fix a typo
 
Line 17: Line 17:
* Simple implementation: [[Jon Bentley (computer scientist)|Jon Bentley]] shows a version that is three lines in [[C (programming language)|C]]-like pseudo-code, and five lines when [[Program optimization|optimized]].<ref name="pearls"/>
* Simple implementation: [[Jon Bentley (computer scientist)|Jon Bentley]] shows a version that is three lines in [[C (programming language)|C]]-like pseudo-code, and five lines when [[Program optimization|optimized]].<ref name="pearls"/>
* Efficient for (quite) small data sets, much like other quadratic (i.e., [[big O notation|O]](''n''<sup>2</sup>)) sorting algorithms
* Efficient for (quite) small data sets, much like other quadratic (i.e., [[big O notation|O]](''n''<sup>2</sup>)) sorting algorithms
* More efficient in practice than most other simple quadratic algorithms such as [[selection sort]] or [[bubble sort]]  
* May be more efficient in practice than most other simple quadratic algorithms such as [[selection sort]] or [[bubble sort]] {{ndash}} but relative incoming data order and read/write costs matter {{ndash}} with high exchange costs and randomly ordered data, [[selection sort]] is faster<ref>{{cite book |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) |year=2011 |title=Algorithms |publisher=Addison-Wesley |isbn=978-0-321-57351-3 |page=248,250}}</ref>
* [[Adaptive sort|Adaptive]], i.e., efficient for data sets that are already substantially sorted: the [[time complexity]] is [[big O notation|O]](''kn'') when each element in the input is no more than {{mvar|k}} places away from its sorted position
* [[Adaptive sort|Adaptive]], i.e., efficient for data sets that are already substantially sorted: the [[time complexity]] is [[big O notation|O]](''kn'') when each element in the input is no more than {{mvar|k}} places away from its sorted position
* [[Stable sort|Stable]]; i.e., does not change the relative order of elements with equal keys
* [[Stable sort|Stable]]; i.e., does not change the relative order of elements with equal keys
Line 100: Line 100:


It does not make the code any shorter, it also does not reduce the execution time, but it increases the additional memory consumption from {{math|O(1)}} to {{math|O(N)}} (at the deepest level of recursion the stack contains {{math|N}} references to the {{code|A}} array, each with accompanying value of variable {{code|n}} from {{math|N}} down to 1).
It does not make the code any shorter, it also does not reduce the execution time, but it increases the additional memory consumption from {{math|O(1)}} to {{math|O(N)}} (at the deepest level of recursion the stack contains {{math|N}} references to the {{code|A}} array, each with accompanying value of variable {{code|n}} from {{math|N}} down to 1).
==Implementation==
Below is an implementation in [[C (programming language)|C]].
<syntaxhighlight lang="c">
// Sorts the array in ascending order using insertion sort.
void insertionSort(int a[], int n) {
    // We treat a[0..i-1] as the sorted part, and a[i..end] as unsorted.
    for (int i = 1; i < n; i++) {
        int key = a[i];  // The value we want to insert into the sorted prefix.
        int j = i - 1;
        // Shift larger elements one position to the right
        // until we find where 'key' belongs.
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        // Place 'key' into the gap created by shifting.
        a[j + 1] = key;
    }
}
</syntaxhighlight>


==Best, worst, and average cases==
==Best, worst, and average cases==
Line 187: Line 210:
If the items are stored in a linked list, then the list can be sorted with O(1) additional space.  The algorithm starts with an initially empty (and therefore trivially sorted) list. The input items are taken off the list one at a time, and then inserted in the proper place in the sorted list. When the input list is empty, the sorted list has the desired result.
If the items are stored in a linked list, then the list can be sorted with O(1) additional space.  The algorithm starts with an initially empty (and therefore trivially sorted) list. The input items are taken off the list one at a time, and then inserted in the proper place in the sorted list. When the input list is empty, the sorted list has the desired result.


<syntaxhighlight lang="c" line="1">
<syntaxhighlight lang="c">
struct LIST * SortList1(struct LIST * pList)  
struct LinkedList {
{
    int value;
    struct LinkedList* next;
};
 
struct LinkedList* sortList(struct LinkedList* list) {
     // zero or one element in list
     // zero or one element in list
     if (pList == NULL || pList->pNext == NULL)
     if (list == NULL || list->next == NULL) {
         return pList;
         return list;
    }
     // head is the first element of resulting sorted list
     // head is the first element of resulting sorted list
     struct LIST * head = NULL;
     struct LinkedList* head = NULL;
     while (pList != NULL) {
     while (list != NULL) {
         struct LIST * current = pList;
         struct LinkedList* current = list;
         pList = pList->pNext;
         list = list->next;
         if (head == NULL || current->iValue < head->iValue) {
         if (head == NULL || current->value < head->value) {
             // insert into the head of the sorted list
             // insert into the head of the sorted list
             // or as the first element into an empty sorted list
             // or as the first element into an empty sorted list
             current->pNext = head;
             current->next = head;
             head = current;
             head = current;
         } else {
         } else {
             // insert current element into proper position in non-empty sorted list
             // insert current element into proper position in non-empty sorted list
             struct LIST * p = head;
             struct LinkedList* p = head;
             while (p != NULL) {
             while (p != NULL) {
                 if (p->pNext == NULL || // last element of the sorted list
                // check last element of the sorted list and middle of the list
                    current->iValue < p->pNext->iValue) // middle of the list
                 if (p->next == NULL || current->value < p->next->value) {
                {
                     // insert into middle of the sorted list or as the last element
                     // insert into middle of the sorted list or as the last element
                     current->pNext = p->pNext;
                     current->next = p->next;
                     p->pNext = current;
                     p->next = current;
                     break; // done
                     break; // done
                 }
                 }
                 p = p->pNext;
                 p = p->next;
             }
             }
         }
         }
Line 226: Line 253:


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
struct LIST
struct LinkedList* sortList(struct LinkedList* list) {
{
    // zero or one element in list
  struct LIST * pNext;
    if (list == NULL || list->next == NULL) {
  int          iValue;
        return list;
};
    }


struct LIST * SortList(struct LIST * pList)
    // build up the sorted array from the empty list
{
    struct LinkedList* sorted = NULL;
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;


  /* build up the sorted array from the empty list */
    // take items off the input list one by one until empty
  struct LIST * pSorted = NULL;
    while (list != NULL) {
        // remember the head
        struct LinkedList* head  = list;
        // trailing pointer for efficient splice
        struct LinkedList** trail = &sorted;


  /* take items off the input list one by one until empty */
        // pop head off list
  while (pList != NULL) {
        list = list->next;
      /* remember the head */
      struct LIST *  pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;


      /* pop head off list */
        // splice head into sorted list at proper place
      pList = pList->pNext;
        // does 'head' belong here?
        while (!(*trail == NULL || head->value < (*trail)->value)) {
            // no - continue down the list
            trail = &(*trail)->next;
        }


      /* splice head into sorted list at proper place */
        head->next = *trail;
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
        *trail = head;
          /* no - continue down the list */
    }
          ppTrail = &(*ppTrail)->pNext;
      }
 
      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }


  return pSorted;
    return sorted;
}
}
</syntaxhighlight>
</syntaxhighlight>
Retrieved from "https://wiki.tachyony.co.uk/wiki/Insertion_sort"