Skip to main content
deleted 22 characters in body; edited tags; edited title
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Implementation of insertion sort - optimization

Information about my code:
I

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

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;
}

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;
}

Implementation of insertion sort

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?

#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;
}
Rollback to Revision 1
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Please Note:
I will keep posting edited code if additional suggestions are made. Please fell free to review any and all of the versions.

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;
}

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

Please note that calling the function by MACRO definition is my idea not his. For reasons as to why I am doing this please see my comments to his answer.

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

#define SORTING_ALGO_CALL insertion_sort(arr, length);

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

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

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

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

    SORTING_ALGO_CALL

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

    free(arr);
    return 0;
}

Please Note:
I will keep posting edited code if additional suggestions are made. Please fell free to review any and all of the versions.

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;
}

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

Please note that calling the function by MACRO definition is my idea not his. For reasons as to why I am doing this please see my comments to his answer.

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

#define SORTING_ALGO_CALL insertion_sort(arr, length);

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

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

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

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

    SORTING_ALGO_CALL

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

    free(arr);
    return 0;
}

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;
}
deleted 7 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
#include<stdio.h>
#include<stdlib.h>

#define SORTING_ALGO_CALL insertion_sort(arr, length);

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

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

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

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

    SORTING_ALGO_CALL

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

    free(arr);
    return 0;
}
#include<stdio.h>
#include<stdlib.h>

#define SORTING_ALGO_CALL insertion_sort(arr, length);

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

int main()
{
    int length, *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 (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    SORTING_ALGO_CALL

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

    free(arr);
    return 0;
}
#include<stdio.h>
#include<stdlib.h>

#define SORTING_ALGO_CALL insertion_sort(arr, length);

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

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

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

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

    SORTING_ALGO_CALL

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

    free(arr);
    return 0;
}
added 158 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
Loading
deleted 18 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
Loading
added 145 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
Loading
Added modified code
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
Loading
Tweeted twitter.com/#!/StackCodeReview/status/353063155036991488
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37
Loading