Various sorting algorithms
#include
using namespace std;
//look at SortQuick to see how to properly pass arrays, pointers, etc
void printarray(int arr[],int n) {
for(int i=0;i
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
//inefficient at O(n^2)
void selectionSort(int arr[], int n) {
int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
//inefficient at O(n^2)
void insertionSort(int arr[], int length) {
int i, j, tmp;
for (i = 1; i < length; i++) {
j = i;
while (j > 0 && arr[j – 1] > arr[j]) {
tmp = arr[j];
arr[j] = arr[j – 1];
arr[j – 1] = tmp;
j–;
}
}
}
//look at SortQuick to see how to properly pass arrays, pointers, etc
//moderate at O(n log n)
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
// m - size of A
// n - size of B
// size of C array must be equal or greater than
// m + n
//merge sort of 2 sorted arrays into 3 array
//time complexity is O(n+m) space is O(n+m)
void merge(int m, int n, int A[], int B[], int C[]) {
int i, j, k;
i = 0;
j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
int main() {
int y[]={10,20,21,1,13,29,70,4,5,11,8};
printarray(y, 11);
// bubbleSort(y,11);
// selectionSort(y,11);
// insertionSort(y,11);
quickSort(y,0,11);
cout<<"after sort"<