# in this week s lesson the algorithms quicksort and bubblesort aredescribed in sortin 4951934

In this week’s lesson,the algorithms
quicksort and
Main.cpp /********************************************

* Week 4lesson:                          *

*   ArrayList class with sorting algorithms *

*********************************************/ #include

#include “ArrayList.h”

#include using namespace std; /*

* Program to test the ArrayList class.

*/

int main()

{

srand((unsigned)time(0));    //creating a list of integers

ArrayList numbersCopy1, numbersCopy2;     //filling the list with random integers

for (int i = 0; i   {

int number = rand()%100;

}     //printing the list

cout

numbersCopy1.display();     //testing bubblesort

cout

numbersCopy1.bubbleSort();

numbersCopy1.display();     //testing quicksort

cout

numbersCopy2.quicksort();

numbersCopy2.display();    return 0;

}
ArrayList.h /********************************************

* Week 4lesson:                          *

*   ArrayList class with sorting algorithms *

*********************************************/ /*

* Class implementing an array based list. Bubblesort and quicksortalgorithms

* are implemented also.

*/

class ArrayList

{

public:

ArrayList ();

~ArrayList();

bool isEmpty();

void display();

void removeAt(int);

void bubbleSort();

void quicksort();

private:

void quicksort(int, int);

int findPivotLocation(int, int);

int SIZE;       //size of thearray that stores the list items

int *list;       //array tostore the list items

int length;   //amount of elements in thelist

};
ArrayList.cpp /********************************************

* Week 4lesson:                          *

*   ArrayList class with sorting algorithms *

*********************************************/ #include

#include “ArrayList.h” using namespace std; /*

* Default constructor. Sets length to 0, initializing the list asan empty

* list. Default size of array is 20.

*/

ArrayList::ArrayList()

{

SIZE = 20;

list = new int[SIZE];

length = 0;

} /*

* Destructor. Deallocates the dynamic array list.

*/

ArrayList::~ArrayList()

{

delete [] list;

list = NULL;

} /*

* Determines whether the list is empty.

*

* Returns true if the list is empty, false otherwise.

*/

bool ArrayList::isEmpty()

{

return length == 0;

} /*

* Prints the list elements.

*/

void ArrayList::display()

{

for (int i=0; i

cout

cout

} /*

* Adds the element x to the end of the list. List length isincreased by 1.

*

* x: element to be added to the list

*/

{

if (length == SIZE)

{

cout

}

else

{

list[length] = x;

length++;

}

} /*

* Removes the element at the given location from the list. Listlength is

* decreased by 1.

*

* pos: location of the item to be removed

*/

void ArrayList::removeAt(int pos)

{

if (pos < 0 || pos >= length)

{

cout

}

else

{

for ( int i = pos; i

list[i] =list[i+1];

length–;

}

} /*

* Bubble-sorts this ArrayList

*/

void ArrayList::bubbleSort()

{

for (int i = 0; i

for (int j = 0; j

if (list[j] >list[j + 1])

{

//swap list[j] and list[j+1]

int temp = list[j];

list[j] = list[j + 1];

list[j + 1] = temp;

}

} /*

* Quick-sorts this ArrayList.

*/

void ArrayList::quicksort()

{

quicksort(0, length – 1);

} /*

* Recursive quicksort algorithm.

*

* begin: initial index of sublist to be quick-sorted.

* end: last index of sublist to be quick-sorted.

*/

void ArrayList::quicksort(int begin, int end)

{

int temp;

int pivot = findPivotLocation(begin, end);    // swap list[pivot] and list[end]

temp = list[pivot];

list[pivot] = list[end];

list[end] = temp;    pivot = end;    int i = begin,

j = end – 1;    bool iterationCompleted = false;

while (!iterationCompleted)

{

while (list[i]            i++;

while ((j >= 0) &&(list[pivot]

j–;        if (i

{

//swap list[i]and list[j]

temp =list[i];

list[i] =list[j];

list[j] =temp;            i++;

j–;

} else

iterationCompleted = true;

}    //swap list[i] and list[pivot]

temp = list[i];

list[i] = list[pivot];

list[pivot] = temp;    if (begin

quicksort(begin, i – 1);

if (i + 1

quicksort(i + 1, end);

} /*

* Computes the pivot location.

*/

int ArrayList::findPivotLocation(int b, int e)

{

return (b + e) / 2;

} Attached