ASW
Sorting Algorithms

Sorting Algorithms

Description

Sorting algorithms are algorithms that orders data in an array. They are most commonly used for numerical or alphanumerical arrays. They have direct applications in searching, database, and many more. And are a major part of what is taught in the study of algorithms in computer science. Here we will look at some common sorting algorithms.

Selection Sort

Download C Source
Download Python Source

Selection Sort Video ASWYouTube
Selection Sort with playing cards Video ASWYouTube

Description

Selection sort is a simple and intuitive sorting algorithm that works by repeatedly selecting the smallest (or largest, depending on the sorting order) element from the unsorted portion of the list and swapping it with the first unsorted element. It continues this process until the entire list is sorted.

Here’s a step-by-step explanation of the selection sort algorithm:

Steps in Selection Sort:

  1. Initialize: Start with the first element in the list, treating it as the current position for sorting.
  2. Find the Minimum: Search for the smallest element in the unsorted portion of the list.
  3. Swap: Swap the smallest element found in the unsorted portion with the element at the current position.
  4. Move to Next Position: Move the current position one step forward and repeat the process for the remaining unsorted portion of the list.
  5. Repeat: Continue steps 2 to 4 until the entire list is sorted.

Characteristics:

  • Time Complexity:
    • Best case: O(n2)O(n2)
    • Average case: O(n2)O(n2)
    • Worst case: O(n2)O(n2)
  • Space Complexity: O(1)O(1) (in-place sorting algorithm).
  • Stability: It is not stable by default because it may change the relative order of equal elements during swaps.

The implementation of the selection sort algorithm contains two loops, an outer loop which traverse the entire array. And an inter loop which traverse the unsorted portion of the array looking for the unsorted minimum element. Once the inter loop has traverse unsorted portion of the array, and has determine minimum element. The minimum element is swapped with the first element of the unsorted portion thus extending the sorted portion. This process is repeated until all the element are moved to the sorted portion.

Source


///////////////////////////////////////////////////////////////////////
// 
// selectionSort.c
// 
// Written by: Don Dugger
//       Date: 2023-04-18
//
// Copyright (C) 2023 Acme Software Works, Inc.
//  
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>
 
#define DATA_SIZE 25

///////////////////////////////////////////////////////////////////////
/// Functions

void selectionSort(int *data, int size);
void createRandomData(int *data,int size, int seed);

///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    selectionSort(data,DATA_SIZE);

    for ( int i = 0; i < DATA_SIZE; ++i) {
        printf(" %2.2d",data[i]);
    }
    printf("\n");

    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

void selectionSort(int *data, int size)
{
    int unsorted_idx;
    int search_idx;
    int min_idx;
    int temp;
    // One by one move boundary of unsorted subdata (Note size = 25) 
    for (unsorted_idx = 0; unsorted_idx < size-1; unsorted_idx++)  
    {  
        // Find the minimum element in unsorted data  
        min_idx = unsorted_idx;  
        for (search_idx = unsorted_idx+1; search_idx < size; search_idx++)  
            if (data[search_idx] < data[min_idx])  
                min_idx = search_idx;  
        // Swap the found minimum element with the first
        // element of the unsorted data.  
        temp = data[min_idx];  
        data[min_idx] = data[unsorted_idx];  
        data[unsorted_idx] = temp;
    }  

} // End of selectionSort()
  
///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf(" %2.2d",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  selectionSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-04-18
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def selectionSort(data, size):

    # One by one track the number sorted elements (Note size = 25)      
    for unsorted_idx in range(size-1):
        # Find the minimum element in unsorted data  
        min_idx = unsorted_idx  
        for search_idx in range(unsorted_idx+1,size):
            if data[search_idx] < data[min_idx]:
                min_idx = search_idx
        # Swap the found minimum element with the first
        # element of the unsorted data.  
        temp = data[min_idx]  
        data[min_idx] = data[unsorted_idx]  
        data[unsorted_idx] = temp

#######################################################################
#
# Main
#
#######################################################################
if __name__ == "__main__":

    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)
    selectionSort(data,size)
    print(data)

#######################################################################
############################ End of File ##############################
#######################################################################

Insertion Sort

Download C Source
Download Python Source

Insertion Sort Video ASWYouTube
Insertion Sort with playing cards Video ASWYouTube

Description

The insertion sort algorithm sorts an array by taking elements from the unsorted portion of the array, storing them in a temporary variable and searching through the sorted portion one by one to determine the proper location to insert it.

Insertion sort is a simple and efficient sorting algorithm, particularly for small or nearly sorted datasets. It builds the sorted list one element at a time by repeatedly taking the next unsorted element and inserting it into the correct position relative to the already sorted portion of the list.

Steps in Insertion Sort:

  1. Start with the Second Element: Assume the first element is already sorted. Pick the second element and determine where it fits in the sorted portion.
  2. Insert into Correct Position: Compare the selected element with elements in the sorted portion of the array (to its left) and shift elements to the right until the correct position for the current element is found.
  3. Repeat for All Elements: Move to the next element and repeat the process until the entire list is sorted.

Characteristics:

  • Time Complexity:
    • Best case (nearly sorted): O(n)O(n)
    • Average case: O(n2)O(n2)
    • Worst case (reverse sorted): O(n2)O(n2)
  • Space Complexity: O(1)O(1) (in-place sorting).
  • Stability: Insertion sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

The implementation of the insertion sort algorithm contains two loops. An outer loop that traverses the unsorted portion of the array. The outer loop obtains a key element from the unsorted portion of the array. And an inter loop which traverses the sorted portion in reverse order, looking for the place to insert the key element.

The key element is taken from the first location of the unsorted portion of the array. Which in the beginning is the second location of the array. Note a single element array is always sorted. So when we begin, the first element is considered sorted. Once we have the key element temporarily stored. We can use it's original location to increase the size of the sorted portion. As we traverse the sorted portion of the array using the search index. We compare each element with the key and if we haven't found the proper location, move that element back one location to make room to insert the current key when we do find the proper location.

Source


///////////////////////////////////////////////////////////////////////
// 
// insertionSort.c
// 
// Written by: Don Dugger
//       Date: 2023-04-18
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>
 
#define DATA_SIZE 25

///////////////////////////////////////////////////////////////////////
/// Functions

void insertionSort(int *data, int size);
void swap(int *xp, int *yp);
void createRandomData(int *data,int size, int seed);
 
///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    insertionSort(data,DATA_SIZE);

    for ( int i = 0; i < DATA_SIZE; ++i) {
        printf(" %2.2d",data[i]);
    }
    printf("\n");

    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

void insertionSort(int *data, int size)
{
    int unsorted_idx;
    int key;
    int search_idx;
    // One by one move boundary of unsorted subdata (Note size = 25) 
    for (unsorted_idx = 1; unsorted_idx < size; unsorted_idx++)  
    {  
        // Find the minimum element in unsorted data  
        key = data[unsorted_idx];  
        search_idx = unsorted_idx -1; 
        while (search_idx >= 0 && data[search_idx] > key) { 
            data[search_idx + 1] = data[search_idx];  
            --search_idx;  
        } 
        // Now insert the key in it's sorted position 
        data[search_idx + 1] = key;
    }  

} // End of insertionSort()

///////////////////////////////////////////////////////////////////////

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;

} // End of swap()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf(" %2.2d",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  insertionSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-04-18
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def insertionSort(data, size):

    # One by one move boundary of unsorted subdata (Note size = 25) 
    for unsorted_idx in range(1,size):
        # Find the minimum element in unsorted data  
        key = data[unsorted_idx]  
        search_idx = unsorted_idx-1 
        while search_idx >= 0 and data[search_idx] > key : 
            data[search_idx+1] = data[search_idx]  
            search_idx -= 1 
        # Now insert the key in it's sorted position 
        data[search_idx + 1] = key

#######################################################################
#
# Main
#
#######################################################################
if __name__ == "__main__":

    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)
    insertionSort(data,size)
    print(data)

#######################################################################
############################ End of File ##############################
#######################################################################

Bubble Sort

Download C Source
Download Python Source

Bubble Sort Video ASWYouTube
Bubble Sort with playing cards Video ASWYouTube

Description

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until the list is sorted. It gets its name because smaller elements "bubble" to the top of the list (toward the beginning) in each pass.

Steps in Bubble Sort:

  1. Compare Adjacent Elements:
  2. Start with the first element in the list and compare it with the next element.
  3. If the first element is larger than the second, swap them.
  4. Repeat for All Pairs:
  5. Move to the next pair of adjacent elements and repeat the comparison and swapping process.
  6. Continue until the end of the list.
  7. Reduce the Unsorted Portion:
  8. After one pass through the list, the largest element is guaranteed to be at the correct position (end of the list).
  9. Ignore the last element in subsequent passes and repeat the process for the remaining unsorted portion.
  10. Repeat Until Sorted:
  11. Continue making passes through the list until no swaps are needed, indicating the list is sorted.

Characteristics:

  • Time Complexity:
    • Best case (already sorted): O(n)O(n)
    • Average case: O(n2)O(n2)
    • Worst case (reverse sorted): O(n2)O(n2)
  • Space Complexity: O(1)O(1) (in-place sorting).
  • Stability: Bubble sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

The bubble sort algorithm sorts an array by traversing the unsorted portion of the array and comparing adjacent elements and putting them in order. And repeating this process until the array is fully sorted.

The implementation of the bubble sort algorithm contains two loops. An outer loop that keeps track of how much of the array has been sorted and an inter loop which traverses the unsorted portion. The inter loop begins at the first element of the array and compares it to the next element and if the first element is larger it swaps the two elements putting them in sort. This process is repeated for each of the following elements until the it reaches the end of the unsorted portion of the array. Note that the number of swaps are counted and if the inter loop traverses the entire array with no swaps the remainder of the array is sorted.

Source


///////////////////////////////////////////////////////////////////////
// 
// bubbleSort.c
// 
// Written by: Don Dugger
//       Date: 2023-04-18
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>
 
#define DATA_SIZE 25

///////////////////////////////////////////////////////////////////////
/// Functions

void bubbleSort(int *data, int size);
void createRandomData(int *data,int size, int seed);

///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    bubbleSort(data,DATA_SIZE);

    for ( int i = 0; i < DATA_SIZE; ++i) {
        printf(" %2.2d",data[i]);
    }
    printf("\n");

 
    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

void bubbleSort(int *data, int size)
{
    int sorted;
    int swapped;
    int search_idx;
    int temp;
     // One by one track the number sorted elements (Note size = 25)      
    for ( sorted = 0; sorted < size-1; sorted++ )                        
    {                                                                    
        // Keep track of the number of times elements were swapped       
        swapped = 0;                                                     
        // Last sorted elements are already in place                     
        for ( search_idx = 0; search_idx < size-sorted-1; search_idx++ ) {      
            if ( data[search_idx] > data[search_idx+1] ) {               
                temp = data[search_idx];                                 
                data[search_idx] = data[search_idx+1];                   
                data[search_idx+1] = temp;                               
                ++swapped;                                                
            }                                                            
        }                                                                
        // If there were no swaps the remaining data is sorted           
        if ( swapped == 0 )                                              
            break;                                                       
    }

} // End of bubbleSort()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf(" %2.2d",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  bubbleSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-04-18
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def bubbleSort(data, size):

    # One by one track the number sorted elements (Note size = 25)      
    for i in range(size):
        # Keep track of the number of times elements were swapped       
        swapped = 0
        for j in range(0, size-i-1):
            # If the current element is greater than the next element, swap them
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swapped += 1

        # If there were no swaps the remaining data is sorted           
        if swapped == 0:
            break

#######################################################################
#
# Main
#
#######################################################################
if __name__ == "__main__":

    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)
    bubbleSort(data,size)
    print(data)

#######################################################################
############################ End of File ##############################
#######################################################################

Quick Sort

Download C Source
Download Python Source
Quick Sort Video ASWYouTube

Description

Quick sort is a highly efficient, widely used sorting algorithm based on the divide-and-conquer strategy. It works by selecting a "pivot" element from the array, partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot, and then recursively sorting the sub-arrays.

Steps in Quick Sort:

  1. Choose a Pivot:
    • Select a pivot element from the array. The choice of pivot can vary (e.g., first element, last element, middle element, or a random element).
  2. Partition the Array:
    • Reorder the array so that all elements smaller than the pivot come before it, and all elements larger than the pivot come after it. The pivot element is then in its correct sorted position.
  3. Recursively Sort:
    • Apply the same process to the sub-arrays of elements smaller and larger than the pivot.
  4. Base Case:
    • The recursion ends when the sub-arrays have one or zero elements, as these are already sorted.

Characteristics:

  • Time Complexity:
    • Best case: O(nlog⁡n)O(nlogn) (when partitions are balanced).
    • Average case: O(nlog⁡n)O(nlogn).
    • Worst case: O(n2)O(n2) (when partitions are highly unbalanced, e.g., already sorted array with poor pivot choice).
  • Space Complexity:
    • O(log⁡n)O(logn) (for the recursion stack).
  • Stability:
    • Quick sort is not stable by default because elements with equal values may be reordered during the partitioning process.

The quick sort algorithm which is implemented here consists of two functions. The first is the primary function and has two recursive calls. The second is called from the primary and is the work horse which deals with the partitions and does the sorting. The partition function derives the pivot from the last element. Then in a loop, searches starting at the first element of the partition, for elements that are less than the pivot.

When it finds an element that is less, it increments the smaller index and swaps the element at the smaller index with the element at the search index. When a smaller element is encountered and the smaller index is increased, this insures that all element to the left are smaller than the pivot. Note that the smaller index is only increased when the search index encounters an element smaller than the pivot. This in affect moves the smaller elements to the left in the partition and the larger ones to the right. And finally the pivot is swapped to the location of the smaller index plus one. Which is between the smaller and the larger elements and it's final sorted location. Then it returns the pivot index to the primary function, quick sort, which will then be used to create the next partition.

Source


///////////////////////////////////////////////////////////////////////
// 
// quickSort.c
// 
// Written by: Don Dugger
//       Date: 2023-04-18
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
//  
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>
 
///////////////////////////////////////////////////////////////////////
/// Functions

void quickSort(int *data, int low, int high);
int partition(int *data, int low, int high);
void swap(int *xp, int *yp);
void createRandomData(int *data,int size, int seed);

#define DATA_SIZE 25

///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    quickSort(data,0,DATA_SIZE-1);
 
    for ( int i = 0; i < DATA_SIZE; ++i) {
        printf(" %2.2d",data[i]);
    }
    printf("\n");
    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

void quickSort(int *data, int low, int high)
{
    if (low < high)
    {
        // Partition array and get the pivot index
        int pivot_idx = partition(data, low, high);

        quickSort(data, low, pivot_idx - 1);  // Before pivot
        quickSort(data, pivot_idx + 1, high); // After pivot
    }

} // End of quickSort()

///////////////////////////////////////////////////////////////////////

int partition(int *data, int low, int high)
{
    // pivot (Element to be placed at right position)
    int pivot = data[high];  

    int smaller_idx = (low - 1);  // Index of smaller element

    for (int search_idx = low; search_idx < high; search_idx++)
    {
        // If current element is smaller than the pivot
        if (data[search_idx] < pivot) {
            ++smaller_idx;    // increment index of smaller element
            swap(&data[smaller_idx],&data[search_idx]);
        }
    }
    swap(&data[smaller_idx + 1],&data[high]);
    return smaller_idx + 1;

} // End of partion();

///////////////////////////////////////////////////////////////////////

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;

} // End of swap()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf(" %2.2d",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  quickSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-04-18
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def quickSort(data,low,high):

    if low < high:
        # Partition array and get the pivot index 
        pivot_idx = partition(data, low, high)

        quickSort(data, low, pivot_idx - 1)  # Before pivot
        quickSort(data, pivot_idx + 1, high) # After pivot
    


#######################################################################

def partition(data,low,high):

    # pivot (Element to be placed at right position)
    pivot = data[high]  

    smaller_idx = low - 1  # Index of smaller element

    for search_idx in range(low, high):
        # If current element is smaller than the pivot
        if data[search_idx] < pivot :
            smaller_idx += 1  # increment index of smaller element
            swap(data,smaller_idx,search_idx)
    swap(data,smaller_idx+1,high)
    return smaller_idx+1

#######################################################################

def swap(data,idx1,idx2):
    temp = data[idx1]
    data[idx1] = data[idx2]
    data[idx2] = temp

#######################################################################
#
# Main
#
#######################################################################
if __name__ == "__main__":

    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)
    quickSort(data,0,size-1)
    print(data)

#######################################################################
############################ End of File ##############################
#######################################################################
.method-title {
  color: #66d;
  text-shadow: #000 3px 3px 3px;
}

Merge Sort

Download C Source
Download Python Source
Merge Sort Video ASWYouTube

Description

The merge sort is efficient sorting algorithm that uses a divide-and-conquer approach to sort an array of elements. The merge sort divides the unsorted array into smaller sub arrays, sorts these sub arrays, and then merge them back together into a single sorted array. This process continues recursively until the entire array is sorted.

Here's a step-by-step explanation of how Merge Sort works:

  1. Divide: The first step of Merge Sort is to divide the input list into two halves. This can be done by finding the middle point of the list. If the list has an odd number of elements, one of the halves will have one more element than the other.
  2. Conquer: Recursively sort both halves of the list. This involves applying the Merge Sort algorithm to each of the two smaller sublists created in the previous step.
  3. Merge: Once both halves are sorted, merge them back together to create a single sorted list. This is where the "merge" in Merge Sort comes into play.
    • Start with an empty result list.
    • Compare the first elements of both sorted halves.
    • Add the smaller of the two elements to the result list and remove it from its original list.
    • Repeat the comparison and addition process until one of the halves is empty.
    • Once one of the halves is empty, simply append the remaining elements of the other half to the result list since they are already sorted.
    • The result list is now a sorted combination of the two halves.
  4. Return: The final step is to return the merged, sorted list as the output.

Merge Sort has a time complexity of O(n log n), making it efficient for sorting large datasets. It is also a stable sort, which means that it maintains the relative order of equal elements in the sorted output. However, it does require additional memory space for the merging step, which might not make it the best choice for sorting very large lists with limited memory.

Source


///////////////////////////////////////////////////////////////////////
// 
// mergeSort.c
// 
// Written by: Don Dugger
//       Date: 2023-10-03
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>
 
///////////////////////////////////////////////////////////////////////
 
#define DATA_SIZE 25

void mergeSort(int *data, int left, int right);
void merge(int *data, int left, int middle, int right);
void createRandomData(int *data,int size, int seed);
void printArray(int data[], int size);
 
///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    mergeSort(data, 0, DATA_SIZE-1);
    printf("Sorted array is\n");
    printArray(data, DATA_SIZE);
 
 
    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

// Divide the array into two sub arrays,
// sort them and merge them.
void mergeSort(int *data, int left, int right)
{
   if (left < right) {
      // middle is the point where the array
      // is divided into two sub arrays.
      int middle = left + ((right - left) / 2); 

     mergeSort(data, left, middle);
     mergeSort(data, middle + 1, right);

      // Merge the sorted sub arrays.
      merge(data, left, middle, right);
   }

} // End of mergeSort()

///////////////////////////////////////////////////////////////////////

void merge(int *data, int left, int middle, int right)
{
   // Size of left & right segment.
   int left_size = middle - left + 1;
   int right_size = right - middle;

   // Allocate the left & right data segments.
   int left_data[left_size], right_data[right_size];

   // Copy the data in to the data segments.
   for (int idx = 0; idx < left_size; idx++)
      left_data[idx] = data[left + idx];
   for (int idx = 0; idx < right_size; idx++)
      right_data[idx] = data[middle + 1 + idx];

   // Allocate & set index's.
   int left_idx = 0, right_idx = 0, data_idx = left;

   // Merge segments back into data array.
   while ( left_idx < left_size && right_idx < right_size)
      if (left_data[left_idx] <= right_data[right_idx]) 
         data[data_idx++] = left_data[left_idx++];
      else
         data[data_idx++] = right_data[right_idx++];

   // Copy any remaining elements in left & right segments.
   while (left_idx < left_size)
      data[data_idx++] = left_data[left_idx++];
   while (right_idx < right_size)
      data[data_idx++] = right_data[right_idx++];

} // End of merge()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf("%2.2d ",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
// 
void printArray(int data[], int size)
{
    for (int i = 0; i < size; i++)
        printf("%2.2d ", data[i]);
    printf("\n");

} // End of printArray()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  heapSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-11-11
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def mergeSort(data):
    if len(data) > 1:

        # middle is the point where the array
        # is divided into two sub arrays.
        middle = len(data)//2
        # Left segment
        left = data[:middle]
        # Right segment
        right = data[middle:]
        # Sort left segment
        mergeSort(left)
        # Sort right segment
        mergeSort(right)
        # init indexs
        left_idx = right_idx = data_idx = 0
        # Merge segments back into data array.
        while left_idx < len(left) and right_idx < len(right):
            if left[left_idx] <= right[right_idx]:
                data[data_idx] = left[left_idx]
                left_idx += 1
            else:
                data[data_idx] = right[right_idx]
                right_idx += 1
            data_idx += 1

        # Copy any remaining elements in the left segments.
        while left_idx < len(left):
            data[data_idx] = left[left_idx]
            left_idx += 1
            data_idx += 1

        # Copy any remaining elements in the right segments.
        while right_idx < len(right):
            data[data_idx] = right[right_idx]
            right_idx += 1
            data_idx += 1



#######################################################################
# Main
if __name__ == '__main__':
    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)

    mergeSort(data)

    print("Sorted array is")
    print(data)

#######################################################################
######################## End of File ##################################
#######################################################################

Heap Sort

Download C Source
Download Python Source
Heap Sort Video ASWYouTube

Description

Heap Sort is a comparison-based sorting algorithm that efficiently transforms an unsorted array into a sorted one using a data structure called a binary heap. Once the entire array have been turned into a max heap, which is referred to as being heapified. The largest element in the array will be in the first location of the array. It is then swapped with the last element of the array, which is it's proper sorted location. Then the remaining portion, which is the unsorted portion will again heapified. And again the largest element of the unsorted portion will be in the first location of the array. And again it will be swapped, this time with the second to the last location, will be it's proper sorted location.

Here's a step-by-step explanation of how Heap Sort works:

  1. Build a Heap: First, you need to build a heap from the input list. A heap is a binary tree structure where the parent node has a value greater (for max-heap) or smaller (for min-heap) than its child nodes. The most common representation of a heap is an array, where the parent and child relationships are maintained through simple mathematical formulas.
    • To build a max-heap, you start from the last non-leaf node and move upwards, ensuring that the max-heap property is satisfied for each subtree.
    • To build a min-heap, the process is similar, but you make sure the min-heap property is satisfied instead.
  2. Heapify: After building the heap, you have a binary heap data structure. Now, the root of the heap contains the maximum (for max-heap) or minimum (for min-heap) element of the list.
  3. Extract and Sort: To sort the list, you repeatedly extract the maximum (or minimum) element from the heap and place it at the end of the sorted portion of the list. This operation reduces the size of the heap by one element. You repeat this process until the heap is empty.
    • For a max-heap (ascending order), you extract the maximum element and place it at the end of the list.
    • For a min-heap (descending order), you extract the minimum element and place it at the end of the list.
  4. Heapify After Extraction: After each extraction, the heap is no longer a valid heap because you've removed the root element. To maintain the heap property, you need to "heapify" the remaining elements. This involves moving the last element of the heap to the root and sifting it down to its proper position, ensuring that the max-heap (or min-heap) property is satisfied.
  5. Repeat and Sort: Continue the extraction and sorting process until the entire list is sorted.

Heap Sort has a time complexity of O(n log n), making it an efficient sorting algorithm for large datasets. It is an in-place sorting algorithm, meaning it doesn't require additional memory for sorting. However, it is not a stable sort, so the relative order of equal elements may not be preserved. Additionally, the process of building the initial heap takes O(n) time, and the heapify operation after each extraction takes O(log n) time, contributing to the overall time complexity.

Source


///////////////////////////////////////////////////////////////////////
// 
// heapSort.c
// 
// Written by: Don Dugger
//       Date: 2023-10-13
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>

///////////////////////////////////////////////////////////////////////

#define DATA_SIZE 25

void swap(int* xp, int* yp);
void heapify(int data[], int N, int i);
void heapSort(int data[], int N);
void printArray(int data[], int N);
void createRandomData(int *data,int size, int seed);

///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);


    // Function call
    heapSort(data, DATA_SIZE);
    printf("Sorted array is\n");
    printArray(data, DATA_SIZE);
 
    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////
// Function to swap the position of two elements
void swap(int* xp, int* yp)
{

    int temp = *xp;
    *xp = *yp;
    *yp = temp;

} // End of swap()

///////////////////////////////////////////////////////////////////////
// heapify
void heapify(int data[], int size, int root)
{
    // Find largest among root, left child and
    // right child Initialize largest as root
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    // If left is larger than root then largest is left
    if (left < size && data[left] > data[largest])
        largest = left;
    // If right is larger than largest then largest is right
    if (right < size && data[right] > data[largest])
        largest = right;
    // if root is not largest swap and continue heapifying
    if (largest != root) {
        swap(&data[root], &data[largest]);
        // Recursively heapify the affected sub-tree
        heapify(data, size, largest);
    }
} // End of heapify()

///////////////////////////////////////////////////////////////////////
// heapSort
void heapSort(int data[], int size)
{   // Build max heap
    for (int root = size / 2 - 1; root >= 0; root--)
        heapify(data, size, root);
    // Heap sort
    for (int root = size - 1; root >= 0; root--) {
        swap(&data[0], &data[root]);
        // Heapify root element to get 
        // highest element at root again
        heapify(data, root, 0);
    }
} // End of heapSort()

///////////////////////////////////////////////////////////////////////
// 
void printArray(int data[], int size)
{
    for (int i = 0; i < size; i++)
        printf("%2.2d ", data[i]);
    printf("\n");

} // End of printArray()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf("%2.2d ",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////

                        

#######################################################################
#  
#  heapSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-11-11
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def heapify(data, size, root):
    # Find largest among root, left child and
    # right child Initialize largest as root
    largest = root 
    left = 2 * root + 1
    right = 2 * root + 2

    # If left is larger than root then largest is left
    if left < size and data[largest] < data[left]:
        largest = left

    # If right is larger than largest then largest is right
    if right < size and data[largest] < data[right]:
        largest = right

    # if root is not largest swap and continue heapifying
    if largest != root:
        # swap
        data[root], data[largest] = data[largest], data[root]
        # Recursively heapify the affected sub-tree
        heapify(data, size, largest)

#######################################################################

def heapSort(data):
    size = len(data)

    # Build max heap
    for root in range(size//2 - 1, -1, -1):
        heapify(data, size, root)

    # Heap sort
    for root in range(size-1, 0, -1):
        data[root], data[0] = data[0], data[root] # swap
        heapify(data, root, 0)


#######################################################################
# Main
if __name__ == '__main__':
    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)

    heapSort(data)

    print("Sorted array is")
    print(data)

#######################################################################
######################## End of File ##################################
#######################################################################

Counting Sort

Download C Source
Download Python Source
Counting Sort Video ASWYouTube

Description

Counting Sort is a non-comparative, integer-based sorting algorithm, that works well when you have a limited range of integers in the data. It is most efficient when sorting a collection of integers within a small range. The range of the data is in direct proportion to the amount of memory needed. It's efficiency is because it doesn't involve any element comparisons. The algorithm works by counting the frequency of each element in the data and using that information to place the elements in the correct sorted order.

Steps in Counting Sort:

  1. Find the Range:
    • Determine the range of the input data by finding the minimum and maximum values.
  2. Create a Count Array:
    • Create a count array to store the frequency of each value within the range.
  3. Count the Elements:
    • Iterate through the input array and populate the count array with the occurrences of each element.
  4. Cumulative Count:
    • Update the count array to store cumulative sums. This determines the final positions of elements in the sorted array.
  5. Place Elements in Sorted Order:
    • Iterate through the input array in reverse order, placing each element in its correct position in the output array, and decrement its count in the count array.
  6. Copy the Output:
    • Copy the sorted elements from the output array back into the original array.

Characteristics:

  • Time Complexity:
    • O(n+k)O(n+k), where nn is the number of elements in the input array and kk is the range of the input values.
  • Space Complexity:
    • O(n+k)O(n+k), for the count array and output array.
  • Stability:
    • Counting sort is a stable sorting algorithm because elements with the same value appear in the same order as in the input array.

The implementation of the counting sort algorithm contains six loops.

  • The first loop determines the range of input elements. In this simulation we will assume zero as the low end of the range, so the loop will simply look for the maximum element.
  • The second loop simply zeros out the count array.
  • The third loop traverses the input array and counts each element and stores it in the count array.
  • Then the fourth loop cumulates the counts by adding each element to it's adjacent higher element.
  • The fifth loop traverses the input array and by using the input element as an index into the count array, determines the sorted location, in the output array. Then decrements the count element, which is the next occurrence of the input element's location in the output array.
  • And then the last loop moves the sorted data back to the original input array.

Source


///////////////////////////////////////////////////////////////////////
// 
// countingSort.c
// 
// Written by: Don Dugger
//       Date: 2023-11-11
//
// Copyright (C) 2023 Acme Software Works, Inc.
// 
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
// GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>
#include <time.h>

///////////////////////////////////////////////////////////////////////

#define DATA_SIZE 25

void countingSort(int data[], int size);
void printArray(int data[], int size);
void createRandomData(int *data,int size, int seed);

///////////////////////////////////////////////////////////////////////
///
///  main 
/// 
///////////////////////////////////////////////////////////////////////
int main()
{
    int seed = time(NULL);

    int data[DATA_SIZE];

    createRandomData(data,DATA_SIZE,seed);

    countingSort(data, DATA_SIZE);
    printf("Sorted array is\n");
    printArray(data, DATA_SIZE);
 
    return 0;

} // End of main()

///////////////////////////////////////////////////////////////////////

void countingSort(int data[], int size)
{
    // Find the largest element of the data
    int max = data[0];
    for (int idx = 1; idx < size; idx++)
        if (data[idx] > max)
            max = data[idx];
    // The size of the count array must 
    // be at least max+1 to accommodate zero.
    int *count  = (int *)malloc((max+1) * sizeof(int));
    // Zero out the count array.
    for (int idx = 0; idx <= max; ++idx)
        count[idx] = 0;
    // Count the elements.
    for (int idx = 0; idx < size; idx++)
        count[data[idx]]++;
    // Cumulate the counts.
    for (int idx = 1; idx <= max; idx++)
        count[idx] += count[idx - 1];
    // Using the index of each element of the original
    // array in count, place the elements in output.
    int output[size];
    for (int idx = size - 1; idx >= 0; idx--) {
        output[count[data[idx]] - 1] = data[idx];
        count[data[idx]]--;
    }
    // Copy the sorted elements into original array
    for (int idx = 0; idx < size; idx++)
        data[idx] = output[idx];
    // Free allocated memory
    free(count);
} // End of countingSort()

///////////////////////////////////////////////////////////////////////

void createRandomData(int *data,int size, int seed)
{
    srand(seed);
    for ( int i = 0; i < size; ++i) {
        data[i] = (rand() % 100);
        printf("%2.2d ",data[i]);
    }
    printf("\n");

} // End of createRandomData()

///////////////////////////////////////////////////////////////////////
// 
void printArray(int data[], int size)
{
    for (int i = 0; i < size; i++)
        printf("%2.2d ", data[i]);
    printf("\n");

} // End of printArray()

///////////////////////////////////////////////////////////////////////
//////////////////////// End of File //////////////////////////////////
///////////////////////////////////////////////////////////////////////
                        

#######################################################################
#  
#  countingSort.py
#  
#  Written by: Don Dugger
#        Date: 2023-11-11
# 
#  Copyright (C) 2023 Acme Software Works, Inc.
#  
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#######################################################################

import random

#######################################################################

def countingSort(data):
    # Find the largest element of the data
    maximum = max(data)

    # Zero out the count array.
    count = [0] * (maximum + 1)
    # Count the elements.
    for num in data:
        count[num] += 1

    # Cumulate the counts.
    for i in range(1, maximum + 1):
        count[i] += count[i - 1]

    # Using the index of each element of the original
    # array in count, place the elements in output.
    output = [0] * len(data)
    for i in range(len(data) - 1, -1, -1):
        output[count[data[i]] - 1] = data[i]
        count[data[i]] -= 1

    return output

#######################################################################
# Main
if __name__ == "__main__":
    size = 25
    data = []

    for i in range(size):
        data.append(random.randrange(0,99))
    print(data)

    print("Sorted array is")
    print(countingSort(data))

#######################################################################
######################## End of File ##################################
#######################################################################

For more information: info@acmesoftwareworks.com