Performance Analysis of Sorting Algorithms with Large Datasets

Abstract

This lab report analyzes the performance of the Quick Sort, Bubble Sort and Bucket Sort algorithms to determine which of these is the most efficient algorithm when it comes to sorting large data sets. The method used to conduct this experiment is feeding each algorithm large data sets of arrays/lists that contain 1,000 integers and keeping record of how long it takes for each algorithm to sort the arrays. According to all the data gathered at the end of the procedure, it was determined that among these three algorithms, the Quick Sort algorithm is the most efficient at sorting large amounts of data.

Introduction

An algorithm is a finite set of instructions that accomplish a particular ask. All algorithms must have an input, provide an output, be definite, finite, and effective. (Horowitz et al., 2008, p. 1). Sorting is the process of placing elements from a collection in some kind of order (Miller & Ranum. 2006, p. 207). A sorting algorithm is a set of definite instructions that takes in a collection of data and sorts the data in a particular order, either ascending or descending order and outputs the sorted collection of data. Sorting algorithms are important to the computer science field as they make it easier for data engineers to manage and understand their data. In general, there are lots of different algorithms available, but for this experiment we will only be focusing on analyzing the performance of three: Quick Sort, Bubble Sort and Bucket Sort. To see which of these algorithms performs the best we must look at two important factors: time complexity and space complexity. The space complexity of an algorithm is the amount of memory it needs to run to completion. The time complexity of an algorithm is the amount of computer time it needs to run to completion (Horowitz et al., 2008, p. 15).

Bubble Sort

Runs at O(n²) time complexity and has O(1) space complexity. (Miller & Ranum. 2006, p. 210).

Bubble Sort compares adjacent elements and exchanges the ones that are out of order. It makes multiple passes through the collection of data and each time it passes it places the next largest value in its proper place. (Miller & Ranum. 2006, p. 207).

This the Bubble Sort in Python:

def bubbleSort (alist):
	for passnum in range ( len (alist) – 1, 0, -1):
		for i in range (passnum):
			 if alist[i] > alist[i+1]:
				temp = alist[i]
				alist[i] = alist[i+1]
				alist[i+1] = temp

(Miller & Ranum. 2006, p. 209)

Bucket Sort

Runs at O(n+k) time complexity and has O(n) space complexity. (Aadhith et al., 2024, p. 1035)

Bucket Sort distributes the element inputs into a set of n buckets, where each bucket corresponds to a specific range of values. (Aadhith et al., 2024, p. 1034)

This is the Bucket Sort Algorithm in pseudo code:

sort (A)
	create n buckets B
	for i = 0 to n-1 do:
		k = hash (A[i])
		add A[i] to the kth bucket B[k]
		extract (B, A)
end 

extract (B, A)
	idx = 0
	for i = 0 to n-1 do:
		insertion sort (B)
		for m = 1 to size(B[i]) do:
			A[idx++] = mth element of B[i]
end

(Heineman et al., 2008, p. 348)

Quick Sort

Runs at O(nlog(n)) time complexity and has O(log(n)) space complexity. (Miller & Ranum. 2006, p. 226).

Quick sort uses divide and conquer. It selects a value, which is called pivot value, its role is to assist with splitting the collection. The actual position where the pivot belongs in the final sorted element collection is used to divide the collection for subsequent calls to the Quick Sort (Miller & Ranum. 2006, p. 222).

This is the Quick Sort in Python:

def quicksort (alist):
	quickSortHelper (alist, 0, len(alist) -1)

def quickSortHelper (alist, first, last):
	if first < last:
		splitpoint = partition (alist, first, last)
		quickSortHelper (alist, first, splitpoint – 1)
		quickSortHelper (alist, splitpoint + 1 last)

def partition (alist, first, last)
	pivotvalue = alist[first] 
	leftmark = first + 1
	rightmark = last
	done = False
	
	while not done:
		while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
			leftmark = leftmark + 1 
		while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
			rightmark = rightmark – 1 
		if rightmark < rightmark:
			done = True
		else:
			temp = alist[leftmark]
			alist[leftmark] = alist[rightmark]
			alist[rightmark] = temp

	temp = alist[first]
	alist[first] = alist[rightmark]
	alist[rightmark] = temp
return rightmark

(Miller & Ranum. 2006, p. 225).

Based on the time and space complexity of each algorithm, Quick Sort will be the most efficient at sorting large data sets between the three.

Materials and Methods

Materials:

Computer with the following algorithms programmed:
- Quick Sort
- Bubble Sort
- Bucket Sort
10 sets of arrays/lists with 1,000 integers each
Time module in the same file of each algorithm

Method:

For this procedure we will be repeating the following steps for each algorithm:

Take time with time module and save as start_time
Execute the algorithm with a data set
Take time with time module and save as end_time
Subtract the start_time from end_time (this is the total execution time)
Record execution time in a data table
Repeat for each data set (10 data sets total)

Bubble Sort

DATA SET	DATA SIZE (INT)	EXECUTION TIME (MS)	MEMORY USAGE (KB)
1	1000	1,922.265	0.328
2	1000	1,867.094	0.328
3	1000	1,908.67	0.328
4	1000	1,880.33	0.328
5	1000	1,891.591	0.328
6	1000	1,944.747	0.328
7	1000	1,937.2	0.328
8	1000	1,903.105	0.328
9	1000	1,928.07	0.328
10	1000	1,905.952	0.328

Average Execution Time: 1908.902 MS

Average Memory Usage: 0.328 KB

Bucket Sort

DATA SET	DATA SIZE (INT)	EXECUTION TIME (MS)	MEMORY USAGE (KB)
1	1000	11.532	98.88
2	1000	10.888	95.359
3	1000	9.34	95.291
4	1000	9.237	95.617
5	1000	8.876	94.68
6	1000	8.995	94.898
7	1000	8.913	95.211
8	1000	8.705	94.773
9	1000	9.025	95.367
10	1000	8.811	94.711

Average Execution Time: 9.432 MS

Average Memory Usage: 95.478 KB

Quick Sort

DATA SET	DATA SIZE (INT)	EXECUTION TIME (MS)	MEMORY USAGE (KB)
1	1000	17.848	40.719
2	1000	15.385	52.573
3	1000	14.371	44.344
4	1000	14.096	42.656
5	1000	16.089	47.297
6	1000	14.233	48.547
7	1000	14.313	42.969
8	1000	14.08	45.312
9	1000	14.91	46.883
10	1000	14.79	52.766

Average Execution Time: 15.011 MS

Average Memory Usage: 46.406 KB

Discussion

When analyzing the results of the experiment, Quick Sort is the most efficient algorithm at sorting large sets of data. Bubble Sort’s average execution time was the slowest among the three, but its average memory usage was the lowest which is great. On the other hand, when looking at Bucket Sorts results, it had the fastest average execution time but the greatest average memory usage. When finally looking at Quick Sorts results, it didn’t have the fastest average execution time or the lowest average memory usage. Its average time was faster than that of Bubble Sort and its average memory usage was lower than of Bucket Sort, making it more efficient in speed and in memory.

Conclusion

In this lab report we were able to analyze the performance of three sorting algorithms, Bubble Sort, Bucket Sort and Quick Sort. The results of the experiment showed that although Quick Sort wasn’t the fastest or wasn’t the best at space saving, it was the most efficient when dealing with large data sets.

References

Horowitz, E., Sahni, S., & Rajasekaran, S. (2008). Fundamentals of Computer Algorithms (2nd ed.). Galgotia Publications.

Miller & Ranum. (2006). Problem Solving with Algorithms and Data Structures using

Python (2nd ed.). Franklin, Beedle & Associates Incorporated.

Aadhith & Rajinikanth (2024). Enhancing Bucket Sort Efficiency: A Combinatorial

Approach to Algorithm Optimization. International Journal for Research in Applied Science & Engineering Technology.

Heineman, G., Pollice, G., & Selkow, S. (2008) Algorithms in a Nutshell. O’Rielly Media Inc.

Hugging Face Co. Sorting Algorithm Performance Metrics. https://huggingface.co/datasets/ismielabir/Sorting-Algorithms-Performance-Metrics/viewer/default