Hello I\'ve got a homework which im supposed to Quick sort an array of numbers.
ID: 3606971 • Letter: H
Question
Hello I've got a homework which im supposed to Quick sort an array of numbers. I've written almost all of the code but I need help with one problem. I dont know what to write on the Swapping piece of the code. This is what it says about the swap function: Swap function swaps two elements. The parameters must be passed by reference.
This is what I've gotten so far:
#include "stdafx.h"
#include
#include
#define ARRAY_SIZE 20 // Size of array
#define UPPER_LIMIT 20 // Max number of arrays used
#define LOWER_LIMIT 12 // Min number of arrays used
#define DATA_UPPER_LIMIT 80 // Max of each array element
#define DATA_LOWER_LIMIT 10 // Min of each array element
void RandomizeAndPrint(int[], int);
void FindMaxMin(int[], int);
void QuickSort(int[], int, int);
int Partition(int[], int, int);
void Swap(int ", int ");
void BinSearch(int[], int, int, int);
////////////////////////// void main ////////////////////////////////////////////
int main(void)
{
int samples[ARRAY_SIZE];
int sampleSize;
int searchItem;
srand(time(NULL));
sampleSize = rand() % (UPPER_LIMIT - LOWER_LIMIT + 1) + LOWER_LIMIT;
RandomizeAndPrint(samples, sampleSize);
FindMaxMin(samples, sampleSize);
QuickSort(samples, 0, sampleSize - 1);
Printf("sorted: ");
for (int i = 0; i < sampleSize; i++)
printf("%d ", samples[i]);
printf(" ");
// Get a random number as search example & print it
searchItem = rand() % (DATA_UPPER_LIMIT - DATA_LOWER_LIMIT + 1) + DATA_LOWER_LIMIT;
printf("Searching element: %d ", searchItem);
BinSearch(samples, 0, sampleSize - 1, searchItem);
return 0;
}
//======================== RandomizeAndPrint (int [], int) =======
void RandomizeAndPrint(int samples[], int sampleSize)
{
int index;
printf("Sample Size: %d ", sampleSize);
for (index = 0; index < sampleSize; index++)
{
samples[index] = rand() % (DATA_UPPER_LIMIT - DATA_LOWER_LIMIT + 1) + DATA_LOWER_LIMIT;
printf("%d ", samples[index]);
}
printf(" ");
}
//======================== FindMaxMin (int [], int) ==============
void FindMaxMin(int samples[], int sampleSize)
{
int index;
int MaxElement = samples[0];
int MinElement = samples[0];
for (index = 1; index < sampleSize; indexx++)
{
if (MaxElement < samples[index])
MaxElement = samples[index];
if (MinElement > samples[index])
MinElement = samples[index];
}
printf("Maximum = %d, Minimum = %d ", MaxElement, MinElement);
}
//======================== QuickSort (int [], int, int) ====
void QuickSort(int samples[], int first, int last)
{
int pivot;
if (first < last)
{
pivot = Partition(samples, first, last);
QuickSort(samples, first, pivot - 1);
QuickSort(samples, pivot + 1, last);
}
}
//======================== Partition (int samples [], int first, int last) =================
int Partition(int samples[], int first, int last)
{
int pivot = samples[last];
int leftIndex = first;
for (int j = first; j <= last; j++)
{
if (samples[j] < pivot)
{
Swap(&samples[leftIndex], &samples[j]);
leftIndex++;
}
}
Swap(&samples[leftIndex], &samples[last]);
for (int i = first; i < leftIndex; i++)
printf("%d ", samples[i]);
printf(" ", samples[leftIndex]);
for (int i = leftIndex + 1; i <= last; i++)
printf("%d ", samples[i]);
printf(" ")
}
//====================================!I need help here!===========
//===================== BinSearch (int samples[], int sampleSize) ===
void BinSearch(int samples[], int first, int last, int searchItem)
{
int midIndex;
if (first <= last)
{
midIndex = (first + last) / 2;
if (searchItem < samples[midIndex])
BinSearch(samples)
BinSearch(samples, first, midIndex - 1, searchItem);
else if (searchItem> samples[midIndex])BinSearch(samples, midIndex + 1, last, searchItem);
else
printf("Item Found: %d, Element Position: %d ", searchItem, midIndex);
}
else
printf("Item not Found: %d ", searchItem);
}
Explanation / Answer
Here is the complete working code with the SWAP function added and corrected Binary search and removed errors
[
void Swap(int &a, int &b)
{
// swapping two numbers by reference without using a temporary variable
a = a + b;
b = a - b;
a = a - b;
}
]
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <cstdlib>
#define ARRAY_SIZE 20 // Size of array
#define UPPER_LIMIT 20 // Max number of arrays used
#define LOWER_LIMIT 12 // Min number of arrays used
#define DATA_UPPER_LIMIT 80 // Max of each array element
#define DATA_LOWER_LIMIT 10 // Min of each array element
void RandomizeAndPrint(int[], int);
void FindMaxMin(int[], int);
void QuickSort(int[], int, int);
int Partition(int[], int, int);
void Swap(int &,int &);
void BinSearch(int[], int, int, int);
////////////////////////// void main ////////////////////////////////////////////
int main(void)
{
int samples[ARRAY_SIZE];
int sampleSize;
int searchItem;
srand(time(NULL));
sampleSize = rand() % (UPPER_LIMIT - LOWER_LIMIT + 1) + LOWER_LIMIT;
RandomizeAndPrint(samples, sampleSize);
FindMaxMin(samples, sampleSize);
QuickSort(samples, 0, sampleSize - 1);
printf("sorted: ");
for (int i = 0; i < sampleSize; i++)
printf("%d ", samples[i]);
printf(" ");
// Get a random number as search example & print it
searchItem = rand() % (DATA_UPPER_LIMIT - DATA_LOWER_LIMIT + 1) + DATA_LOWER_LIMIT;
printf("Searching element: %d ", searchItem);
BinSearch(samples, 0, sampleSize - 1, searchItem);
return 0;
}
//======================== RandomizeAndPrint (int [], int) =======
void RandomizeAndPrint(int samples[], int sampleSize)
{
int index;
printf("Sample Size: %d ", sampleSize);
for (index = 0; index < sampleSize; index++)
{
samples[index] = rand() % (DATA_UPPER_LIMIT - DATA_LOWER_LIMIT + 1) + DATA_LOWER_LIMIT;
printf("%d ", samples[index]);
}
printf(" ");
}
//======================== FindMaxMin (int [], int) ==============
void FindMaxMin(int samples[], int sampleSize)
{
int index;
int MaxElement = samples[0];
int MinElement = samples[0];
for (index = 1; index < sampleSize; index++)
{
if (MaxElement < samples[index])
MaxElement = samples[index];
if (MinElement > samples[index])
MinElement = samples[index];
}
printf("Maximum = %d, Minimum = %d ", MaxElement, MinElement);
}
//======================== QuickSort (int [], int, int) ====
void QuickSort(int samples[], int first, int last)
{
int pivot;
if (first < last)
{
pivot = Partition(samples, first, last);
QuickSort(samples, first, pivot - 1);
QuickSort(samples, pivot + 1, last);
}
}
//======================== Partition (int samples [], int first, int last) =================
int Partition(int samples[], int first, int last)
{
int pivot = samples[last];
int leftIndex = first - 1;
for (int j = first; j <= last - 1; j++)
{
if (samples[j] < pivot)
{
leftIndex++;
Swap(samples[leftIndex], samples[j]);
}
}
Swap(samples[leftIndex + 1], samples[last]);
for (int i = first; i < leftIndex; i++)
printf("%d ", samples[i]);
printf(" ", samples[leftIndex]);
for (int i = leftIndex + 1; i <= last; i++)
printf("%d ", samples[i]);
printf(" ");
return leftIndex + 1;
}
//====================================!I need help here!===========
//===================== BinSearch (int samples[], int sampleSize) ===
void BinSearch(int samples[], int first, int last, int searchItem)
{
int midIndex;
if (first <= last)
{
midIndex = (first + last) / 2;
if (searchItem < samples[midIndex])
{
BinSearch(samples, first, midIndex - 1, searchItem);
}
else if (searchItem > samples[midIndex])
BinSearch(samples, midIndex + 1, last, searchItem);
else
printf("Item Found: %d, Element Position: %d ", searchItem, midIndex);
}
else
printf("Item not Found: %d ", searchItem);
}
void Swap(int &a, int &b)
{
// swapping two numbers by reference without using a temporary variable
a = a + b;
b = a - b;
a = a - b;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.