The sorting technique refers to the processes of arranging and rearranging groups of data in some specific order. There are many sorting techniques in the data structure some are mentioned below:
1. Bucker sort
2. Insertion sort
3. Merge sort
4. Quick Sort
5. Selection sort
Bucket Sort:
//The real-life example of bucket sort. The scenario is employee data, which is sorted by using the bucket sorting technique.
#include<iostream>
#include<stdio.h>
using namespace std;
typedef struct employee{
char name[10];
float salary;
}Employee;
void Bucket_Sort(int array[], int n)
{
int i, j;
int count[n];
for(i=0; i < n; i++){
count[i] = 0;
}
for(i=0; i < n; i++)
{
(count[array[i]])++;
}
for(i=0,j=0; i < n; i++)
{
for(; count[i]>0;(count[i])--)
{
array[j++] = i;
}
}
}
int main()
{
int array[100];
int a,i;
cout<<"Enter How many Numbers of Employees : ";
cin>>a;
cout<<"\n\nEnter the numbers of Employees to be sorted:\n";
for(i = 0; i < a; i++ )
{
cin>>array[i];
}
cout<<"\nThe array of elements before sorting : \n";
for (i = 0;i < a;i++)
{
cin>>array[i];
}
cout<<"\nThe array of elements after sorting : \n";
Bucket_Sort(array, a);
for (i = 0;i < a;i++)
{
cout<<array[i];
}
cout<<"\n";
return 0;
}
Insertion sort:
//The real-life example of insertion sort. The scenario is students' data, which is sorted by using the insertion sorting technique.
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
int a[10];
int i,j,k,temp,z;
cout<<"\n How many number of Students do you want?\n\n";
cin>>z;
cout<<"\n Enter Student numbers\n";
for(i=0;i<z;i++)
cin>>a[i];
cout<<"\n\n Student numbers are\n\n";
for(i=0;i<z;i++)
cout<<"\t"<<a[i];
for(i=1;i<z;i++)
{
temp=a[i];
k=i-1;
while((k>=0)&&(a[k]>temp))
{
a[k+1]=a[k];
k=k-1;
}
a[k+1]=temp;
}
//insertion sorting
cout<<"\n\n Array after insertion sorting\n\n";
for(i=0;i<z;i++)
cout<<"\t"<<a[i];
}
Merge sort:
//The real-life example of merge sort. The scenario is teachers’ data, which is sorted by using the merge sorting technique.
#include<iostream>
using namespace std;
void Merge(int* A,int,int,int);
void Merge_Sort(int* A,int p,int r);
int main()
{
int a[] = {145, 0, 645, 3, -556, -35, 21324, 43, 545};
int len = 9;
cout << "\nOriginal number of teachers :\n";
for(int i=0; i<len; i++) {
cout << a[i] << "\n ";
}
Merge_Sort(a,0,len-1);
cout << "\n\n Sorted numbers of teachers :\n";
for(int i=0; i<len; i++) {
cout << a[i] << " \n";
}
return 0;
}
void Merge(int* arr,int p,int q,int r) {
int n1=q-p+1;
int n2=r-q;
int L[n1+1];
int R[n2+1];
for(int i=0; i<n1; i++) L[i]=arr[p+i];
for(int j=0; j<n2; j++) R[j]=arr[q+1+j];
int i=0;
int j=0;
int n=0;
while(i!=n1 && j!=n2) {
if(L[i]>R[j]) {
arr[p+n]=R[j];
j++;
} else {
arr[p+n]=L[i];
i++;
}
n++;
}
while(j!=n2) {
arr[p+n]=R[j];
j++;
n++;
}
while(i!=n1) {
arr[p+n]=L[i];
i++;
n++;
}
}
void Merge_Sort(int* arr,int p,int r) {
if(r>p) {
int q;
q=(p+r)/2;
Merge_Sort(arr,p,q);
Merge_Sort(arr,q+1,r);
Merge(arr,p,q,r);
}
}
Quick Sort:
//The real-life example of quicksort. The scenario is salesman data, which is sorted by using the quick sorting technique.
#include<iostream>
#include <stdio.h>
using namespace std;
typedef struct salesman{
char name[81];
float salary;
}Employee;
void sort(salesman **tab, int begin, int end){
float p = tab[(begin + end) / 2]->salary; /* float needed for compare == */
int i = begin, j = end;
Employee *tmp; /* microsoft is c89 */
while(i <= j){ /* using while */
while(tab[i]->salary > p) i++; /* >, <= pivot stops scan */
while(tab[j]->salary < p) j--; /* <, >= pivot stops scan */
if(i > j) /* using break */
break;
tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
i++; j--;
}
if(begin < j) sort(tab, begin, j);
if(end > i) sort(tab, i, end);
}
int main(int argc, char**argv)
{
salesman tab[] = {{"Hina", 525.}, {"Samina", 520.},
{"Sumbul", 537.},{"Seher", 523.},
{"Sadaf", 548.},{"Amna", 524.},
{"Rizwana", 527.},{"Batool", 541.},
{"Samiya", 521.},{"Farhana", 531.}};
Employee *ptr[sizeof(tab)/sizeof(tab[0])];
int i;
cout<<"Quick sorted elements"<<endl;
/* create array of pointers */
for(i = 0; i < (sizeof(tab)/sizeof(tab[0])); i++)
ptr[i] = &tab[i];
sort(ptr, 0, sizeof(ptr)/sizeof(ptr[0])-1);
for(i = 0; i < (sizeof(ptr)/sizeof(ptr[0])); i++)
cout<<"\n "<< ptr[i]->name<< ptr[i]->salary;
return 0;
}
Selection sort:
//The real-life example of selection sort. The scenario is salesman data, which is sorted by using the selection sorting technique.
#include <iostream>
#include <iomanip>
using namespace std;
// Constant for the array size.
const int ARRAY_SIZE = 4;
// Function Prototypes
void getSalesmanInfo(long [], int [], double [], double [], int);
//void bubbleSort(long salesamnId[],int hours[],double payRate[],double wages[],int size);
void selectionSort(long salesmanId[],int hours[],double payRate[],double wages[],int size);
void displayWages(long salesmanId[], double wages[], int size);
int main()
{
// Array of salesman ID numbers
long salesmanId[ARRAY_SIZE] = { 2134,5987 , 36475,5857};
// Array to hold the hours worked for each salesman
int hours[ARRAY_SIZE] = {0};
// Array to hold the hourly pay rate for each salesman
double payRate[ARRAY_SIZE] = {0};
// Array to hold the gross wages for each employee
double wages[ARRAY_SIZE] = {0};
// Get the salesman payroll information and store
getSalesmanInfo(salesmanId, hours, payRate, wages, ARRAY_SIZE);
// Display the UNSORTED payroll information.
cout << "This is the unsorted payroll information: " << endl;
displayWages(salesmanId, wages, ARRAY_SIZE);
// Sort the payroll information in ascending order with a bubble sort.
// bubbleSort(salesmanId, hours, payRate, wages, ARRAY_SIZE);
// Sort the payroll information with in ascending order a selection sort.
selectionSort(salesmanId, hours, payRate, wages, ARRAY_SIZE);
// Display the SORTED payroll information.
cout << "This is the sorted payroll information: " << endl;
displayWages (salesmanId, wages, ARRAY_SIZE);
system("PAUSE");
return 0;
}
void getSalesmanInfo(long salesman[], int hrs[], double rate[],double pay[], int size)
{
cout << "Enter the requested information "<< "for each salesman.\n";
// Get the information for each salesman.
for (int count = 0; count < size; count++)
{
cout << "\nSalesman #: " << salesman[count] << "\t";
// Get this salesman hours worked.
cout << "Hours worked: ";
cin >> hrs[count];
// Validate hours worked.
while (hrs < 0)
{
cout << "\nHours worked must be 0 or more. "
<< "Please re-enter: ";
cin >> hrs[count];
}
// Get this salesman pay rate.
cout << "\tPay rate: $";
cin >> rate[count];
// Validate the pay rate.
while (rate[count] < 6.00)
{
cout << "\nPay rate must be 6.00 or more. "
<< "Please re-enter: $";
cin >> rate[count];
}
// Calculate this salesman gross pay.
pay[count] = hrs[count]*rate[count];
// ADD statement to calculate wages by multiplying
// hours with rate of pay;
}
}
// The bubbleSort function sorts the information based on
// the wages array.
//void bubbleSort(long salesmanId[],int hours[],double payRate[],double wages[],int size)
//{
// bool swap;
// double temp1;
// int temp2;
// long temp3;
// do
// {
// swap = false;
// for (int count = 0; count < (size - 1); count++)
// {
// // compare the wages, because that is what you are sorting on
// if (wages[count] > wages [count + 1])
// {
// // swap all the data between the two array positions:
// temp1 = wages[count];
// wages[count] = wages[count + 1];
// wages[count + 1] = temp1;
// temp1 = payRate[count];
// payRate[count] = payRate[count + 1];
// payRate[count + 1] = temp1;
// temp2 = hours[count];
// hours[count] = hours[count + 1];
// hours[count + 1] = temp2;
// temp3 = empId[count];
// salesmanId[count] = salesmanId[count + 1];
// salesmanId[count + 1] = temp3;
// swap = true;
// }
// }
//
// } while (swap);
//}
void selectionSort(long salesmanId[],int hours[],double payRate[],double wages[],int size)
{
int startScan, minIndex;
double minValue1, minValue2;
int minValue3;
long minValue4;
for (startScan = 0; startScan < (size - 1); startScan++)
{
minIndex = startScan;
minValue1 = wages[startScan];
minValue2 = payRate[startScan];
minValue3 = hours[startScan];
minValue4 = salesmanId[startScan];
for (int index = startScan + 1; index < size; index++)
{
if (wages[index] < minValue1)
{
minValue1 = wages[index];
minIndex = index;
minValue2 = payRate[index];
minIndex = index;
minValue3 = hours[index];
minIndex = index;
minValue4 = salesmanId[index];
minIndex = index;
}
}
wages[minIndex] = wages[startScan];
wages[startScan] = minValue1;
payRate[minIndex] = payRate[startScan];
payRate[startScan] = minValue2;
hours[minIndex] = hours[startScan];
hours[startScan] = minValue3;
salesmanId[minIndex] = salesmanId[startScan];
salesmanId[startScan] = minValue4;
}
}
void displayWages(long salesmanId[], double wages[], int size)
{
// Set up the numeric output formatting.
cout << fixed << showpoint << setprecision(2) << endl;
// Display the header.
cout << "----------------------------\n";
cout << "Salesman Wages\n";
cout << "----------------------------\n\n";
// Display each salessman pay.
for (int count = 0; count < ARRAY_SIZE; count++)
{
cout << "Salesman " << salesmanId[count] << " $";
cout << setw(7) << wages[count] << endl << endl;
}
}
Software: DEV C++
0 Comments