Question

C++. Difficulty with quickSort function.

Code will not run quickSort function. The code I'm having trouble with is in bold.

-------------------------------------------------------------------------------------------------driverProgram.cpp

#include

#include

#include

#include

#include "quickSort.cpp"

using namespace std;

int main()

{

const int MIN_SIZE = 4;

//Array size

const int SIZE = 25;

int theArray[SIZE] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 12, 13,

14, 15, 16, 17, 18, 19, 18, 19, 20, 21, 22, 23, 24, 25};

cout << "List of 25 items: ";

  

int length = (sizeof(theArray)/sizeof(theArray[0]));

int first = 0;

int last = length - 1;

  

//Display array of unsorted items

for(int count = 0; count < length; count++)

  

{

cout << theArray[count] << " ";

}

  

cout << "Sort list of 25 items: " << endl;

  

//Call quickSort() method to sort array

quickSort(theArray, first, last);

cout << "Sorted List: \n" << endl;

for(int count = 0; count < length; count++)

{

cout << theArray[count] << " " << "\n";

}

  

string stringArray[] = { "g", "r", "e", "w", "a", "r", "d", "s", "d", "f", "v", "r", "z", "w", "b",

"q", "p", "a", "z", "s", "l", "p", "u", "d", "x"};

  

length = (sizeof(stringArray)/sizeof(stringArray[0]));

first = 0;

last = length - 1;

  

// Display unsorted string array

cout << "List of 25 items: " << endl;

for (int count = 0; count < length; count++)

{

cout <

}

  

cout << "Sort list of 25 string items: " << endl;

  

//Call quickSort() to start string array

quickSort(stringArray, first, last);

  

cout << "Sorted List: " << endl;

for(int count = 0; count < length; count++)

{

cout << stringArray[count] << " " << "\n";

}

  

return 0;

  

}

-------------------------------------------------------------------------------------------------quickSort.cpp

#include "insertionSort.cpp"

#include

using namespace std;

template

void quickSort(ItemType theArray[], int first, int last)

{

const int MIN_SIZE = 4;

  

if ((last - first + 1) < MIN_SIZE)

{

cout << "Calling insertionSort with size " << last - first + 1 << endl;

insertionSort(theArray, first, last);

}

else

{

// Create the partition: S1 | Pivot | S2

int pivotIndex = partition(theArray, first, last);

  

int leftSize = pivotIndex - first;

int rightSize = last - pivotIndex;

cout << "Calling quickSort with left size " << leftSize <<

"and right size " << rightSize << endl;

  

// Sort subarrays S1 and S2

quickSort(theArray, first, pivotIndex - 1);

quickSort(theArray, pivotIndex + 1, last);

} // end if

} // end quickSort

template

int partition(ItemType theArray[], int first, int last)

{

//Choose pivot and reposition it

int mid = first + (last - first) / 2;

sortFirstMiddleLast(theArray, first, mid, last);

swap(theArray[mid], theArray[last-1]);

int pivotIndex = last - 1;

ItemType pivot = theArray[pivotIndex];

  

//Determine the regions S1 and S2

int indexFromLeft = first + 1;

int indexFromRight = last - 2;

  

bool done = false;

while(!done)

{

//Locate first entry on left that is >= pivot

while(theArray[indexFromLeft] < pivot)

{

indexFromLeft = indexFromLeft + 1;

}

//Locate first entry on the right that is <= pivot

while(theArray[indexFromRight] > pivot)

{

indexFromRight = indexFromRight - 1;

}

  

if(indexFromLeft < indexFromRight)

{

swap(theArray[indexFromLeft], theArray[indexFromRight]);

indexFromLeft = indexFromLeft + 1;

indexFromRight = indexFromRight - 1;

}

else

{

   done = true;

}

}

//Place pivot in proper position between S1 and S2 and mark its new location

swap(theArray[pivotIndex], theArray[indexFromLeft]);

pivotIndex = indexFromLeft;

  

return pivotIndex;

}

template

void sortFirstMiddleLast(ItemType theArray[], int first, int mid, int last)

{

if (theArray[first] > theArray[mid])

{

swap(theArray[first], theArray[mid]);

}

if (theArray[mid] > theArray[last])

{

swap(theArray[mid], theArray[last]);

}

if (theArray[first] > theArray[mid])

{

swap(theArray[first], theArray[mid]);

}

}

//function to swap array elements

template

void swap(ItemType &x, ItemType &y)

{

ItemType t = x;

x = y;

y = t;

}

-------------------------------------------------------------------------------------------------inserationSort.cpp

template

void insertionSort(ItemType theArray[], int first, int last)

{

// unsorted = first index of the unsorted region,

// loc = index of insertion in the sorted region,

// nextItem = next item in the unsorted region.

// Initially, sorted region is theArray[0],

// unsorted region is theArray[1..n-1].

// In general, sorted region is theArray[0..unsorted-1],

// unsorted region theArray[unsorted..n-1]

for (int unsorted = first + 1; unsorted <= last; unsorted++)

{

// At this point, theArray[first..unsorted-1] is sorted.

// Find the right position (loc) in theArray[first..unsorted]

// for theArray[unsorted], which is the first entry in the

// unsorted region; shift, if necessary, to make room

ItemType nextItem = theArray[unsorted];

int loc = unsorted;

while ((loc > first) && (theArray[loc - 1] > nextItem))

{

// Shift theArray[loc - 1] to the right

theArray[loc] = theArray[loc - 1];

loc--;

} // end while

  

// At this point, theArray[loc] is where nextItem belongs

theArray[loc] = nextItem; // Insert nextItem into sorted region

} // end for

} // end insertionSort

Answer 1

I just want to know that if taking length = sizeof(array)/sizeof(array[0]) is right.
Because I think that array[0] is an integer and hence sizeof(array[0]) will only give the size of an integer so length=sizeof(array)/sizeof(array[0]) wont give the size of the array. And hence the length of the array should be just sizeof(array) and not sizeof(array)/sizeof(array[0]).

Kindly revert back on this, so we can further discuss the answer.