Sorting algorithms
Sameh
c_cpp
10 months ago
5.4 kB
3
Indexable
Never
#include <iostream> #include <ctime> using namespace std; void generateRandomArray(int *a , int sizeofArray) { srand(time(NULL)); for(int i = 0 ; i < sizeofArray ; i++) { a[i] = rand() % 101; } } void printArray(int * a , int sizeOfArray) { for (int i = 0 ; i < sizeOfArray ; i++) { cout << a[i] << "\t"; } cout << "\n"; } int partitioning (int * a , int firstIndex , int lastIndex) { int rightCounter = firstIndex + 1; int leftCounter = lastIndex; int pivot = a[firstIndex]; int temp; while (rightCounter <= leftCounter) { while(rightCounter <= lastIndex && a[rightCounter] <= pivot) { rightCounter++; } while (leftCounter > firstIndex && a[leftCounter] >= pivot) { leftCounter--; } if(rightCounter < leftCounter) { temp = a[rightCounter]; a[rightCounter] = a[leftCounter]; a[leftCounter] = temp; } } temp = a[firstIndex]; a[firstIndex] = a[leftCounter]; a[leftCounter] = temp; return leftCounter; } void quickSort(int * a , int firstIndex , int lastIndex) { if (firstIndex >= lastIndex) return; int partitioningReturn = partitioning(a , firstIndex , lastIndex); quickSort (a , firstIndex , partitioningReturn - 1); quickSort (a , partitioningReturn + 1 , lastIndex); } void mergeTwoArrays(int *a , int firstIndexOfFirstArray , int lastIndexOfFirstArray , int firstIndexOfSecondArray , int lastIndexOfSecondArray) { int *tempArray; tempArray = new int[((lastIndexOfSecondArray - firstIndexOfFirstArray) + 1)]; int firstArrayCounter = firstIndexOfFirstArray; int secondArrayCounter = firstIndexOfSecondArray; int tempArrayCounter = 0; while(firstArrayCounter <= lastIndexOfFirstArray && secondArrayCounter <= lastIndexOfSecondArray) { if (a[firstArrayCounter] < a[secondArrayCounter]) { tempArray[tempArrayCounter] = a[firstArrayCounter]; tempArrayCounter++; firstArrayCounter++; } else { tempArray[tempArrayCounter] = a[secondArrayCounter]; tempArrayCounter++; secondArrayCounter++; } } while (firstArrayCounter <= lastIndexOfFirstArray) { tempArray[tempArrayCounter] = a[firstArrayCounter]; firstArrayCounter++; tempArrayCounter++; } while (secondArrayCounter <= lastIndexOfSecondArray) { tempArray[tempArrayCounter] = a[secondArrayCounter]; secondArrayCounter++; tempArrayCounter++; } for (int i = 0 ; i < ((lastIndexOfSecondArray - firstIndexOfFirstArray) + 1) ; i++) { a[i + firstIndexOfFirstArray] = tempArray[i]; } delete[] tempArray; } void mergeSort(int * a , int firstIndex , int lastIndex) { if (firstIndex >= lastIndex) return; int midIndex = ((firstIndex + lastIndex) / 2); mergeSort(a , firstIndex , midIndex); mergeSort(a , midIndex + 1 , lastIndex); mergeTwoArrays(a , firstIndex , midIndex , midIndex + 1 , lastIndex); } void simpleSelectionSortAlgorithm(int *a , int n) { int temp; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } } } void selectionSortAlgorithm(int *a , int n) { int temp , minValueIndex; for(int i = 0 ; i < n - 1 ; i++) { minValueIndex = i; for(int j = i + 1 ; j < n ; j++) { if(a[minValueIndex] > a[j]) { minValueIndex = j; } } if(minValueIndex != i) { temp = a[i]; a[i] = a[minValueIndex]; a[minValueIndex] = temp; } } } void simpleBubbleSortAlgorithm(int *a , int n) { int temp; for (int i = 0 ; i < n - 1 ; i++) { for(int j = 0 ; j < n - i - 1 ; j++) { if(a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } void bubbleSortAlgorithm(int *a , int n) { int temp; bool isSwapped; for (int i = 0 ; i < n - 1 ; i++) { isSwapped = false; for(int j = 0 ; j < n - i - 1 ; j++) { if(a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; isSwapped = true; } } if(isSwapped == false) { break; } } } void insertionSortAlgorithm(int *a , int n) { int temp , j; for (int i = 1 ; i < n ; i++) { temp = a[i]; j = i - 1; while(j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j+1] = temp; } } int main() { int arr[5]; generateRandomArray(arr , 5); printArray(arr , 5); mergeSort(arr , 0 , 4); printArray(arr , 5); return 0; }
Leave a Comment