Quick Sort split and merge c++

Question

I have an idea to implement quick sorting first by dividing arrays recursively until I get a tree of cells of the array. Then I combine the sorted array into a whole. Can someone help me find an error and tell me why the program is not working properly?

#include <iostream>
#include <ctime>

using namespace std;

void random(int arr[], int N)
{
    for(int i = 0; i < N; i++)
        arr[i] = rand()%10;
}

void print(int arr[], int N)
{
    for(int i = 0; i < N; i++)
        cout << arr[i] << " ";
}

int  quickSort(int arr[], int N)
{
    int pivot = arr[0];
    int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
    for(i = 1; i < N; i++)
    {
        if(arr[i] <= pivot)
        {
            arr1[j++] = arr[i];
            N1 = j;
        }
        else
        {
            arr2[k++] = arr[i];
            N2 = k;
        }
    }
    arr1[N] = quickSort(arr1, N1), arr2[N] = quickSort(arr2, N2);
    for(i = 0; i < N1; i++)
    {
        arr[i] = arr1[i];
    }
    arr[N1] = pivot;
    for(i = N1 + 1; i < N; i++)
    {
        arr[i] = arr2[i];
    }
}

int main()
{
    srand(time(NULL));
    int N;
    cout << "How many elements should be in array?" << endl;
    cin >> N;
    int arr[N];
    random(arr, N);
    print(arr, N);
    cout << endl;
    quickSort(arr, N);
    print(arr, N);

    return 0;
}

0 1 5 2 9 6 ---quickSort---> 0 1 2 5 6 9

Answer 1

The Two problems are:

1: Initialization

int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
                                       ^^^^^^^ Not initialized.

Looking ahead were they are initialized.

        if(arr[i] <= pivot)
        {
            arr1[j++] = arr[i];
            N1 = j;
        }

If no points are smaller or equal to the pivot point then N1 will remain uninitialized. Your subsequent call to

arr1[N] = quickSort(arr1, N1)

Here, you are passing an un-initialized value as a parameter. This will result in Unspecified Behavior not as bad as Undefined Behavior but still not good. In reality, you are passing a random number that is the value that was in that memory location. As you are using it as the size of a zero sized array anything other than 0 is an going to result in a program error, anything greater than N will result in Undefined Behavior in the next level down.

---

2: Recursion with no exit.

Next this is a recursive function.

There is currently no exit criteria, so this will recurse forever (or until you reach hardware limits and the OS kills the application (it crashes)).

At the top of your quickSort() you should add an exit test. If the list has zero length, then there is no need to sort. If the length is 1 then it is already sorted so no need to do extra work.

So any input that has a value of N less than 2 simply exit.

int  quickSort(int arr[], int N)
{
    if (N < 2) {
        return;
    }

---

My main advice here is that both these problems were spotted by the compiler.

• If you are using g++/clang then increase the warning levels -Wall -Wextra -Werror
• If you are using dev studio

Other issues that should be fixed.

Technically, this is not valid C++

arr1[N]

A lot of compilers allow it as an extension (but I am betting its not universal). Best not to rely on features that are not standard. If you are experimenting and have not learned about std::vector then fine. Please use them while you learn. But once you have learned about std::vector prefer this

---

The function quickSort() does not return a value. So change its return type to void. Then change the recursive calls so it does not assign the return value to arr

void quickSort(int arr[], int N)

/// .....
quickSort(arr1, N1);
quickSort(arr2, N2);

---

Other things you should address.

OK. rand() is fine for dirty hacks. But you should start using the proper C++ random number generator. Make that your habit.

Here is an example.

---

Stop using

using namespace std;

Rad all about it: Question The best answer (IMO)

---

Please put braces around block statements (even if they are a single line). This will save you hours of debugging one day.

    for(int i = 0; i < N; i++) {   // Add this brace
        arr[i] = rand()%10;
    } // This brace

One day you will be trying to do something add another line to that loop and accidentally forget to add the now required braces around the code and it will not work and in your code blindness will not spot it until you ask the intern to look at the code and they will spot it in 30 seconds.

---

This style of passing an array and length is very C like.

void print(int arr[], int N)

Sure it works. But it does not match the style of most C++ functions (especially the ones that come from the standard library). Usually you pass a begin and end pointer (more commonly referred to as iterators in C++).

 void print(int* begin, int* end) {
 {
     for(int* loop = begin; loop != end; ++loop) { 
         std::cout << *loop << " ";
     }
 }

Now you can call like this:

 print(arr, arr + N);

---

This is lazy:

int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;

Its also hard to read for other engineers. Be nice to your fellow engineers, one declaration per line please. Personally (but others have other opinions) stop using i/j/k as loop variables. This is a holdover from Fortran. Variable naming is a skill, develop it.

Other Ways to improve your C++ skill

Get some code reviews.

There is a stack exchange site to handle C++ code reviews that will help you write better idiomatic C++ code. PLEASE NOTE they only review working code (this is not a site to fix bugs).

QuickSort is a common request for review (especially in C++). So you can look at what others have done, where they went wrong, and better ways to handle the situation.

Search Quick Sort On CodeReview