Member Avatar for yuugib

Hi, I was wondering if you can help me figure how to go about this problem.

This is what I have to do:

Write a programme to generate an array of 100 random integers.

While the array is being filled incrementally, produce a sorted array by comparing the new element n+1 to a sorted array of n elements and inserting the new element into the appropriate position (this mean shifting all larger elements into one position up in the array).
This process will ultimately produce a sorted list of the 100 random numbers.


This is what I have so far.. I understood that there needs to be a function, that sorts out the array, while its being filled and produces new array.
I tried to use bubble sort in the function, but it doesnt appear to sort the array.
Can somebody please advice how can I fix this or is there a better way to go at it?

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;


int arraysort(int array[], int num, int size);


int main()
{
    int array[100], i, size = 0;

    srand(time(NULL));
    for(i=0; i<100; i++){
        array[i] = rand();

        size++;

        array[i] = arraysort(array, array[i], size);
        }

    for (int i=0; i<100; i++) cout << array[i] << " ";

    return 0;
}

int arraysort(int array[], int num, int size){

    int a, b, t;
    if (a == 0) return num;

    for (a=1; a<size; a++)
        for (b=size-1; b>=a; b--) {
            if(array[b-1] > array[b]) {
                t=array[b-1];
                array[b-1] = array[b];
                array[b] = t;
            }
        }

    for (t=0; t<size; t++)
    return array[t];
}
  • 2 Contributors
  • 2 Replies
  • 238 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by yuugib

Dani AI

Generated

As pointed out, insertion sort is the right fit for “build-as-you-go” sorting. The original code has a few concrete bugs that prevent correct behavior: an uninitialized variable (a) used in if (a == 0), an immediate return inside a loop so the function exits after the first iteration, and a mismatch between what the function does and how it’s used (you're assigning the function result back to array[i] when the sort should be done in-place). Bubble sort also adds unnecessary complexity for this assignment.

A clean pattern is: place the new random value at the end of the used portion of the array, then shift larger elements one position up until you find the insertion spot, and put the new value there. That single small routine implements the incremental insertion step required by the assignment.

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void insertIntoSorted(int arr[], int size) {
    int key = arr[size-1];
    int j = size - 2;
    while (j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        --j;
    }
    arr[j+1] = key;
}

int main() {
    int array[100];
    srand(static_cast<unsigned>(time(NULL)));
    int size = 0;

    for (int i = 0; i < 100; ++i) {
        array[size++] = rand();
        insertIntoSorted(array, size);
    }

    for (int i = 0; i < 100; ++i) cout << array[i] << " ";
    return 0;
}

Notes: for better randomness use <random> (std::mt19937 + uniform distribution) and remember insertion sort is O(n^2) but perfectly fine for 100 items. Check off-by-one boundaries carefully and avoid returning from inside loops unless intended. Congrats to for getting it working after switching to insertion sort.

Recommended Answers

All 2 Replies

Member Avatar for Fbody

You're definitely on the right track, but because you have to do it while entering/generating the values, you actually have to use a variation on the "insertion sort" algorithm. A bubble sort could work, but it's extremely inefficient and doesn't meet the specifications/parameters of the assignment.

Here is some information on insertion sort.

Initially, you'll want to store the random value to a temp value not as a member of the array. Then send the temp value to the function. Inside the function, you'll find where the value belongs then "slide" the values/elements above it. Once the "slide" is complete, you then assign it to the appropriate array element.

Edited by Fbody because: n/a
commented: Managed to fix my problem thanks to this post +1
Member Avatar for yuugib

Thank you so much! Insertion sort worked for me.
You were very helpful.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.