Sorting Algorithms

 avatar
itsLu
c_cpp
2 months ago
3.6 kB
8
Indexable
Never
#include <iostream>
using namespace std;

void Selection_Sort (int arr[], int arraySize)
{
    int minIndex, temp, p, c;
    for (p = 0 ; p < arraySize - 1 ; p++)
    {
        minIndex = p;
        for (c = p + 1 ; c < arraySize ; c++)
        {
            if (arr[c] < arr[minIndex])
            {
                minIndex = c;
            }
        }
        temp = arr[p];
        arr[p] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

void Bubble_Sort (int arr[], int arraySize)
{
    int p, c, temp;
    bool isSwapped;
    for (p = 0 ; p < arraySize - 1 ; p++)
    {
        isSwapped = false;
        for (c = 0 ; c < arraySize - p - 1 ; c++)
        {
            if (arr[c] > arr[c+1])
            {
                temp = arr[c];
                arr[c] = arr[c+1];
                arr[c+1] = temp;
                isSwapped = true;
            }
        }
        if (isSwapped == false)
            break;
    }
}

void Insertion_Sort (int arr[], int arraySize)
{
    int p, c, key;
    for (p = 1 ; p < arraySize ; p++)
    {
        key = arr[p];
        c = p - 1;
        while (c >= 0 && arr[c] > key)
        {
            arr[c+1] = arr[c];
            c--;
        }
        arr[c+1] = key;
    }
}

void Quick_Sort (int arr[], int first, int last)
{
    if (last > first)
    {
       int pivot = arr[first], leftCounter = first + 1, rightCounter = last, temp;
        while (leftCounter <= rightCounter)
        {
            while (leftCounter <= pivot && leftCounter <= last)
                leftCounter++;
            while (rightCounter >= pivot && rightCounter > first)
                rightCounter--;
            if (leftCounter < rightCounter)
            {
                temp = arr[rightCounter];
                arr[rightCounter] = arr[leftCounter];
                arr[leftCounter] = temp;
            }
        }
        temp = arr[first];
        arr[first] = arr[rightCounter];
        arr[rightCounter] = temp;
        Quick_Sort(arr, first, rightCounter - 1);
        Quick_Sort(arr, rightCounter + 1, last);
    }
}

void Merge2Arrays(int arr[], int first1, int last1, int first2, int last2)
{
    int *tempArray = new int [((last2 - first1) + 1)];
    int firstCounter = first1, secondCounter = first2;
    int tempCounter = 0;
    while (firstCounter <= last1 && secondCounter <= last2)
    {
        if (arr[firstCounter] < arr[secondCounter])
        {
            tempArray[tempCounter] = arr[firstCounter];
            firstCounter++;
            tempCounter++;
        }
        else
        {
            tempArray[tempCounter] = arr[secondCounter];
            secondCounter++;
            tempCounter++;
        }
    }
    while (firstCounter <= last1)
    {
        tempArray[tempCounter] = arr[firstCounter];
        tempCounter++;
        firstCounter++;
    }
    while (secondCounter <= last2)
    {
        tempArray[tempCounter] = arr[secondCounter];
        tempCounter++;
        secondCounter++;
    }
    for (int k = 0 ; k < (last2 - first1 + 1) ; k++)
        arr[first1+k] = tempArray[k];
    delete [] tempArray;
}

void Merge_Sort (int arr[], int first, int last)
{
    if (first < last)
    {
        int mid = ((first + last)/2);
        Merge_Sort(arr, first, mid);
        Merge_Sort(arr, mid + 1, last);
        Merge2Arrays(arr, first, mid, mid + 1, last);
    }

}

int main()
{
    int arr[5] = {5, 4, 3, 2 , 1};
    Merge_Sort(arr, 0, 4);
    for (int k = 0 ; k < 5 ; k++)
        cout << arr[k] << "\t";
}
Leave a Comment