How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the C programming language

Table of Contents

Problem Statement

The   cocktail sort   is an improvement on the   Bubble Sort.

A cocktail sort is also known as:

The improvement is basically that values "bubble"   (migrate)   both directions through the array,   because on each iteration the cocktail sort   bubble sorts   once forwards and once backwards. After   ii   passes,   the first   ii   and the last   ii   elements in the array are in their correct positions,   and don't have to be checked (again). By shortening the part of the array that is sorted each time,   the number of comparisons can be halved.

Pseudocode for the   2nd   algorithm   (from Wikipedia)   with an added comment and changed indentations: %   indicates a comment,   and   deal   indicates a   swap.

Implement a   cocktail sort   and optionally show the sorted output here on this page. See the   discussion   page for some timing comparisons.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the C programming language

This code demonstrates the cocktail shaker sort algorithm, which is a variant of the bubble sort that sorts an array in ascending order. The algorithm works by repeatedly swapping adjacent elements if they are out of order, and then reversing the direction of the sort after each pass. This process is repeated until the array is sorted.

To sort an array of strings, the code first defines a comparison function, string_compare, which compares two strings and returns an integer indicating their relative order. The cocktail_shaker_sort function then takes the array of strings, the number of elements in the array, the size of each element, and the comparison function as arguments.

The cocktail_shaker_sort function begins by setting two pointers, begin and end, to the first and last elements of the array, respectively. The function then enters a loop that continues until the begin and end pointers cross each other. Within this loop, the function repeatedly swaps adjacent elements that are out of order, moving the begin pointer to the right and the end pointer to the left.

After each pass through the array, the function reverses the direction of the sort by updating the begin and end pointers. This process continues until the array is sorted.

The main function of the code initializes an array of strings, calls the cocktail_shaker_sort function to sort the array, and then prints the sorted array to the console.

Source code in the c programming language

#include <stdio.h>
#include <string.h>

void swap(char* p1, char* p2, size_t size) {
    for (; size-- > 0; ++p1, ++p2) {
        char tmp = *p1;
        *p1 = *p2;
        *p2 = tmp;
    }
}

void cocktail_shaker_sort(void* base, size_t count, size_t size,
                          int (*cmp)(const void*, const void*)) {
    char* begin = base;
    char* end = base + size * count;
    if (end == begin)
        return;
    for (end -= size; begin < end; ) {
        char* new_begin = end;
        char* new_end = begin;
        for (char* p = begin; p < end; p += size) {
            char* q = p + size;
            if (cmp(p, q) > 0) {
                swap(p, q, size);
                new_end = p;
            }
        }
        end = new_end;
        for (char* p = end; p > begin; p -= size) {
            char* q = p - size;
            if (cmp(q, p) > 0) {
                swap(p, q, size);
                new_begin = p;
            }
        }
        begin = new_begin;
    }
}

int string_compare(const void* p1, const void* p2) {
    const char* const* s1 = p1;
    const char* const* s2 = p2;
    return strcmp(*s1, *s2);
}

void print(const char** a, size_t len) {
    for (size_t i = 0; i < len; ++i)
        printf("%s ", a[i]);
    printf("\n");
}

int main() {
    const char* a[] = { "one", "two", "three", "four", "five",
        "six", "seven", "eight" };
    const size_t len = sizeof(a)/sizeof(a[0]);
    printf("before: ");
    print(a, len);
    cocktail_shaker_sort(a, len, sizeof(char*), string_compare);
    printf("after: ");
    print(a, len);
    return 0;
}

You may also check:How to resolve the algorithm Longest common subsequence step by step in the J programming language
You may also check:How to resolve the algorithm Reduced row echelon form step by step in the Ursala programming language
You may also check:How to resolve the algorithm Ternary logic step by step in the Erlang programming language
You may also check:How to resolve the algorithm Elementary cellular automaton/Random number generator step by step in the Perl programming language
You may also check:How to resolve the algorithm Padovan sequence step by step in the Swift programming language