-
Notifications
You must be signed in to change notification settings - Fork 522
/
Quicksort_Radixsort.cpp
129 lines (102 loc) · 3.55 KB
/
Quicksort_Radixsort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*The code is for the
1.Quick sort
Description: Quick Sort is a divide-and-conquer algorithm. It selects a "pivot" element and partitions the array into two halves such that elements smaller than the pivot go to the left and elements larger go to the right. This process is repeated recursively for the left and right subarrays.
// Time Complexity:*/
// Best Case: O(n log n)
// Worst Case: O(n²)
// Average Case: O(n log n)
// Now first code
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
// //Now moving to second code
// 2.Radix sort
// Description: Radix Sort is a non-comparative sorting algorithm. It sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It uses a stable sorting algorithm like counting sort as a subroutine to sort individual digits.
// Time Complexity:
// Best Case: O(nk), where n is the number of elements, and k is the number of digits.
// Worst Case: O(nk)
// second code
#include <iostream>
using namespace std;
// A utility function to get the maximum value in arr[]
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
return max;
}
// A function to do counting sort of arr[] according to the digit represented by exp
void countingSort(int arr[], int n, int exp) {
int output[n]; // output array
int count[10] = {0}; // count array to store occurrences
// Store count of occurrences in count[]
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that count[i] now contains the actual position of this digit in output[]
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now contains sorted numbers
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] using Radix Sort
void radixSort(int arr[], int n) {
// Find the maximum number to know the number of digits
int max = getMax(arr, n);
// Do counting sort for every digit. Instead of passing the digit number, exp is passed.
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
// thakyou forthis opportunity