Question

I need help with this code:

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

void dump(int ar[], int size)
{
cout << "\nDUMP [ ";
for (int i=0; i<=size; i++)

{
cout << ar[i] << " ";

}
cout << "]\n\n";
}
void quicksort(int ar[], int start, int end)
{
cout << "TOP OF SORT ===========================" << endl;
dump(ar, start, end);
int pivot = ar[end];
int left = start;
int right = end - 1;
int tmp;
cout << "Pivot = " << pivot << endl;
while(left < right)
{
cout << "looping from left (starting at " << left << ") and from right (starting at index " << right << ")\n";
while(ar[left] <= pivot && left < end) left++;
while(ar[right] > pivot && right > start) right--;
cout << "looping done. left is now " << left << ", right is now " << right << endl;
if(left >= right) break;
cout << "swapping the " << ar[left] << " (at index " << left << ") and the "
<< ar[right] << " (at index " << right << ")." << endl;
tmp = ar[left];
ar[left] = ar[right];
ar[right] = tmp;
left++;
right--;
dump(ar, start, end);
}
cout << "AFTER loop (left and right have crossed!) left = " << left << " right = " << right << endl;
if(ar[left] > pivot)
{
cout << "swapping the " << ar[left] << " (at index " << left << ") and the pivot "
<< ar[end] << " (at index " << end << ")." << endl; cout << "(note that the pivot is now in its correct position)\n";

tmp = ar[left];
ar[left] = pivot;
ar[end] = tmp;
}
dump(ar, start, end);

if(left - 1 - start > 0)
{
cout << "calling sort with LESS THAN list:" << endl;
quicksort(ar, start, left - 1);
}
if(end - 1 - left > 0)
{
cout << "calling quicksort with GREATER THAN list:" << endl;
quicksort(ar, left + 1, end);
}
}
void sort(int list[], int length)
{
quicksort(list, 0, length - 1);
}
int main(void)
{
int ar[100];

int i, v, len;

for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;

if (v < 0) break;

ar[i] = v;
}

len = i;

cout << "main: before sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}

sort(ar, len);

cout << "main: after sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}
}
This is what it should be the output:

SAMPLE OUTPUTE-- $ lab9 enter a number(-1 to quit) 5 enter a number(-1 to quit) 2 enter a number(-1 to quit) 6 enter a number(-1 to quit) 3 enter a number(-1 to quit) 4 enter a number(-1 to quit): -1 main: before sort: main: ar[0]=5 main: ar[1]2 main : ar[2]=6 main: ar[3]3 main: ar[4] 4 TOP OF SORT seEEssEssEsEEEEEsEEsEEssEssEssEssE- DUMP [ 5 263 4] pivot 4 looping from left (starting at index e) and from right (starting at index 3) looping done left is now e, right is now 3 swapping the 5 (at index e) and the 3 (at index 3) DUMP 3 26 5 4 ] looping from left (starting at index 1) and from right (starting at index 2) looping done. left is now 2, right is now 1 AFTER loop (left and right have crossed!) left - 2 right - 1 swapping the 6 (at index 2) and the pivot 4 (at index 4) (note that the pivot is now in its correct position) DUMP [ 3 2 4 5 6 ] calling sort with LESS THAN list: TOP OF SORT sessEssEssEsEEEEEssssEssesssssEssE- DUMP 3 2 1 pivot- 2 AFTER loop (left and right have crossed!) left-e right - e

Answer 1

Please find the code below:

I have updated the dump method in existing code to get the output as required.

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

/*
void dump(int ar[], int size){
cout << "\nDUMP [ ";
for (int i=0; i<=size; i++){
cout << ar[i] << " ";
}
cout << "]\n\n";
}
*/
void dump(int ar[], int start,int end){
cout << "\nDUMP [ ";
for (int i=start; i<=end; i++){
cout << ar[i] << " ";
}
cout << "]\n\n";
}

void quicksort(int ar[], int start, int end){
cout << "TOP OF SORT ===========================" << endl;
dump(ar, start, end);
int pivot = ar[end];
int left = start;
int right = end - 1;
int tmp;
cout << "Pivot = " << pivot << endl;
while(left < right){
cout << "looping from left (starting at " << left << ") and from right (starting at index " << right << ")\n";
while(ar[left] <= pivot && left < end) left++;
while(ar[right] > pivot && right > start) right--;
cout << "looping done. left is now " << left << ", right is now " << right << endl;
if(left >= right) break;
cout << "swapping the " << ar[left] << " (at index " << left << ") and the " << ar[right] << " (at index " << right << ")." << endl;
tmp = ar[left];
ar[left] = ar[right];
ar[right] = tmp;
left++;
right--;
dump(ar, start, end);
}
cout << "AFTER loop (left and right have crossed!) left = " << left << " right = " << right << endl;
if(ar[left] > pivot){
cout << "swapping the " << ar[left] << " (at index " << left << ") and the pivot " << ar[end] << " (at index " << end << ")." << endl; cout << "(note that the pivot is now in its correct position)\n";

tmp = ar[left];
ar[left] = pivot;
ar[end] = tmp;
}
dump(ar,start,end);

if(left - 1 - start > 0){
cout << "calling sort with LESS THAN list:" << endl;
quicksort(ar, start, left - 1);
}
if(end - 1 - left > 0){
cout << "calling quicksort with GREATER THAN list:" << endl;
quicksort(ar, left + 1, end);
}
}
void sort(int list[], int length){
quicksort(list, 0, length - 1);
}
int main(void){
int ar[100];
int i, v, len;
for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;
if (v < 0) break;
ar[i] = v;
}
len = i;
cout << "main: before sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}

sort(ar, len);

cout << "main: after sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}
}

Output:

enter a number(-1 to quit): 5 enter a number(-1 to quit): 2 enter a number(-1 to quit) 6 enter a number(-1 to quit) 3 enter a number(-1 to quit): 4 enter a number(-1 to quit): -1 main: before sort: main: arle] 5 main: ar[11 2 main: ar[21 6 main: ar[31 3 main: ar[4] 4 TOP OF SORT 55 2 55255 255 25522 DUMP[ 5 26 34 Piyot4 looping from left (starting at e) and from right (starting at index 3) looping done. left is now e, right is now 3 swapping the 5 (at index e) and the 3 (at index 3) DUMP 3 2654 looping from left (starting at 1) and from right (starting at index 2) looping done. left is now 2, right is now 1 AFTER loop (left and right have crossed) left2 right 1 swapping the 6 (at index 2) and the pivot 4 (at index 4) (note that the pivot is now in its correct position) DUMP 3 2 4 56 calling sort with LESS THAN list: TOP OF SORT 55 2 55255 255 25522 DUMP 3 2 Piyot2 AFTER loop (left and right have crossed!) left right swapping the 3 (at index e) and the pivot 2 (at index 1) (note that the pivot is now in its correct position)

DUMP [ 2 3 calling quicksort with GREATER THAN list TOP OF SORT 5 5555255552 5555 DUMP5 6 Pivot 6 AFTER loop (left and right have crossed!) left - 3 right - 3 DUMP 5 6 main: after sort main: ar[e] = 2 main : ar[1] = 3 main: ar[2] 4 main: ar[3] 5 main: arl46