Skip to main content
deleted 2004 characters in body; edited title
Source Link
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Recursive Implementationimplementation of merge sort

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

EDIT:

The book I am reading "Introduction to ALgorithms 3rd Edition"is Introduction to Algorithms 3rd Edition by Cormen. It mentions a sentinalsentinel value be placed at the end of two subarrays. That, if implemented, it can result in better efficiency but. But I am not sure what to use as a sentinalsentinel value.

Edited code after Josay's comments

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

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This while and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < j; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,         mid);
        merge_sort(arr + mid,   length - mid);
        merge_parts(arr, length);
    }
}

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 = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

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

    merge_sort(arr, length);

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

    free(arr);
    return 0;
}

Recursive Implementation of merge sort

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

EDIT:

The book I am reading "Introduction to ALgorithms 3rd Edition" by Cormen mentions a sentinal value be placed at the end of two subarrays. That, if implemented, can result in better efficiency but I am not sure what to use as a sentinal value.

Edited code after Josay's comments

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

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This while and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < j; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,         mid);
        merge_sort(arr + mid,   length - mid);
        merge_parts(arr, length);
    }
}

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 = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

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

    merge_sort(arr, length);

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

    free(arr);
    return 0;
}

Recursive implementation of merge sort

The book I am reading is Introduction to Algorithms 3rd Edition by Cormen. It mentions a sentinel value be placed at the end of two subarrays. That, if implemented, it can result in better efficiency. But I am not sure what to use as a sentinel value.

Recursion tag, grammar, and remove tags from title
Source Link
rolfl
  • 98.1k
  • 17
  • 220
  • 419

Recursive Implementation of merge 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 merge sort in C.

What I am looking for:
I

I am looking whether the 2 functions can be optimized without changing the algorithm(merge sort), whether it follows the best-practices of programming in C and does it have proper readability factor?

Please Note:
I

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

Recursive Implementation of merge 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 merge sort in C.

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

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

Recursive Implementation of merge sort

Information about my code:

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

What I am looking for:

I am looking whether the 2 functions can be optimized without changing the algorithm(merge sort), whether it follows the best-practices of programming in C and does it have proper readability factor?

Please Note:

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

added 1840 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 23
  • 37

Edited code after Josay's comments

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

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This while and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < j; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,         mid);
        merge_sort(arr + mid,   length - mid);
        merge_parts(arr, length);
    }
}

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 = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

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

    merge_sort(arr, length);

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

    free(arr);
    return 0;
}

Edited code after Josay's comments

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

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This while and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < j; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,         mid);
        merge_sort(arr + mid,   length - mid);
        merge_parts(arr, length);
    }
}

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 = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

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

    merge_sort(arr, length);

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

    free(arr);
    return 0;
}
added 255 characters in body
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 23
  • 37
Loading
Source Link
Aseem Bansal
  • 2.3k
  • 3
  • 23
  • 37
Loading