Sorting algorithms

 avatar
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