c: Sorting Algorithms

/*****************************************************************//**
 * \file   SortAlgorithm.c
 * \brief  c Sorting Algorithms 业务操作方法
 * VSCODE   c11  https://stackoverflow.com/questions/71924077/configuring-task-json-and-launch-json-for-c-in-vs-code
 * https://www.programiz.com/dsa/counting-sort
 * https://www.geeksforgeeks.org/sorting-algorithms/
 * 安装插件“Doxygen Documentation Generator”，用来生成注释。
 * 安装插件”C/C++ Snippets”，用来生成文件头、代码块分割线等。
 * \author geovindu,Geovin Du
 * \date   2023-09-19
***********************************************************************/
 
 
#include <stdio.h>
#include <stdlib.h>
 
 
#define MAXSIZE 100 

/** 
 * @brief 1。Bubble Sort冒泡排序法
 * @param data    INT 数组
 * @param lensize   数组长度
 *
 * @return 排序好的数组
 *     -<em>数组</em> 整型数组
 *     -<em>数组</em> 整型数组
 */
int* BubbleSort(int* data,int lensize)
{
    int i,j,tmp;
    int* newdate;
    /* 原始数据 */
    //int lensize=sizeof(data) / sizeof(data [0]);//sizeof(data); //sizeof(data) / sizeof(data[0]);//
    printf("2共 長度是：%d ",lensize);
    printf("冒泡排序法：\n原始数据为:");
    for (i=0;i<lensize;i++)
        printf("%3d",data[i]);
    printf("\n");
 
    for (i=(lensize-1);i>=0;i--)     /* 扫描次数 */
    {
        for (j=0;j<i;j++)/*比较、交换次数*/
        {
            if (data[j]>data[j+1])   /* 比较相邻两数，如第一个数较大则交换 */
            {
                tmp=data[j];
                data[j]=data[j+1];
                data[j+1]=tmp;
            }
        }
        printf("第 %d 次排序后的结果是：",lensize-i); /*把各次扫描后的结果打印出来*/
        for (j=0;j<lensize;j++)
            printf("%3d",data[j]);
        printf("\n");
    }
    //printf("最终排序的结果为：");
    for (i=0;i<lensize;i++)
        //newdate[i]=data[i];
        printf("%3d",data[i]);
    printf("\n");
 
    return data;
 
}
 
 
void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
 

/** 
 * @brief 2 C Program for Selection Sort 选择排序
 * @param arr    INT 数组
 * @param size   数组长度
 *
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void selectionSort(int arr[], int len)
{
    int i,j;
 
        for (i = 0 ; i < len - 1 ; i++)
       {
                int min = i;
                for (j = i + 1; j < len; j++)     //走訪未排序的元素
                        if (arr[j] < arr[min])    //找到目前最小值
                                min = j;    //紀錄最小值
                swap(&arr[min], &arr[i]);    //做交換
        }
 
     
 
}


/** 
 * @brief 3 Insertion Sort插入排序
 * @param arr    INT 数组
 * @param size   数组长度
 *
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */

void InsertionSort(int arr[], int size){  
  
    // defining some iterables and variables  
    int i, temp, j;  
  
    // using the for-loop  
    for (i = 1; i < size; i++){  
        // initializing the temp variable as value at index i from array  
        temp = arr[i];  
        // initializing another iterable value  
        j = i - 1;  
        // using the while loop for j >= 0 and arr[j] > temp  
        while (j >= 0 && arr[j] > temp){  
            // swapping the elements  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = temp;  
    }  
}  

void qswap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
 
/** 
 * @brief 4 Quick Sort 快速排序
 * @param arr    INT 数组
 * @param size   数组长度
 *
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */

int partition(int arr[], int low, int high)
{
    // Choosing the pivot
    int pivot = arr[high];
 
    // Index of smaller element and indicates
    // the right position of pivot found so far
    int qi = (low - 1);
 
    for (int j = low; j <= high - 1; j++) {
 
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {             
           qi++;
           qswap(&arr[qi], &arr[j]);
        }
    }
    qswap(&arr[qi + 1], &arr[high]);
    return (qi + 1);
}

/** 
 * @brief 4 Quick Sort 快速排序
 * @param arr    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void QuickSort(int arr[], int low, int high){  
 if (low < high) {
 
        // pi is partitioning index, arr[p]
        // is now at right place
        int pi = partition(arr, low, high);
 
        // Separately sort elements before
        // partition and after partition
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}  


void merge(int array[], int const left, int const mid,
           int const right)
{
    int const subArrayOne = mid - left + 1;
    int const subArrayTwo = right - mid;
 
    // Create temp arrays
    int* leftArray =(int*)malloc(subArrayOne);// int [subArrayOne];
    int* rightArray = (int*)malloc(subArrayTwo);//int [subArrayTwo];
 
    // Copy data to temp arrays leftArray[] and rightArray[]
    for (int i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (int j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];
 
    int indexOfSubArrayOne = 0;
    int indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;
 
    // Merge the temp arrays back into array[left..right]
    while (indexOfSubArrayOne < subArrayOne
           && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne]
            <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray]
                = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray]
                = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
 
    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray]
            = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
 
    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray]
            = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }

    //delete[] leftArray;
    
    //delete[] rightArray;
}
 
/** 
 * @brief 5 Merge Sort 合并/归并排序
 * @param arr    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void MergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return;
 
    int mid = begin + (end - begin) / 2;
    MergeSort(array, begin, mid);
    MergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

/** 
 * @brief 6 Counting Sort 计数排序
 * @param arr    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void CountingSort(int array[], int size) {
  int output[10];

  // Find the largest element of the array
  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  // The size of count must be at least (max+1) but
  // we cannot declare it as int count(max+1) in C as
  // it does not support dynamic memory allocation.
  // So, its size is provided statically.
  int count[10];

  // Initialize count array with all zeros.
  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  // Store the count of each element
  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  // Store the cummulative count of each array
  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // Find the index of each element of the original array in count array, and
  // place the elements in output array
  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

  // Copy the sorted elements into original array
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}


int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

void radcountingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((array[i] / place) % 10) > max)
      max = array[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  // Calculate count of elements
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;
    
  // Calculate cumulative count
  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

  // Place the elements in sorted order
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}


/** 
 * @brief 7 Radix Sort 基数排序
 * @param arr    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void Radixsort(int array[], int size) {
  // Get maximum element
  int max = getMax(array, size);

  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    radcountingSort(array, size, place);
}

//这个数是有规则的
#define NARRAY 9   // Array size 7
#define NBUCKET 8  // Number of buckets  6
#define INTERVAL 12  // Each bucket capacity  10


struct Node {
  int data;
  struct Node *next;
};

struct Node *BucketInsertionSort(struct Node *list);
//void printBuckets(struct Node *list);

int getBucketIndex(int value);


/** 
 * @brief 8 Radix Sort 基数排序
 * @param arr    INT 数组
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void BucketSort(int arr[]) {
  int i, j;
  struct Node **buckets;

  // Create buckets and allocate memory size
  buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);

  // Initialize empty buckets
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = NULL;
  }

  // Fill the buckets with respective elements
  for (i = 0; i < NARRAY; ++i) {
    struct Node *current;
    int pos = getBucketIndex(arr[i]);
    current = (struct Node *)malloc(sizeof(struct Node));
    current->data = arr[i];
    current->next = buckets[pos];
    buckets[pos] = current;
  }

  // Print the buckets along with their elements
  //for (i = 0; i < NBUCKET; i++) {
    //printf("Bucket[%d]: ", i);
    //printBuckets(buckets[i]);
    //printf("\n");
  //}

  // Sort the elements of each bucket
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = BucketInsertionSort(buckets[i]);
  }

  //printf("-------------\n");
  //printf("Bucktets after sorting\n");
 // for (i = 0; i < NBUCKET; i++) {
    //printf("Bucket[%d]: ", i);
    //printBuckets(buckets[i]);
    //printf("\n");
 // }

  // Put sorted elements on arr
  for (j = 0, i = 0; i < NBUCKET; ++i) {
    struct Node *node;
    node = buckets[i];
    while (node) {
      arr[j++] = node->data;
      node = node->next;
    }
  }

  return;
}


struct Node* BucketInsertionSort(struct Node *list) {
  struct Node *k, *nodeList;
  if (list == 0 || list->next == 0) {
    return list;
  }

  nodeList = list;
  k = list->next;
  nodeList->next = 0;
  while (k != 0) {
    struct Node *ptr;
    if (nodeList->data > k->data) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = nodeList;
      nodeList = tmp;
      continue;
    }

    for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
      if (ptr->next->data > k->data)
        break;
    }

    if (ptr->next != 0) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = ptr->next;
      ptr->next = tmp;
      continue;
    } else {
      ptr->next = k;
      k = k->next;
      ptr->next->next = 0;
      continue;
    }
  }
  return nodeList;
}

int getBucketIndex(int value) {
  return value / INTERVAL;
}

void printBuckets(struct Node *list) {
  struct Node *cur = list;
  while (cur) {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}


void heapify(int arr[], int n, int i) {
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
  
    if (left < n && arr[left] > arr[largest])
      largest = left;
  
    if (right < n && arr[right] > arr[largest])
      largest = right;
  
    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
  }


/** 
 * @brief 9 Heap Sort 堆排序
 * @param arr    INT 数组
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void HeapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);
  
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }
}
  
/** 
 * @brief 10 Heap Sort 希尔排序
 * @param arr    INT 数组
 * @param n 数组长度
 * @return 返回说明
 *     -<em>false</em> fail
 *     -<em>true</em> succeed
 */
void ShellSort(int array[], int n) {
  // Rearrange elements at each n/2, n/4, n/8, ... intervals
 for (int gap = n/2; gap > 0; gap /= 2)
    {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is
        // gap sorted 
        for (int i = gap; i < n; i += 1)
        {
            // add a[i] to the elements that have been gap sorted
            // save a[i] in temp and make a hole at position i
            int temp = array[i];
  
            // shift earlier gap-sorted elements up until the correct 
            // location for a[i] is found
            int j;            
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
                array[j] = array[j - gap];
              
            //  put temp (the original a[i]) in its correct location
            array[j] = temp;
        }
    }
    

  /*
  for (int interval = n / 2; interval > 0; interval /= 2) {
    for (int i = interval; i < n; i += 1) {
      int temp = array[i];
      int j;
      for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
        array[j] = array[j - interval];
      }
      array[j] = temp;
    }
  }
  */
}

/*
 * @Author: 涂聚文 geovindu,Geovin Du
 * @Date: 2023-09-11 14:07:29
 * @LastEditors: 
 * @LastEditTime: 2023-09-20 14:35:49
 * @FilePath: \testcpp\helloword.c
 * @Description: 
 */
/*****************************************************************//**
 * \file   helloworld.C
 * \brief  业务操作方法
 * VSCODE   c11         安装插件“Doxygen Documentation Generator”，用来生成注释。
                        安装插件”C/C++ Snippets”，用来生成文件头、代码块分割线等。KoroFileHeader
                        C/C++ Snippets插件设置
 * \author geovindu,Geovin Du
 * \date   2023-09-19
***********************************************************************/

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include "include/SortAlgorithm.h"


int main()
{
    printf("hello world, c \n");
    printf("你好，中国\n");


    int i;
    int *p;   
    char str[20];
    //1冒泡排序
    int data[12]={60,50,39,27,12,8,45,63,20,2,10,88};   /* 原始数据 */
    int lensize=sizeof(data) / sizeof(data [0]);//sizeof(data);
    p=BubbleSort(data,lensize);
     
    itoa(lensize, str, 10);
    printf("1共長度是 %d ",lensize);
     
    printf("\n1冒泡排序的结果为:");
    for (i=0;i<lensize;i++)
        printf("%3d",p[i]);
    printf("\n");
    //2选择排序
    int arr[] = { 64, 25, 12, 22, 11,88,28,100 };
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    int ii;
    printf("2选择排序结果为:");
    for(ii = 0; ii < n; ii++)
        printf("%d ", arr[ii]);
    printf("\n");
    //3插入排序
     int inarr[] = {25, 23, 28, 16, 18,100,8,99};  
  
    // calculating the size of array  
    int size = sizeof(inarr) / sizeof(inarr[0]);  
    printf("3插入排序结果为:");
    InsertionSort(inarr, size);  
        for(ii = 0; ii < n; ii++)
        printf("%d ", inarr[ii]);
    printf("\n");

    //4快速排序
    // defining and initializing an array  
    int qsarr[] = {100,25, 23, 28, 16, 18,8,99,3,20}; 
    printf("4快速排序结果为:");
    // calculating the size of array  
    size = sizeof(qsarr) / sizeof(qsarr[0]);  
    QuickSort(qsarr, 0, size - 1);  
    for (int i = 0; i < size; i++) 
        printf("%d ", qsarr[i]);
    printf("\n");
    //5 合并排序
    printf("5合并排序结果为:");
    int mearr[] = { 12, 11, 23, 55, 6, 57,3,100,9 };
    int arr_size = sizeof(mearr) / sizeof(mearr[0]);
    MergeSort(mearr, 0, arr_size - 1);
    for (int i = 0; i < arr_size; i++) 
        printf("%d ", mearr[i]);
    printf("\n");

    //6 计数排序
    printf("6计数排序结果为:");
    int carray[] = {4, 2, 2, 8, 3, 3, 1};
    int cn = sizeof(carray) / sizeof(carray[0]);
    CountingSort(carray, cn);
    for (int i = 0; i < cn; i++) 
        printf("%d ", carray[i]);
    printf("\n");

    //7. 基数排序
    printf("7基数排序结果为:");
    int rarray[] = {121, 432, 564, 23, 1, 45, 788};
    int rn = sizeof(rarray) / sizeof(rarray[0]);
    Radixsort(rarray, rn);
    for (int i = 0; i < rn; i++) 
        printf("%d ", rarray[i]);
    printf("\n");

    //8 Bucket Sort 桶排序
    printf("8桶排序结果为:");
    int barray[] = {42, 32, 33, 5,52, 37,100, 47, 51};
    BucketSort(barray);
    int bn = sizeof(barray) / sizeof(barray[0]);
    for (int i = 0; i < bn; i++) 
        printf("%d ", barray[i]);
    printf("\n");
    //9堆排序
    printf("9堆排序结果为:");
    int harr[] = {1, 12, 9, 5, 6, 10};
    int hn = sizeof(harr) / sizeof(harr[0]);  
    HeapSort(harr, hn);
    for (int i = 0; i < hn; i++) 
        printf("%d ", harr[i]);
    printf("\n");

    //10.希尔排序
    printf("10.希尔排序结果为:");
    int sdata[] = {9, 8, 3, 7, 25, 6, 4, 11,38};
    int ssize = sizeof(sdata) / sizeof(sdata[0]);
    ShellSort(sdata, ssize);
    for (int i = 0; i < ssize; i++) 
        printf("%d ", sdata[i]);
    printf("\n");





    system("pause");
    return 0;
    
}