Sorting algorithms
Sameh
c_cpp
2 years ago
5.4 kB
11
Indexable
#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;
}Editor is loading...
Leave a Comment