CODEWITHSUNDEEP
c++arrayssortingbooleanquicksort
levi
levi

Reputation: 3

Quicksorting Boolean Array in C++

Good day! We were asked to sort a Boolean array but the thing is when I run my program, it always stops working. I tried printing the values inside the Boolean array and they are printed but when I try to inject the quick sort function, the unsorted values don't print anymore nor the array is sorted. This code sorted different data types except for Boolean. I hope you can help me find the problem. Thank you.

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

void sortArray(bool* arr, int start, int end)
{
   int pivot = arr[start];
   int p;

   if(end > start)
   {
     p = partition(arr, pivot, start, end);
     arr[p] = pivot;
     sortArray(arr, start, p);
     sortArray(arr, p+1, end);
   }

}

int partition(bool* arr, int pivot, int start, int end)
{
  int header = start;
  int p = end;

  while(header < p)        
  {
    while( pivot < arr[p] && p > header)   
    {
        p=p-1;            
    }
    swap(arr[header], arr[p]);


    while( pivot >= arr[header] && header < p)    
    {
       header++;            
    }
    swap(arr[p], arr[header]);

   }
   return header;
}

Upvotes: 0

Views: 823

Answers (2)

CiaPan
CiaPan

Reputation: 9570

This code sorted different data types except for Boolean – I doubt it. Have you tried to sort array of int, say int arr[4] = {4, 4, 4, 4}...?

Your code has a flaw in handling partitions: when the N-items subarray to be partitioned consists of equal items, the second internal loop in partition() terminates with header==p and you get partitions of N and ZERO items. That causes an infinite recursion and leads to a crash due to the stack overflow.

You need to skip sorting the pivot item—after partitioning it is in its final position and doesn't need to be touched anymore:

 p = partition(arr, pivot, start, end);
 arr[p] = pivot;               // this item done
 sortArray(arr, start, p-1);   // skip it in recursion  <<<<<<<<
 sortArray(arr, p+1, end);

Upvotes: 0

GreenScape
GreenScape

Reputation: 7737

Boolean type has an advantage here. You can simply count number of trues.

In which case sort function should look like:

void sortArray(bool* arr, int start, int end)
{
    int true_count = 0;
    for (int i = start; i != end; ++i) {
        if (arr[i]) {
            ++true_count;
        }
    }

    int true_range_end = start + true_count;

    // Here go true
    for (int i = start; i != true_range_end; ++i) {
        arr[i] = true;
    }

    // Here go false
    for (int i = true_range_end; i != end; ++i) {
        arr[i] = false;
    }
}

Note that this is a descending order (true goes first).

Upvotes: 5

Related Questions