Untitled

//-------------------------------
// qsort

#include <bits/stdc++.h>

using namespace std;

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b; //小到大
};

int main()
{
    int n = 0;
    cin >> n;
    int *arr = new int[n];
    int tmp;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        arr[i] = tmp;
    }
    qsort(arr, n, sizeof(int), cmp); // a[n]
    for (int i = 0; i < n; i++)
    {
        cout << arr[i];
    }
    return 0;
}

//-------------------------------
// heap sort

#include <iostream>
using namespace std;

void heapify(int *&arr, int N, int i)
{

    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < N && arr[l] > arr[largest])
        largest = l;

    if (r < N && arr[r] > arr[largest])
        largest = r;

    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        heapify(arr, N, largest);
    }
}

void heapSort(int *&arr, int N)
{
    for (int i = N / 2 - 1; i >= 0; i--)
    {
        heapify(arr, N, i);
    }

    for (int i = 0; i < N; ++i)
    {
        cout << arr[i] << " ";
    }

    for (int i = N - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);

        heapify(arr, i, 0);
    }
}

void printArray(int *&arr, int N)
{
    for (int i = 0; i < N; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";
}
int main()
{
    int *arr = new int[6];
    int tmp = 0;
    for (int i = 0; i < 6; i++)
    {
        cin >> tmp;
        arr[i] = tmp;
    }

    // int N = sizeof(arr) / sizeof(arr[0]);
    //! Note that if you pass an array to a function, the above won't work since the array decays to a pointer and sizeof(array) returns the size of the pointer.
    int N = 6;

    // Function call
    heapSort(arr, N);

    cout << "Sorted array is \n";
    printArray(arr, N);
}

//-------------------------------
// radix sort

#include <bits/stdc++.h>
using namespace std;
int findMax(int arr[], int n)
{
    int i, max = arr[0], cnt = 0;
    for (i = 1; i < n; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }
    while (max > 0)
    {
        cnt++;
        max = max / 10;
    }

    return cnt;
}

void radixSort(int arr[], int *bucket[], int n)
{
    static int i, j[10], k, l, d = 1;
    int digit = 0;
    digit = findMax(arr, n);
    // cout << "c: " << c << endl;

    for (int m = 0; m < digit; m++)
    {
        for (i = 0; i < 10; i++)
            j[i] = 0;
        for (i = 0; i < n; i++)
        {
            k = (arr[i] / d) % 10;
            cout << "k: " << k << endl;

            bucket[k][j[k]++] = arr[i];
        }
        cout << "--------------------- " << endl;

        l = 0;                   // array index
        for (i = 0; i < 10; i++) // bucker row
        {
            for (k = 0; k < j[i]; k++) // bucket col
                arr[l++] = bucket[i][k];
        }
        for (int t = 0; t < l; t++)
        {
            cout << "arr[t]: " << arr[t] << endl;
        }

        d *= 10;
    }
}
int main()
{
    int n, *arr, i;
    int *bucket[10];
    cout << "Enter no of element : ";
    cin >> n;
    arr = new int[n + 1];
    for (i = 0; i < 10; i++)
        bucket[i] = new int[n];
    cout << "Enter array element : ";
    for (i = 0; i < n; i++)
        cin >> arr[i];
    radixSort(arr, bucket, n);

    cout << "Sorted array : ";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

//-------------------------------
// bucket sort

// Bucket sort in C++

#include <iomanip>
#include <iostream>
using namespace std;

#define NARRAY 7    // Array size
#define NBUCKET 6   // Number of buckets
#define INTERVAL 10 // Each bucket capacity

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

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

// Sorting function
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++)
    {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }

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

    cout << "-------------" << endl;
    cout << "Bucktets after sorted" << endl;
    for (i = 0; i < NBUCKET; i++)
    {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }

    // 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;
        }
    }

    for (i = 0; i < NBUCKET; ++i)
    {
        struct Node *node;
        node = buckets[i];
        while (node)
        {
            struct Node *tmp;
            tmp = node;
            node = node->next;
            free(tmp);
        }
    }
    free(buckets);
    return;
}

// Function to sort the elements of each bucket
struct Node *InsertionSort(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;
}

// Print buckets
void print(int ar[])
{
    int i;
    for (i = 0; i < NARRAY; ++i)
    {
        cout << setw(3) << ar[i];
    }
    cout << endl;
}

void printBuckets(struct Node *list)
{
    struct Node *cur = list;
    while (cur)
    {
        cout << setw(3) << cur->data;
        cur = cur->next;
    }
}

// Driver code
int main(void)
{
    int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};

    cout << "Initial array: " << endl;
    print(array);
    cout << "-------------" << endl;

    BucketSort(array);
    cout << "-------------" << endl;
    cout << "Sorted array: " << endl;
    print(array);
}

//-------------------------------