Merge Sort - Detailed Version

 avatar
itsLu
c_cpp
a year ago
2.2 kB
9
Indexable
#include <iostream>
using namespace std;

/*لازم نخلي الكاونترز جلوبال عشان ده ريكرجن لو عرفتهم جوا الفانكشن
  مش هيشتغلوا لأن كل ندهة عالفانكشن هترجع الكاونترز اصفار وده مش عايزينه
  مش هيحصل أي تبديل فا كاونتر التبديل هيفضل صفر لأننا بنعمل أراي مؤقتة فا مش بنبدل حاجة*/
int cCounter = 0, swapCounter = 0;

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++;
            cCounter++;
        }
        else
        {
            tempArray[tempCounter] = arr[secondCounter];
            secondCounter++;
            tempCounter++;
            cCounter++;
        }
    }
    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);
    cout << endl << "Number of Comparisons: " << cCounter << "\tNumber of Swaps: " << swapCounter << endl;
//اللوب الجاية دي عشان تطبع الأراي بعد الترتيب ممكن تكرفله عادي
    for (int k = 0 ; k < 5 ; k++)
        cout << arr[k] << "\t";
}
Editor is loading...
Leave a Comment