ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
185
QUADRATIC, LOGARITHMIC, AND LINEAR COMPLEXITY SORTING
ALGORITHM COMPARISON AND EFFICIENCY EVALUATION
Toirov Bobirmirzo Nodir ugli
Uzbekistan, Bukhara district, Specialized school
11th grade student, E-mail: toirovbobirmirzo53@gmail.com
https://doi.org/10.5281/zenodo.14562263
Quadratic Sorting Algorithms Bubble Sort is a simple comparison-based
sorting algorithm. It iterates through the list repeatedly, comparing adjacent
elements and swapping them if they are not in the correct order. This process
repeats until the list is sorted.
Algorithm Steps:
1.
Start at the beginning of the list.
2.
Compare the first two elements.
3.
If the first element is larger than the second, swap them.
4.
Move to the next pair of elements and repeat steps 2–3.
5.
Continue this process until the end of the list.
6.
Repeat the entire process until no swaps are needed, indicating the
list is sorted.
Efficiency Evaluation:
Time Complexity:
Worst case: O(n²) – when the list is in reverse order.
Average case: O(n²).
Best case: O(n) – when the list is already sorted.
Memory Complexity:
O(1) – Bubble Sort is an in-place algorithm that requires no additional
memory.
Advantages and Disadvantages:
Advantages:
Simple to understand and implement.
Performs in-place sorting.
Disadvantages:
Inefficient for large datasets.
Quadratic time complexity limits its broader use.
Bubble Sort is useful for educational purposes and small datasets but is not
recommended for large datasets. Algorithms like Quick Sort or Merge Sort are
more efficient for such cases.
Python Code:
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
186
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# Example usage:
my_list = [64, 25, 12, 22, 11]
bubble_sort(my_list)
print("Sorted array:", my_list)
Conclusion:
Although Bubble Sort is easy to understand, its inefficiency for large datasets
limits its practical applications compared to more efficient algorithms.
Insertion Sort is a simple comparison-based sorting algorithm. It sorts a list
by taking each element and inserting it into its correct position, comparing it to
previous elements.
Algorithm Steps:
1.
Consider the first element in the list as sorted.
2.
Insert the selected element into the appropriate position in the
sorted section.
3.
Compare and place elements one by one into their correct positions.
4.
Repeat the process until the end of the list is reached.
Efficiency Evaluation:
Time Complexity:
Worst case: O(n²) – when the list is in reverse order.
Average case: O(n²).
Best case: O(n) – when the list is already sorted.
Memory Complexity:
O(1) – Insertion Sort is an in-place algorithm requiring no additional
memory.
Advantages and Disadvantages:
Advantages:
Easy to understand and implement.
Efficient for short lists.
Disadvantages:
Inefficient for large datasets.
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
187
Quadratic time complexity limits its broader use.
Use Cases:
Insertion Sort is suitable for short lists and scenarios where small
modifications to the list are required. It is inefficient for large datasets and may
lead to problems in such cases.
Python Code:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
Example Usage:
my_list = [64, 25, 12, 22, 11]
insertion_sort(my_list)
print("Sorted array:", my_list)
Conclusion:
Although Insertion Sort is easy to understand, its inefficiency for large datasets
makes it less suitable for real-world applications compared to more efficient
sorting algorithms.
Logarithmic Sorting Algorithms:
Merge Sort is a divide-and-conquer algorithm. It divides the input list into
smaller parts, recursively sorts them, and then merges them back together.
Algorithm Steps:
1.
Divide the list into two halves.
2.
Recursively apply Merge Sort to each half.
3.
Merge the sorted halves.
Efficiency Evaluation:
Time Complexity:
Worst case: O(n log n) – consistently efficient.
Average case: O(n log n).
Best case: O(n log n).
Memory Complexity:
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
188
O(n) – Merge Sort requires additional memory for temporary storage.
Advantages and Disadvantages:
Advantages:
Widely used.
Consistently efficient regardless of the input size.
Disadvantages:
Requires additional memory, which can increase space usage.
Merge Sort is effective for large datasets and is widely used due to its
consistent performance and stability.
Python Code:
python
Copy code
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
189
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
Example Usage:
python
Copy code
my_list = [64, 25, 12, 22, 11]
merge_sort(my_list)
print("Sorted array:", my_list)
Quick Sort is a sorting algorithm that selects a pivot element, partitions the
list into two parts based on the pivot, and recursively applies Quick Sort to the
partitions.
Algorithm Steps:
1.
Pivot Selection: Select a pivot element (e.g., the middle element) and
place it at the start of the list. Then move elements smaller than the pivot to the
left and larger elements to the right. This determines the final position of the
pivot.
2.
Partitioning: Split the list into two parts based on the pivot.
Recursively apply Quick Sort to each part.
3.
Repetition: Repeat Quick Sort for both the left and right partitions.
4.
Merge: Combine all parts to create the final sorted list.
Efficiency Evaluation:
Time Complexity:
Worst case: O(n²) – occurs when partitions are unbalanced.
Average case: O(n log n).
Best case: O(n log n)
Space complexity:
O(log n) – for recursive stack usage.
Advantages and Disadvantages:
Advantages:
Efficient in terms of average time complexity.
Reduces additional memory usage.
Minimizes the impact of using auxiliary variables on execution time.
Disadvantages:
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
190
In the worst case (when the pivot is poorly chosen), time complexity
can be high.
Unstable – may not preserve the relative order of equal elements.
If partitions are unbalanced, time complexity may increase.
Quick Sort is considered a widely used algorithm due to its average time
complexity and ability to leverage storage devices efficiently. It is highly
effective for sorting small to medium-sized datasets and has advantages over
other sorting algorithms in certain scenarios. If the dataset is small or the first
element of the list is well-suited as the pivot, Quick Sort can be both safe and
highly efficient.
Python Code:
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
Example Usage:
python
Copy code
my_list = [64, 25, 12, 22, 11]
quick_sort(my_list, 0, len(my_list) - 1)
print("Sorted array:", my_list)
Merge Sort:
ACADEMIC RESEARCH IN MODERN SCIENCE
International scientific-online conference
191
Merge Sort is an efficient algorithm in terms of average time and space
complexity. It is widely used and effective for large datasets. While it does not
require additional memory allocation by default, it may use extra space
internally.
Quick Sort:
Quick Sort is an efficient and widely used algorithm for average time and
space complexity. It performs well as a sorting algorithm and is often more
efficient than other sorting methods in well-optimized implementations.
However, its worst-case behavior, when partitions are unbalanced, can result in
high time complexity.
Heap Sort:
Heap Sort is an efficient and widely used algorithm in terms of average time
and space complexity. It operates by arranging elements in a heap structure.
While it requires additional memory and utilizes heap manipulation to reorder
elements, it performs well for handling large datasets and in remote data
operations.
Conclusion:
For standard datasets or when widespread usage is not required, Merge Sort or
Heap Sort is recommended. However, if other considerations need to be
accounted for, Quick Sort can be more efficient than the other two. By
understanding the advantages and disadvantages of each algorithm, it is
possible to select the best option for achieving optimal results with specific
datasets and remote data operations.
References:
1.
freecodecmp.org
2.
codesdope.com
3.
copyprogramming.com
4.
hyperskill.org
