# Untitled

unknown
c_cpp
2 years ago
7.8 kB
2
Indexable
Never
```//-------------------------------
// 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);
}

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

#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];

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

//-------------------------------```