StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Friday, March 1, 2013

C++ Insertion Sort

 March 01, 2013     Algorithms     No comments   

Insertion sort algorithm takes an element from the input list, finds the location it belongs in the sorted list, make space for the new element by moving the remaining elements and then inserting the element. This article explains the insertion sort with an implementation in C++.

Insertion sort introduction

Insertion sort similar to card ordering in your hand as you pick the cards one by one from the lot. The idea of the sort is to go through numbers from the beginning towards end one by one. At each time, check the number in question should be placed in the already visited numbers and move the numbers to make space for it. When all the numbers are visited, the list should be sorted. See below example output to see the operation.
  1. Average and Worst case performance are O(N^2), best case is O(N) (--> nearly sorted input).
  2. Need not have full list during start and can start as the numbers arrive.
  3. Stable and in-place.
  4. Below example, uses swapping of numbers, but one could directly move the number in question to its place and make efficient block move of the needed numbers.

Implementation of insertion sort

#include <iostream>

using namespace std;
const int INPUT_SIZE = 10;

void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void insertionsort(int* input)
{
    for (int i=1;i<INPUT_SIZE;i++)
    {
        for (int j=i;j>0;j--)
        {
            if (input[j]<input[j-1])
            {
                int tmp = input[j];
                input[j] = input[j-1];
                input[j-1] = tmp;
            } else
                break;
        }
        cout << "PASS: ";
        print(input);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    insertionsort(input);
    cout << "Output: ";
    print(input);
    return 0;
}
Output:-
Input: 500 700 800 100 300 200 900 400 1000 600 
PASS: 500 700 800 100 300 200 900 400 1000 600 
PASS: 500 700 800 100 300 200 900 400 1000 600 
PASS: 100 500 700 800 300 200 900 400 1000 600 
PASS: 100 300 500 700 800 200 900 400 1000 600 
PASS: 100 200 300 500 700 800 900 400 1000 600 
PASS: 100 200 300 500 700 800 900 400 1000 600 
PASS: 100 200 300 400 500 700 800 900 1000 600 
PASS: 100 200 300 400 500 700 800 900 1000 600 
PASS: 100 200 300 400 500 600 700 800 900 1000 
Output: 100 200 300 400 500 600 700 800 900 1000 
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk