List: How to Quick Sort an Array in C++

This updated guide examines List: How to Quick Sort an Array in C++ and organizes the essential facts, background, and practical takeaways in clear American English.

Part 1

Creating the quickSort Function

1. Create the quickSort function. This is a recursivevoidfunction. It requires three parameters:
   • Thearray(anint array)
   • Theleftbound (anintvariable)
   • Therightbound (anintvariable; the size of thearraysubtracted by 1)
2. Create the variables. These variables will be used to go through the list and to swap the values. Four variables are needed:
   • Anint i(the left bound)
   • Anint j(the right bound)
   • Anint temp(a temporary variable used for swapping without losing any data)
   • Anint pivot(the value of the middle point that splits the list to make it easier to sort)
3. Create awhileloop to begin sorting. A loopwhile i ? jis used to go through the indexes of the list. These values will be changed as the sublists that are being sorted change.
4. Iterate through the left side. Anotherwhileloop checking if the element is less thanpivotiterates through the list. If it is less thanpivotvalue, increaseiby 1. This checks if the left side of the sublist needs to be sorted.
5. Iterate through the right side. Anotherwhileloop checking if the element is greater thanpivotiterates through the list. If it is greater thanpivot, decreasejby 1. This checks if the right side of the sublist needs to be sorted.
6. Begin swapping the values ifi ? j. Swapping the values of the list puts the values in ascending order. Assigning one value to another without a temporary variable will result in a loss of data. To avoid this, this procedure is used:
   • Assign the value of the list at indexitotemp.
   • Assign the value of the list at indexjto the list at indexi.
   • Assign temp to the list at indexj.
   • Add 1 toi.
   • Subtract 1 fromj.
7. Check if each half of the list is sorted. This is done by two recursive calls. The first function call sorts the left sublist created by changing the bounds. When the left side is completely sorted, the next recursive call sorts the right sublist by changing its bounds.
   • Ifleft< j, call the function withleftandias the bounds.
   • Ifright< i, call the function withiandrightas the bounds.

Part 2

Testing the quickSort Function

1. Create thelistin themainfunction. The array can be any size and can be initialized both explicitly and through other methods.
2. Output the unsortedlistusing afor-loop. The bounds of the loop go from 0 to thesizeof(list)/4. This piece of code gives the number of elements inlist.
3. Call the quickSort function. The three needed parameters are:
   • Thelist
   • Theleftbound (0)
   • Therightbound (the size of thearraysubtracted by 1)
4. Output the new list using afor-loop. Again, the bounds of the loop go from 0 to thesizeof(list)/4. This is because the sorted list contains the same amount of elements as the unsorted list (no data was lost).
5. Run the program to see the sorted list. The number of items inlistshould be the same in both lists.