Skip to content

Instantly share code, notes, and snippets.

@esthicodes

esthicodes/week3_sort.c

Created August 4, 2021 11:57
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save esthicodes/0f8b422e4f6be74197e15b642e260e6c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save esthicodes/0f8b422e4f6be74197e15b642e260e6c to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. esthicodes created this gist Aug 4, 2021.
    205 changes: 205 additions & 0 deletions week3_sort.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,205 @@
    #include <stdio.h>
    #include <cs50.h>

    /**
    * Sorts array in place using bubble sort - optimizes to end if there are
    * no swaps
    */
    void bubble_sort(int array[], int n)
    {
    // cycle through array
    for(int k = 0; k < n - 1; k++)
    {
    // optimize; check if there are no swaps
    int swaps = 0;

    // swap adjacent elements if out of order
    for(int i = 0; i < n - 1 - k; i++)
    {
    if (array[i] > array[i + 1])
    {
    int temp = array[i + 1];
    array[i + 1] = array[i];
    array[i] = temp;

    swaps++;
    }
    }

    if (!swaps)
    break;
    }
    }


    /**
    * Sorts array in place using selection sort
    */
    void selection_sort(int array[], int size)
    {
    // iterate over array
    for(int i = 0; i < size - 1; i++)
    {
    // smallest element and its position in sorted array
    int smallest = array[i];
    int position = i;

    // unsorted part of array
    for(int k = i + 1; k < size; k++)
    {
    // find the next smallest element
    if (array[k] < smallest)
    {
    smallest = array[k];
    position = k;
    }
    }

    // swap
    int temp = array[i];
    array[i] = smallest;
    array[position] = temp;
    }
    }


    /**
    * Sorts array in place using insertion sort
    */
    void insertion_sort(int array[], int size)
    {
    // iterate through unsorted part of array from l->r
    for(int i = 1; i < size; i++)
    {
    // define the start of the sorted array
    int j = i - 1;

    // specify the next element to sort
    int to_sort = array[i];

    // iterate through sorted part of array from r->l
    // figure out where in sorted portion to_sort should go
    while(j >= 0 && to_sort < array[j])
    {
    // shift sorted elements rightward
    array[j + 1] = array[j];
    j--;
    }

    // insert element into sorted portion of array
    array[j + 1] = to_sort;
    }
    }


    /**
    * The power of halving - Merge Sort
    */
    void merge (int array[], int start_1, int end_1, int start_2, int end_2)
    {
    int length = end_2 - start_1 + 1;
    int index = start_1;
    int temp[length];

    // While there are elements in both subarrays
    while (start_1 <= end_1 && start_2 <= end_2)
    {
    // Compare numbers at the start of the subarrays
    if (array[start_1] <= array[start_2])
    {
    // Append smaller to merged array
    temp[index] = array[start_1];
    index++;
    start_1++;
    }
    else
    {
    // Append smaller to merged array
    temp[index] = array[start_2];
    index++;
    start_2++;
    }
    }

    // While elements remain in subarray 1 (but not subarray 2)
    while (start_1 <= end_1)
    {
    // Append element to merged array
    temp[index] = array[start_1];
    start_1++;
    index++;
    }

    // While elements remain in subarray 2 (but not subarray 1)
    while (start_2 <= end_2)
    {
    // Append element to merged array
    temp[index] = array[start_2];
    start_2++;
    index++;
    }

    // Copy newly sorted array over to original array
    for (int i = end_2, j = 0; j < length; i--, j++)
    {
    array[i] = temp[i];
    }
    }

    void merge_sort (int array[], int start, int end)
    {
    if (end > start)
    {
    int middle = (start + end) / 2;

    // sort left half
    merge_sort(array, start, middle);

    // sort right half
    merge_sort(array, middle + 1, end);

    // merge the two halves
    merge(array, start, middle, middle + 1, end);
    }
    }

    /**
    * Prints all the elements in an array on one line.
    */
    void print_array(int array[], int n)
    {
    for(int i = 0; i < n; i++)
    {
    printf("%i ", array[i]);
    }
    printf("\n");
    }

    int main(void)
    {
    int size = 5;

    // bubble sort
    printf("Bubble sort\n");
    int bubble_nums[] = {7, 3, 0, 5, 2};
    bubble_sort(bubble_nums, size);
    print_array(bubble_nums, size);

    // selection sort
    printf("Selection sort\n");
    int selection_nums[] = {7, 3, 0, 5, 2};
    selection_sort(selection_nums, size);
    print_array(selection_nums, size);

    // insertion sort
    printf("Insertion sort\n");
    int insertion_nums[] = {7, 3, 0, 5, 2};
    insertion_sort(insertion_nums, size);
    print_array(insertion_nums, size);

    // merge sort
    printf("Merge sort\n");
    int merge_nums[] = {7, 3, 0, 5, 2};
    merge_sort(merge_nums, 0, size - 1);
    print_array(merge_nums, size);
    }