Skip to main content
2 of 8
Added modified code
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37

Implementation of insertion sort - optimization

Information about my code:
I am following this MIT OCW algorithms course. The first lecture described insertion sort and merge sort. I implemented insertion sort in C.

The algorithm is structured as a function called from the main function. The array to be sorted is allocated dynamically in the main function but can also be statically allocated.

What I am looking for:
I am looking whether the code can be optimized without changing the algorithm(insertion sort), whether it follows the best-practices of programming in C and does it have proper readability factor?

My code

#include<stdio.h>
#include<stdlib.h>

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into non-decreasing order
    To change the sorting to non-increasing order just change
    the comparison in while loop
    */
    register int j, k;
    int temp;

    for(j = 1; j < length; j++)
    {
        temp = arr[j];
        k = j - 1;
        while (k >= 0 && arr[k] > temp)
        {
            arr[k + 1] = arr[k];
            k--;
        }
        arr[k + 1] = temp;
    }
}

int main()
{
    int length;
    register int i;
    int *arr;

    //Finds the length of array and dynamically creates array of that length
    scanf("%d", &length);
    if ( (arr =  (int *)malloc(sizeof(int) * length)) == NULL)
    {
        printf("Not enough memory");
        return 1;
    }

    //Reads the array
    for(i = 0; i < length; i++)
        scanf("%d", &arr[i]);

    //Calls the sorting algorithm
    insertion_sort(arr, length);

    //Prints the sorted array
    for(i = 0; i < length; i++)
        printf("%d ", arr[i]);

    //Frees the memory allocated and returns
    free(arr);
    return 0;
}

EDIT:

My code after I changed it according to suggestions by @WilliamMorris

#include<stdio.h>
#include<stdlib.h>

#define SORTING_ALGO_CALL insertion_sort(arr, length);

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into non-decreasing order
    To change the sorting to non-increasing order just change
    the comparison in while loop
    */
    int k, temp;
    for (int j = 1; j < length; j++)
    {
        temp = arr[j];
        for (k = j - 1; arr[k] > temp && k >= 0; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

int main()
{
    int length, i, *arr;
    scanf("%d", &length);
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
    }

    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

    for (i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    SORTING_ALGO_CALL

    for (i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }

    free(arr);
    return 0;
}
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37