Can someone help me fix and edit my C++ coding?

+3 votes
asked Nov 19 by Hymns Appraisal (150 points)
I need someone to go over with me on my coding format on C++. I need to tweak it a bit to make it work.but i dont know what im doing wrong. Its an assignment that i have to turn in. I dont know where to go to get it double check. I did get most of the basic coding done and its all about the basic sorting functions in an array. But my problem lies in the structure. Its all cluttered. Im just not sure how to organize it.

This Function is suppose to be able to basic sorting in a array which should allow me to input any size of an array as well as sorting, shuffling, reverse order, and shuffle it by 10%. The requirements are It should contain a class Array that has such Functions as Time measurement functions, Generate of the simulation (main function), Creation of a sorted array, Creation of a completely shuffled array, Creation of a shuffled array at 10%, Insertion sort, Selection sort, Bubble sort, Partition function (for Quick sort), Quick sort, Merge sorted array (for Merge sort), Merge sort. Hopefully my coding i did has everything, but piece it together it a bit hard.

#include <iostream>
#include <algorithm>
#include <chrono>
#include <iostream>
#include<vector>

using namespace std;  
using namespace std::chrono;

void shuffle_array(int a[], int size)
{
    unsigned seed = 0;
    shuffle(a, a + size, default_random_engine(seed));
}

void insertion_sort(int a[],int n)
{
        int i,j,temp;
        
        for(i=1;i<n;i++)
        {
                temp = a[i];
                j = i-1;
                
                while(j>=0&&temp<a[j])            
                {
                        swap(a[j],a[j+1]);
                        j--;
                }
        }
        cout<<endl<<"Sorted array:- ";
        for(i=0;i<n;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
}

void Selection_Sort(int a[],int size)
{
        int min,temp;
        cout<<"Unsorted array is:- ";
        for(int i = 0;i<size;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
        for(int i=0;i<size-1;i++)
        {
                min = i;
                for(int j = i+1;j<size;j++)
                {
                        if(a[min]>a[j])
                                min = j;
                }
                swap(a[i],a[min]);
        
        
        }
        
        cout<<endl<<endl<<"Sorted array is:- ";
        
        for(int i = 0;i<size;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
}

void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
}

void bubble_sort(int a[],int size)
{
        
        int temp;
        for(int i =0;i<size;i++)
        {
                for(int j=0;j<size-i-1;j++)  
                {
                        if(a[j]>a[j+1])
                        {       
                                swap(a[j],a[j+1]);                              
                        }
                }
        }
        cout<<endl<<"Sorted Array:- ";
        for(int i=0;i<size;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
}

int partition(int input[],int si,int ei){
    
        int pivot = input[ei];
    int partIdx = si;
    
    for(int i=si;i<ei;i++){
        if(input[i] <= pivot){
            swap(input[i],input[partIdx]);
            partIdx++;
        }
    }
    
    swap(input[ei],input[partIdx]);
    return partIdx;
    
}

void _quickSort(int input[],int si,int ei){
    
        if(si < ei){
    int partIdx = partition(input,si,ei);
    _quickSort(input,si,partIdx-1);
    _quickSort(input,partIdx,ei);
    }
}

void merge(int input[],int si,int ei,int mid){
    
    int aux[ei - si + 1];
    int i = si;
    int j = mid+1;
    int temp = 0;
    while(i<=mid && j <= ei){
        
        if(input[i] <= input[j]){
            aux[temp++] = input[i++];
        }else{
            aux[temp++] = input[j++];
        }
        
    }
    
    while(i<=mid){
        aux[temp++] = input[i++];
    }
    
    while(j<=ei){
        aux[temp++] = input[j++];
    }
    
    
    temp = 0;
    
    for(i=si;i<=ei;i++){
        input[i] = aux[temp++];
    }
    
    
}

int main()
{
        int a[INT_MAX],size;
        cout<<"Enter the array size:- ";
        cin>>size;
        
        cout<<"Enter the array:- ";
        for(int i=0;i<size;i++)
        {
                cin>>a[i];
        }
        cout<<endl<<"Unsorted array:- ";
        for(int i=0;i<size;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
        
        insertion_sort(a,size);
        
        Selection_Sort(a,size);
        
        bubble_sort(a,size);
        
        quickSort(a,0,size-1);
        cout<<endl<<"Sorted array:- ";
        for(i=0;i<n;i++)
        {
                cout<<"\t"<<a[i]<<" ";
        }
        
        merge(a,size,0,0);
        cout<<endl<<"Sorted array:- ";
        for(i=0;i<n;i++)
        {
                cout<<"\t"<<a[i]<<" ";
                
        }
        
      
        
        shuffle_array(a, size);  
        cout << "The completely suffled array: \n";
        printArray(a,size);
    
    
         shuffle_array(a, size*0.1);  
        cout << "The 10'%' suffled array: \n";
        printArray(a,size);
        
        

        auto start = high_resolution_clock::now();

 
        sort(a, a+size);

        auto stop = high_resolution_clock::now();

        auto duration = duration_cast<microseconds>(stop - start);
    

        cout << "Time taken by function: "
                << duration.count() << " microseconds" << endl;

        return 0;
}

2 Answers

0 votes
answered 6 days ago by Peter Minarik (12,220 points)
edited 2 days ago by Peter Minarik

Some general advices

Do not copy-pate code around.

You keep repeating the part of code that prints the sorted array. Put it in a function and call it whenever needed. ;)

Measuring execution time

Probably the point of measuring time is to compare the execution time of the various sorting algorithms. So you'd need a nicely constructed.

Please, have a look at this forum thread, specifically the function called funcTime. (I don't like the name, but the functionality it provides is what you'd need. You can rename it to anything, e.g.: MeasureExecution or you can come up with a better name.)

Sorting the array

I've noticed that after your first sorting, you'll sort again, but this time you're sorting the already sorted array. Easy task. :D

What I'd do instead is a function, that duplicates the array you want to sort, so you can test all the various sorting methods with the same input.

This can be done simply by defining another array with the same size as your original array and use the copy in the sorting algorithms and reset the copy from the original array before every sorting test. Below is a small example of how to duplicate an array. It's really just a single line calling memcpy.

#include <iostream>
#include <cstring>

int main()
{
    int originalArray[] = { 1, 2, 3 };
    int arrayToBeTested[3];
    
    std::memcpy(arrayToBeTested, originalArray, sizeof(originalArray)); // Duplicating the array
    
    for (int i = 0; i < 3; i++)
    {
        std::cout << arrayToBeTested[i] << std::endl;
    }

    return 0;
}

Insertion sort

I think you misunderstood insertion sort. The insertion starts from an empty array and adds elements one by one. So what I'd have a function that inserts a single element into an array and would call this method with each element of your unsorted array. You do not seem to follow the same logic in your code.

Selection sort

I found it works fine. Well done on this one!

Bubble sort

Well done, it works fine too! However, there is a more optimised version for this specific sorting algorithm.

Quick sort and partitioning

Well done, this works fine too! However, you're doing unnecessary steps in the partitioning when you check

if (input[i] <= pivot)

Checking for less is fine enough. With equal, you'll swap the pivot with another time of the same value, which doesn't really make much sense for me.

One more thing: there is a more efficient partitioning algorithm (Hoare partition scheme). I'll include it later below.

Merge sort

Your merge sort implementation doesn't seem to work for me. I'd suggest reading on the merge sort here.

My attempt for the solution

I'll post it in another "answer" as this one is reaching it's maximum character limit.
0 votes
answered 2 days ago by Peter Minarik (12,220 points)

I rewrote (part of) your solution and I came up with the below code.

The TestRun() method receives an array and size and runs all the various sorting algorithms on the input and measures the time. It shows interesting results for the various inputs (already sorted, reverse sorted, multiple elements, randomly shuffled).

I'd suggest modifying my code and changing it in a way that you would measure execution in a more precise way. The problem with my implementation is that it measures the execution of a function only once. So any interference from the operating system or other running programs affect the results so comparison to other results is not really accurate.

You could achieve better results if you run it multiple times (e.g. 100) and measure the minimum, maximum and average execution time for each sorting function.

Also, in my code the sorting function contains the printing part as well. You can refactor the code for that not to be included. Or not, as if every function does the same printing, then the comparison should be not depend on this extra time.

Have fun! :)

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

#include <cstring>

void Print(const std::string & message, int a[], int size, bool addNewLine = false)
{
    std::cout << message << ' ';
    for (int i = 0; i < size; i++)
    {
        if (i > 0)
            std::cout << ", ";
            
        std::cout << a[i];
    }
    if (addNewLine)
        std::cout << std::endl;
}

void Shuffle(int a[], int size)
{
    unsigned seed = 0u; // Fixed seed, random generates the same results every time
    // time based seed: unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::shuffle(a, a + size, std::default_random_engine(seed));
}

void Swap(int & a, int & b)
{
    int temp = a;
    a = b;
    b = temp;
}

// NOTE: cannot pass argument as int[]. Variable sized arrays are not supported for template arguments. Hence an (int*) cast is needed.
template<typename F, typename ... Args> void RunSort(F func, Args && ... args)
{
    std::chrono::high_resolution_clock::time_point startTime = std::chrono::high_resolution_clock::now();
    func(std::forward<Args>(args) ...);
    double duration = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - startTime).count();
    
    std::cout << " [" << duration << " ns]" << std::endl;
}

// array, left, right
int Partition(int a[], int l, int r)
{
    int pivot = a[(l + r) / 2];
    int i = l - 1;
    int j = r + 1;

    while (true)
    {
        while (a[++i] < pivot) /* nothing to do */;
        while (a[--j] > pivot) /* nothing to do */;
        if (i >= j)
            return j;

        Swap(a[i], a[j]);
    }
}

// Insert `data` into array `a` which has a size `size`
// a: the array to be inserted into
// size: the number of elements already in the array (not the total capacity)
// data: the data to be inserted
void InsertInto(int a[], int size, int data)
{
    int insertAt = size;
    for (int i = 0; i < size; i++)
    {
        if (a[i] >= data)
        {
            std::memmove(&a[i + 1], &a[i], sizeof(int) * (size - i));
            insertAt = i;
            break;
        }
    }
    
    a[insertAt] = data;
}

void InsertionSort(int originalArray[], int size)
{
    int result[size];
    for (int i = 0; i < size; i++)
        InsertInto(result, i, originalArray[i]);
    
    Print("Insertion-sorted array:", result, size);
}

void SelectionSort(int a[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (a[min] > a[j])
                min = j;
        }
        Swap(a[i], a[min]);
    }
    
    Print("Selection-sorted array:", a, size);
}

void BubbleSort(int a[], int size)
{
    int length = size;
    while (length >= 1)
    {
        int newLength = 0; // newLength shows the last position where a swap happened. Anything beyond this is already sorted.
        for (int i = 1; i < length; i++)
        {
            if (a[i - 1] > a[i])
            {
                Swap(a[i - 1], a[i]);
                newLength = i;
            }
        }
        length = newLength;
    }

    Print("Bubble-sorted array:   ", a, size);
}

// array, left, right: array[l, r]; (left and right are inclusive)
void QuickSort(int a[], int l, int r)
{
    if (l < r)
    {
        int p = Partition(a, l, r);
        QuickSort(a, l, p);
        QuickSort(a, p + 1, r);
    }
}

void QuickSortWrapper(int a[], int size)
{
    QuickSort(a, 0, size - 1);
    Print("Quick-sorted array:    ", a, size);
}

// Sources: src[l, m[; src[m, r[
// Result: dst[l, r[
void TopDownMerge(int src[], int l, int m, int r, int dst[])
{
    int i = l;
    int j = m;
 
    // While there are elements in the left or right runs...
    for (int k = l; k < r; k++)
    {
        // If left run head exists and is <= existing right run head.
        if (i < m && (j >= r || src[i] <= src[j]))
        {
            dst[k] = src[i++];
        }
        else
        {
            dst[k] = src[j++];
        }
    }
}

// Sort a merge run from src to dst
// src[l, r[; (left inclusive, right exclusive)
void TopDownSplitMerge(int src[], int l, int r, int dst[])
{
    if (r - l <= 1)
        return;

    int m = (l + r) / 2; // middle

    // Split the run longer than 1 item into halves: [l, m[; [m, r[
    // Sort both runs recursively from dest to src (their roles swap)
    TopDownSplitMerge(dst, l, m, src);  // sort the left run
    TopDownSplitMerge(dst, m, r, src);  // sort the right run

    TopDownMerge(src, l, m, r, dst);
}

void TopDownMergeSort(int a[], int size)
{
    int temp[size];
    std::memcpy(temp, a, sizeof(int) * size); // Copy a to tmp
    TopDownSplitMerge(temp, 0, size, a);
    Print("Merge-sorted array:    ", a, size);
}

void TestRun(int array[], int size)
{
    Print("Array to be sorted:    ", array, size, true);

    int a[size];
    std::memcpy(a, array, sizeof(int) * size);
    RunSort(InsertionSort, (int*)a, size);
    
    std::memcpy(a, array, sizeof(int) * size);
    RunSort(SelectionSort, (int*)a, size);

    std::memcpy(a, array, sizeof(int) * size);
    RunSort(BubbleSort, (int*)a, size);
    
    std::memcpy(a, array, sizeof(int) * size);
    RunSort(QuickSortWrapper, (int*)a, size);
    
    std::memcpy(a, array, sizeof(int) * size);
    RunSort(TopDownMergeSort, (int*)a, size);
}

int main()
{
    const int size = 10;
    int array1[size] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // already sorted
    TestRun(array1, size);
    std::cout << std::endl;

    int array2[size] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // reverse sorted
    TestRun(array2, size);
    std::cout << std::endl;

    int array3[size] = { 1, 1, 1, 2, 1, 1, 1, 2, 2, 1 }; // repeated elements
    TestRun(array3, size);
    std::cout << std::endl;

    Shuffle(array1, size);  // Shuffled array
    TestRun(array1, size);
    std::cout << std::endl;
}
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...