Bubble Sort

What is a bubble sort?

 In A Level Computer Science, a bubble sort sorts items into order, smallest to largest
 It compares pairs of elements and swaps them if they are out of order
 The first element is compared to the second, the second to the third, the third to the fourth and so
on, until the second to last is compared to the last. Swaps occur if each comparison is out of
order
 This overall process is called a pass

Examiner Tips and Tricks

The highest value in the list eventually “bubbles” its way to the top like a fizzy drink, hence the name
“Bubble sort”

 Once the end of the list has been reached, the value at the top of the list is now in order and
the sort resets back to the start of the list. The next largest value is then sorted to the top of
the list
 More passes are completed until all elements are in the correct order
 A final pass checks all elements and if no swaps are made then the sort is complete
 An example of using a bubble sort would be sorting an array of names into alphabetical order, or
sorting an array of student marks from a test
Performing the bubble sort

Figure 1: Performing the Bubble sort

Time complexity of the bubble sort
 To determine the algorithm's execution time as measured by the number of instructions or steps
carried out Big-O notation must be used
 Four statements are present in the above algorithm O(1), followed by a while loop O(n) containing
two statements and a further for loop O(n). This results in the expression: 2n2 + 4
 As coefficients and lower order values are not used, this give the bubble sort O(n2) worst
case time complexity
 The best case scenario would be an already sorted list which means a time complexity
of O(n) as each item must still be compared to check if they are in order
 The average case scenario would be an almost sorted list leading to O(n2/2), which if
coefficients are removed still gives O(n2)

Space complexity of the bubble sort

 A bubble sort has a space complexity of O(1) because it operates in-place, requiring a fixed
amount of memory
 The fixed amount of memory is for variables such as loop counters and a temporary swap
variable

Tracing a bubble sort

 The trace table follows the algorithm through, updating values that change in the table
 Each iteration of the list reduces the overall size of the list by 1 as after each pass the previously
sorted final digit is in order and does not need to be rechecked. This means that 9 is in order and
doesn't need to be rechecked, followed by 9 and 7, followed by 9, 7 and 6 and so on
 When the if statement is checked a new row has been added to show the swap of list[j], list[j + 1]
and Temp, followed by the subsequent change to Swap from FALSE to TRUE
 After several iterations (that are not shown) the algorithm will eventually output a sorted list

Trace table of the bubble sort

LastElement Index Mylist[Index] Mylist[Index + 1] Temp Swap Output

10 1 5 9 FALSE
2 9 4
4 9 4 TRUE
3 9 2
2 9 9
4 9 6
6 9
5 9 7
7 9
6 9 1
1 9
7 9 2
2 9
8 4 9
9 4
 9 9 3
3 9
9 1 5 4 FALSE
4 5 5 TRUE
2 5 2
2 5

1 FALSE 1, 2, 2, 3, 4, 4, 5, 6, 7, 9

Implementing a Bubble Sort

Pseudocode
list = [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]
last = len(list)
swap = True
i = 0
while i < (last - 1) and (swap = True)
swap = False
for j = 0 to last - i - 2
if list[j] > list[j+1]
temp = list[j]
list[j] = list[j+1]
list[j+1] = temp
swap = True
endif
next j
i = i + 1
endwhile
print(list)
 The algorithm above implements an efficient bubble sort in that with each successive iteration,
the number of comparisons decreases
o This is due to the sorted end of the list not being rechecked as it is already sorted and
therefore inefficient to compare them
o This is managed by the j for loop where i increments after each iteration and reduces the
number of compared items by 1
o This is because the last iteration’s sorted element should already be in the correct
position. The overall effect is reducing unnecessary swaps
 Furthermore, using a while loop instead of a for loop means that if a swap does not occur then
the list is in order. A for loop would continue comparing even if the items are already in order

Python
def bubble_sort(list):
n = len(list)
for i in range(n - 1):
swapped = False
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
swapped = True
 if not swapped:
break # Early termination if no swaps occurred
return list

Java
public class BubbleSort {
public static void bubbleSort(int[] list) {
int n = [Link];
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (list[j] > list[j + 1]) {
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break; // Early termination if no swaps occurred
}
}
}

Insertion sort
What is an insertion sort?
 In A Level Computer Science, the insertion sort sorts one item at a time by placing it in the
correct position of an unsorted list
 This process repeats until all items are in the correct position
 Specifically, the current item being sorted is compared to each previous item
 If it is smaller than the previous item then the previous item is moved to the right and
the current item takes its place
 If the current item is larger than the previous item then it is in the correct position and the next
current item is then sorted as illustrated below
Performing the insertion sort

Figure 2: Performing the Insertion sort

Time complexity of an insertion sort
 In the above algorithm, one statement is present, a for loop with three statements and a nested
while loop that contains two statements
 The time complexity for the insertion sort would be 3n*2n + 1, giving 6n2 + 1. 3n comes from the
for loop having three statements inside it, not including the while. 2n comes from the while loop
having two statements inside it
 Removing coefficients and dominated factors leaves O(n2) as the worst case scenario
 The best case scenario would be an already sorted list which means each item is checked one
at a time giving a time complexity of O(n)

The average case scenario would be a half sorted list giving O(n2/2), which when coefficients are
removed still gives O(n2)

Space complexity of an insertion sort

 As the insertion sort requires no additional space, it is space complexity O(1)

Tracing an insertion sort

 Tracing through the insertion sort involves starting at element 1 (not 0)
 i increments through each element one at a time and each item is compared to the one previous.
If the previous item is bigger or equal it is set to list[position]
 If position equals 0 then the iteration is at the start of the list and the next iteration begins

Trace Table of the Insertion sort

list i item position list[position-1] list[position]

[5, 9, 4, 2, 7, 1, 2, 4, 3] 1 9 1 5 9
2 4 2 9 9
1 5 5
0
[4, 5, 9, 2, 7, 1, 2, 4, 3] 3 2 3 9 9
2 5 5
1 4 4
0
[2, 4, 5, 9, 7, 1, 2, 4, 3] 4 7 4 9 9
3 5 7
[2, 4, 5, 7, 9, 1, 2, 4, 3] 5 1 5 9 9
4 7 7
3 5 5
2 4 4
1 2 2
0 1
[1, 2, 4, 5, 7, 9, 2, 4, 3] 6 2 6 9 9
5 7 7
4 5 5
 3 4 4
2 2 2
[1, 2, 2, 4, 5, 7, 9, 4, 3] 7 4 7 9 9
6 7 7
5 5 5
4 4 4
[1, 2, 2, 4, 4, 5, 7, 9, 3] 8 3 8 9 9
7 7 7
6 5 5
5 4 4
4 4 4
3 2 3
[1, 2, 2, 3, 4, 4, 5, 7, 9]

Worked Example
The following pseudocode procedure performs an insertion sort on the array parameter.

01 procedure insertionSort(dataArray:byRef)
02 for i = 1 to [Link] - 1
03 temp = dataArray[i]
04 tempPos = i – 1
05 exit = false
06 while tempPos >= 0 and exit == false
07 if dataArray[tempPos] < temp then
08 dataArray[tempPos + 1] = dataArray[tempPos]
09 tempPos = tempPos - 1
10 else
11 exit = t rue
12 endif
13 endwhile
14 dataArray[tempPos + 1] = temp
15 next i
16 endprocedure
Describe how a bubble sort will sort an array of 10 elements.

[6]

Bubble sort compares each pair of adjacent elements [1]. If they are not in the correct order then the
elements are swapped [1] and a flag is set to false [1], otherwise they are not swapped [1]. The loop is
repeated while the flag is not false [1]. When the end of the array is reached, we return to the start and is
the process is repeated for a total of n times [1].
Implementing an insertion sort
Pseudocode
procedure insertsionSort(list)
n = len(list)
for i = 1 to n -1
item = list[i]
position = i
while position > 0 and list[position - 1] > item
list[position] = list[position -1]
position = position - 1
endwhile
list[position] = item
next i
endprocedure

list = [5, 9, 4, 2, 7, 1, 2, 4, 3]
insertionSort(list)
print(list)
 In the algorithm above, each item is iterated over starting with the first value (9) as the 5 is
already in the correct position

Examiner Tips and Tricks

 Remember, in computer science, indexing always starts at 0

 The 9 (the current item) is compared to each previous value using the “position” pointer. While
the “position” pointer is greater than the 0th index and the previous item (5) is also larger than 9
then the 5 will be moved right. 5 is less than 9 so no move happens. The 9 is therefore in the
correct position
 The process repeats with 4 which is compared to the 9, which is larger and therefore moved right,
then 4 is compared to 5, which is larger and is also moved right
 Moving an item right is defined using the “list[position] = list[position-1]” which sets the previous
item into the current “position”
 The for loop iterates over all items in the list and each is compared until the correct position is
found for each item

Python
def insertion_sort(data):
for i in range(1, len(data)):
item = data[i]
position = i
while position > 0 and data[position - 1] > item:
data[position] = data[position - 1]
position -= 1
data[position] = item
return data
Java
public class InsertionSort {

public static void insertionSort(int[] data) {

for (int i = 1; i < [Link]; i++) {
int item = data[i];
int position = i;
while (position > 0 && data[position - 1] > item) {
data[position] = data[position - 1];
position--;
}
data[position] = item;
}
}

Merge sort
What is a Merge Sort?
 Merge sort is an example of a divide and conquer algorithm that reduces the size of the
problem into smaller problems that are more easily solvable by an algorithm
 Specifically, the merge sort divides the list in half, creating two sub lists. Each sub list is then
divided into two until each sub list contains only one item or element
 Groups of two sub lists are then sorted and merged together to form new, larger sub lists until all
sub lists have been merged into a single sorted list
 The merge sort therefore contains two parts:
o Part one: Divide the list into sub lists until each sub list contains only one element
o Part two: Repeatedly merge groups of two and sort them, until all lists have been
merged into a single sorted list
 The merge sort has been illustrated below using a list of ten items: [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]
Performing the Merge sort

Figure 1: Performing the Merge sort

  Notice that halving the list sometimes produces odd numbers of elements in sub lists. When
dividing, all sub lists must contain a single element before merging can begin.
 When merging, only two sub lists can be merged at a time. Any left over sub lists are merged
in the next merging iteration
 In order to merge two sub lists, two pointers are required, one for each sub list.
The pointer keeps track of which elements are to be compared. Once an element has been
merged into the new list, the corresponding pointer is incremented. The process continues until
a list contains no elements to compare, at which point the remaining elements are appended to
the end of the new merged sub list.

Time Complexity of a Merge Sort

 To determine the algorithm's execution time as measured by the number of instructions or steps
carried out Big-O notation must be used
 The time complexity of a merge sort is dependent on its divide and conquer nature O(logn) and
the fact that n sub lists must be merged. This means the overall worst case time complexity of
the merge sort is O(nlogn)
 The best case and average case scenario time complexity of the merge sort is O(nlogn) as
regardless of the number of elements or item, n must still be merged and halved

Space Complexity of a Merge Sort

 The merge sort requires twice the amount of space of other sorting algorithms due to holding
copies of the left and right halves of the list. Its space complexity is therefore O(n) original space
and an additional O(n) space to store the copies of the list

Tracing a Merge Sort

 In the trace table below, several calls to merge sort are made which splits the list. Each call
generates a stack frame which is put on the stack. Stack frames are removed when the
current stack frame reaches the end of its code
 The list is gradually broken down into sub lists, starting with the left side of each sub list. Sub lists
are created until each sub list contains only one element which is the base case. When a base
case is reached the stack frame is removed and the program continues execution on the line
after the call to merge sort
 Each sub list is gradually merged, two at a time and passed up the stack to be merged with
another sub list in a later merge sort call
 Pointers are incremented during the merge such that the next element to merge in each sub list is
tracked and appropriately added to the new list. NewListPointer tracks the position of elements in
the new list
 Row 25 shows the algorithm completing the left side of the list and the beginning of the merge of
the right sub list which repeats the process outlined in the trace table

Trace Table for the Merge Sort

Split left, Left Right
Stack len(list)
Row left right right or newList mid newListPointer
frame > 1?
merge? Pointer Pointer
15, 5, 9, 10,
1 1 TRUE LEFT 5
2, 7, 4 1, 8, 3
2 2 TRUE 15, 5 2, 7, 4 LEFT 2
3 3 TRUE 15 5 LEFT 0
4 4 FALSE BASE CASE
5 3 TRUE 15 5 RIGHT 0
6 4 FALSE BASE CASE
7 3 TRUE 15 5 MERGE [5, 15] 0 0 0 0
8 3 TRUE 2 7, 4 LEFT 1
9 4 FALSE BASE CASE
10 3 TRUE 7 4 LEFT 0
11 4 FALSE BASE CASE
12 3 TRUE 7 4 RIGHT 0
13 4 FALSE BASE CASE
14 3 TRUE 7 4 MERGE [4, 7] 0 0 0 0
15 3 TRUE 2 4, 7 MERGE 1 0 0 0
16 [2] 1 1
17 [2, 4] 1 2
18 [2, 4, 7] 2 3
19 3 TRUE 5, 15 2, 4, 7 MERGE 2 0 0 0
20 [2] 1 1
21 [2, 4] 2 2
22 [2, 4, 5] 1 2 3
[2, 4, 5,
23 1 3 4
7]
[2, 4, 5, 7,
24 1 4 5
15]
25 2 TRUE 9, 10 1, 8 3 LEFT 2
Examiner Tips and Tricks
Merge sort is a complex algorithm. You will not be asked to derive its time or space complexity in detail.

 You will however be expected to know and justify its time and space complexity

Implementing a merge sort

Pseudocode
procedure mergesort(list)
if len(list) > 1 then
mid = len(list) div 2
left = list[:mid]
right = list[mid:]

mergesort(left)
mergesort(right)

leftPointer = 0
rightPointer = 0
newListPointer = 0
while leftPointer < len(left) and rightPointer < len(right)
if left[leftPointer] < right[rightPointer] then
list[newListPointer] = left[leftPointer]
leftPointer = leftPointer + 1
else
list[newListPointer] = right[rightPointer]
rightPointer = rightPointer + 1
endif
 newListPointer = newListPointer + 1
endwhile

while leftPointer < len(left)

list[newListPointer] = left[leftPointer]
leftPointer = leftPointer + 1
newListPointer = newListPointer + 1
endwhile

while rightPointer < len(right)

list[newListPointer] = right[rightPointer]
rightPointer = rightPointer + 1
newListPointer = newListPointer + 1
endwhile
endif
endprocedure

list = [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]

mergesort(list)
print(list)
 It is important to note that the merge sort uses [popover id="N-tIO9JV~O-0w97n"
label="recursion"] in order to work. To divide the list into sub lists, the merge sort algorithm
must call itself, using a [popover id="5UjdORCO7kg2tW1L" label="base case"] of one
element. Repeated calls to the algorithm are put on the [popover id="vZKPSwu5BsgHPpV_"
label="stack"]. Once each list is composed on one element, [popover
id="eAY1NI_y6NFvH4Le" label="stack frame"] are removed from the stack and processed
 It is furthermore important to note that [:mid] means “all elements up to but not including the
mid value” and [mid:] means “all elements starting from and including the mid value”
o This technique is known as slicing
 Once the list has been split, and no more recursive calls are made, three new variables are
defined per stack frame:
o leftPointer (keeps track of the left sub list)
o rightPointer (keeps track of the right sub list)
o newListPointer (keeps track of the next available space in the sorted list)
 The new list is merged in two stages:
o Stage one: Merge all elements until one list is empty
 The first while loop manages this process. The left and right pointers increment
over the left and right lists, comparing elements one at a time. If one is smaller
than the other then it is placed in the next available space in the new list
o Stage two: Append the non-empty list's remaining elements to the new list
 This is managed by the final two while loops. One merges if the left half has
remaining elements. The other merges if the right half has remaining elements.
Only one will be called, not both

Python
def merge_sort(list):
if len(list) > 1:
mid = len(list) // 2
left = list[:mid]
right = list[mid:]
merge_sort(left)
merge_sort(right)
left_pointer, right_pointer, new_list_pointer = 0, 0, 0
new_list = [None] * len(list)
while left_pointer < len(left) and right_pointer < len(right):
if left[left_pointer] < right[right_pointer]:
 new_list[new_list_pointer] = left[left_pointer]
left_pointer = left_pointer + 1
else:
new_list[new_list_pointer] = right[right_pointer]
right_pointer = right_pointer + 1
new_list_pointer = new_list_pointer + 1
while left_pointer < len(left):
new_list[new_list_pointer] = left[left_pointer]
left_pointer = left_pointer + 1
new_list_pointer = new_list_pointer + 1
while right_pointer < len(right):
new_list[new_list_pointer] = right[right_pointer]
right_pointer = right_pointer + 1
new_list_pointer = new_list_pointer + 1
list[:] = new_list
return list

list = [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]

merge_sort(list)
print(list) # Output: [1, 2, 3, 4, 5, 7, 8, 9, 10, 15]
Java
public class MergeSort {

public static void mergeSort(int[] data) {

if ([Link] > 1) {
int mid = [Link] / 2;
int[] left = new int[mid];
int[] right = new int[[Link] - mid];
[Link](data, 0, left, 0, mid);
[Link](data, mid, right, 0, [Link] - mid);
mergeSort(left);
mergeSort(right);
merge(data, left, right);
}
}

private static void merge(int[] data, int[] left, int[] right) {

int leftPointer = 0, rightPointer = 0, newListPointer = 0;
while (leftPointer < [Link] && rightPointer < [Link]) {
if (left[leftPointer] < right[rightPointer]) {
data[newListPointer] = left[leftPointer];
leftPointer++;
} else {
data[newListPointer] = right[rightPointer];
rightPointer++;
}
newListPointer++;
}
[Link](left, leftPointer, data, newListPointer, [Link] -
leftPointer);
[Link](right, rightPointer, data, newListPointer, [Link] -
rightPointer);
}

public static void main(String[] args) {

int[] data = {15, 5, 2, 7, 4, 9, 10, 1, 8, 3};
mergeSort(data);
 [Link]([Link](data)); // Output: [1, 2, 3, 4, 5, 7, 8,
9, 10, 15]
}
}

Quick sort
What is a quick sort?
 In A Level Computer Science, a quick sort is another example of a divide and conquer algorithm
that reduces the size of the problem into smaller problems that are more easily solvable by
an algorithm
 Unlike the merge sort however, quick sort does not use any additional storage
 Below is an illustration of the quick sort
Figure 2: Performing the Quick sort
Time complexity of a quick sort
 Like merge sort, quick sort is a divide and conquer algorithm which means the problem size is
reduced, creating an easier problem to solve. This gives quick sort a time complexity of O(logn).
Like merge sort it must sort n lists, giving it an overall best case time complexity of O(nlogn)
 Unlike merge sort, quick sort has a worst case time complexity of O(n2). This is due to
the potential placement of the pivot values
o If the pivot value is placed roughly in the middle of the list, then quick sort performs
optimally
o If the pivot is sorted at the start of the list, all items are above this value. If the pivot is
sorted at the end of the list, all items are below this value
o As the sorted pivots are at the extremes of the list this means there is only one call to
quick sort rather than two, as no second sublist exists past the extreme. Each
subsequent list has a size of n-1 with n operations performed, leading to n*(n-1) or O(n2)
o Quick sort also has the problem that if the list is too large or pivots aren’t optimally
chosen and recursion continues for too long, this can cause a stack overflow as too
many stack frames have been placed on the stack

Space complexity of a quick sort

 Quick sort requires additional memory as copies of lists are made and put on the stack. The
overall space complexity is therefore O(n) with O(n) additional space required

Tracing a quick sort

 The trace table below shows the process of calling the quick sort and moving the left and right
pointers up and down the list to find elements to swap and then find the correct position of the
pivot
 Once the pivot is in place, quick sort is recursively called on both sublists on either side of the
pivot. Note that a second call to quick sort may not exist if the pivot value ends on either extreme
of the list
 The process repeats, calling quick sort on progressively smaller sublists until all values are in the
correct order

Trace Table for the Quick sort

list operation done pivot list[pivot] left list[left] right list[right]

[8, 2, 6, 1, 7, 9, 1, 4] QUICKSORT False 0 8 1 2 7 4
INC LEFT 1 2
2 6
3 1
4 7
5 9
DEC RIGHT 7 4
[8, 2, 6, 1, 7, 4, 1, 9] SWAP 5 4 7 9
INC LEFT 6 1
7 9
DEC RIGHT 6 1
[1, 2, 6, 1, 7, 4, 8, 9] SWAP PIVOT True 6 8 7 9 0 1
[1, 2, 6, 1, 7, 4] QUICKSORT False 0 1 1 2 5 4
INC LEFT 1 2
DEC RIGHT 5 4
4 7
3 1
2 6
1 2
0 1
SWAP PIVOT True 0 1 1 2 0 1
[2, 6, 1, 7, 4] QUICK SORT
CONTINUE UNTIL ALL ITEMS SWAPPED
[1, 1, 2, 4, 6, 7, 8, 9]
Worked Example
A 1-dimensional array stores a set of numbered cards from 0 to 7. An example of this data is
shown below

[2, 0, 1, 7, 4, 3, 5, 6]

A programmer is writing a computer program to sort the cards into the correct order (0 to 7).

i) Show how an insertion sort would sort the array in above into the correct order. Draw the array
after each move

3 marks

ii) Describe how a quick sort algorithm works with the data in shown above.

6 marks

i)

[2, 0, 1, 7, 4, 3, 5, 6]

[0, 1, 2, 7, 4, 3, 5, 6] [1]

Sort the 0 into place

[0, 1, 2, 4, 7, 3, 5, 6]

[0, 1, 2, 3, 4, 7, 5, 6] [1]

Sort 4 and 3 into place

[0, 1, 2, 3, 4, 7, 5, 6]

[0, 1, 2, 3, 4, 5, 6, 7] [1]

Sort 5 and 6 into place

ii) Quick sort uses divide and conquer to split the list into sublists [1]. The first item becomes the pivot, so
2 is the pivot here [1]. Compare each item to the pivot, 0 to 2, 1 to 2, etc [1]. Two lists are created, one
with items less than the pivot [0, 1] [1] and one with items more than the pivot [7, 4, 3, 5, 6] [1]. Quick sort
is called on the new sublists and the lists are eventually recombined. [1]

Implementing a Quick Sort

Pseudocode
function quicksort(list, start, end)

if start <= end then

return
else
pivot = list[start]
left = start + 1
right = end
done = False
while done == False
while left <= right and list[left] <= pivot
left = left + 1
endwhile

while right >= left and list[right] >= pivot

right = right - 1
endwhile

if left < right then

temp = list[left]
list[left] = list[right]
list[right] = temp
else
done = True
endif
endwhile

temp = items[start]
list[start] = list[right]
list[right] = temp

quicksort(list, start, right - 1)

quicksort(list, right + 1, end)
endif

return list
endfunction
 The quick sort works in several stages
o 1) The pivot is set to the 0th element, the left pointer is set to the 1st element and
the right pointer is set to the end of the list
o 2) The left pointer increments while it is less than or equal to the right pointer and
the value indexed by the left pointer is less than or equal to the pivot value. Once the
left pointer finds a value bigger than the pivot, or it passes the right pointer it stops
o 3) After the left pointer has been incremented, the right pointer is decremented. While
the right pointer is greater than or equal to the left pointer and the value indexed by
 the right pointer is greater than or equal to the pivot value, the right pointer is
decremented
o 4) If both pointers have not yet passed each other but both have finished moving,
the values indexed by both pointers are swapped. The pointers then continue moving
as per step 2 and 3
o 5) If both pointers pass each other then the swapping is done. The pivot value is
then swapped with the value indexed by the right pointer. The pivot value is now in the
correct position and is sorted
o 6) Both sides of the pivot value now exist as two new sublists. Quicksort is recursively
called on both sublists and the process repeats as per step 1
o 7) Steps 1-7 repeat until all sublists have been sorted

Python
def quicksort(data, start, end):
if start <= end:
pivot = data[start]
left = start + 1
right = end
done = False
while not done:
while left <= right and data[left] <= pivot:
left += 1
while right >= left and data[right] >= pivot:
right -= 1
if left < right:
temp = data[left]
data[left] = data[right]
data[right] = temp
else:
done = True
temp = data[start]
data[start] = data[right]
data[right] = temp
quicksort(data, start, right - 1)
quicksort(data, right + 1, end)
return data

data = [5, 2, 7, 4, 9, 10, 1, 8, 3]

quicksort(data, 0, len(data) - 1)
print(data) # Output: [1, 2, 3, 4, 5, 7, 8, 9, 10]

Java
public class QuickSort {

public static void quickSort(int[] data, int start, int end) {

if (start < end) {
int pivotIndex = partition(data, start, end);
quickSort(data, start, pivotIndex - 1);
quickSort(data, pivotIndex + 1, end);
}
}

private static int partition(int[] data, int start, int end) {

int pivot = data[start];
int left = start + 1;
int right = end;
while (true) {
 while (left <= right && data[left] <= pivot) {
left++;
}
while (right >= left && data[right] >= pivot) {
right--;
}
if (left < right) {
swap(data, left, right);
} else {
break;
}
}
swap(data, start, right);
return right;
}

private static void swap(int[] data, int i, int j) {

int temp = data[i];
data[i] = data[j];
data[j] = temp;
}

public static void main(String[] args) {

int[] data = {5, 2, 7, 4, 9, 10, 1, 8, 3};
quickSort(data, 0, [Link] - 1);
[Link]([Link](data)); // Output: [1, 2, 3, 4, 5, 7, 8, 9, 10]
}
}