C++ Example – Insertion Sort Algorithm




Insertion Sort

  • Idea: Start at position 1 and move each element to the left until it is in the correct place
  • At iteration i, the leftmost i elements are in sorted order.
  • Sorts list by moving each element to its proper place.
  • Efficient for sorting small numbers.
  • In place sort: Takes an array A[0..n-1] (sequence of n elements) and arranges them in place, so that it is sorted.
  • Attempts to improve high selection sort key comparisons.

Online computer science courses to jumpstart your future.
Pseudo Code

for i = 1; i < a.size(); i++

  tmp = a[i]

  for j = i; j > 0 && tmp < a[j-1]; j--

    a[j] = a[j-1]

  a[j] = tmp

In this lesson we will learn how to write a source code in C++ programming language for doing simple Insertion sort using array in ascending order.

C++ Example

#include <iostream>

void PrintArray(int *array, int n) {
  for (int i = 0; i < n; ++i)
    std::cout << array[i] << " " << std::flush;
  std::cout << std::endl;
}

void InsertionSort(int arr[], int arr_size){
  if(arr_size > 1){
    int size = arr_size;
    for(int i = 1; i < size; ++i){
      int j = i - 1;
      int key = arr[i];
      while(j >= 0 && arr[j] > key){
        arr[j+1] = arr[j];
        --j;
      }
      arr[j+1] = key;
    }
  }
}

int main() {
  int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};
  int n = sizeof(array)/sizeof(array[0]);

  std::cout << "Before Insertion Sort :" << std::endl;
  PrintArray(array, n);

  InsertionSort(array, n);

  std::cout << "After Insertion Sort :" << std::endl;
  PrintArray(array, n);
  return (0);
}


/*
OUTPUT
Before Insertion Sort :
94 42 50 95 333 65 54 456 1 2325
After Insertion Sort :
1 42 50 54 65 94 95 333 456 2325
*/

 


Partner Sites

VideoToGifs.com

EasyOnlineConverter.com

SqliteTutorials.com





Be the first to comment

Leave a Reply

Your email address will not be published.


*