Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

Bubble Sort vs Quick Sort

In this article, we are going to compare two sorting techniques, Bubble sort and Quick Sort. In starting, we will first discuss the idea of sorting an array using bubble sort and quick sort both, and later on, we will discuss their differences.

Let’s start the discussion with the Bubble sort:

Q. Discuss the idea of bubble sort through an example:

Bubble sort - The bubble sort is a ‘subtract and conquer’ based sorting technique. In which it continuously compares all the elements and places all the elements in their right order. It is called bubble sort because it only compares two adjacent elements referred to as the bubble at any instant.

On each complete iteration of the internal for loop, the largest element is placed at the last index of the unsorted part of the array.

The pseudo-code of the Bubble Sort Function:

1. Bubble Sort (A, N)
2.	For I = 1 to N - 1
3.		For J = 0 to N - I – 1
4.			If A[J] > A[J + 1]
5.				Swap (A[J], A[J + 1])
// Where N represents the number of elements present in the array A.

// Where N represents the number of elements present in the array A.

In the above pseudo-code, we have nested for-loops. The internal for-loop starts and ends at 0 and N – I – 1, respectively, and the external for-loop starts and ends at 1 and N – 1, respectively. The if-block checks if the element at the right is smaller than the element at the left and swaps them if the condition is satisfied.

Now, let us sort a sample array to get a complete overview of the bubble sort.

Consider an array A[] = {17, 12, 16, 4, 3} with five elements passed to the bubble sort function. The steps involved in sorting the given array using bubble sort are listed below:

1. First iteration of External For-Loop – I = 1. The internal for loop starts from 0 and ends at 5 – 1 – 1 = 3.

  • First Iteration of Internal For-Loop, J = 0.
    Here, A[J] = 17 and A[J + 1] = 12 and 17 > 12. Hence, the if-condition is true. We swap them, and the 17 and 12 are now placed in ascending order.
Bubble Sort vs Quick Sort
  • Second Iteration of Internal For-Loop, J = 1.
    Here, A[J] = 17 and A[J + 1] = 16 and 17 > 16. Hence, the if-condition is true. We swap them, and the 17 and 16 are now placed in ascending order.
Bubble Sort vs Quick Sort
  • Third Iteration of Internal For-Loop, J = 2.
    Here, A[J] = 17 and A[J + 1] = 4 and 17 > 4. Hence, the if-condition is true. We swap them, and the 17 and 4 are now placed in ascending order.
Bubble Sort vs Quick Sort
  • Fourth Iteration of Internal For-Loop, J = 3.
    Here, A[J] = 17 and A[J + 1] = 3 and 17 > 3. Hence, the if-condition is true. We swap them, and the 17 and 3 are now placed in ascending order.
Bubble Sort vs Quick Sort

We can see that the largest element = 17, has finally taken his place. Now, we have the unsorted array of size N - 1 = 4. We repeat the same process for the remaining elements, same as above.

2. Second Iteration of External For-Loop, I = 1

In this iteration, the second largest value = 16 will be placed at the index = 3, as shown in the figure.

Bubble Sort vs Quick Sort

3. Third Iteration of External For-Loop, I = 2

In this iteration, the third largest value = 12 will be placed at the index = 3, as shown in the figure.

Bubble Sort vs Quick Sort

4. Fourth Iteration of External For-Loop, I = 3

In this iteration, the fourth largest value = 4 will be placed at the index = 1. Also, the smallest value takes its position at index = 0, as shown in the figure below:

Bubble Sort vs Quick Sort

At the end of all the iterations of the external for loop, we have a sorted array as the program’s output.

Now, let us move to the idea of Quick Sort:

Q. Discuss the idea of Quick Sort with an example.

Quick Sort – The quick sort algorithm uses the ‘divide and conquer’ technique to sort several elements. The quick sort selects a random pivot element and places all the elements smaller than the pivot on its left side and all the elements greater than the pivot on its right side. By doing so, the pivot element reaches its correct position in the array. Now, the problem is divided into two subarrays which are the left subarray and right subarray. The quick sort repeats the same process on the left and right subarrays recursively until the array gets sorted.

The idea of selecting a good pivot element – The performance of the quick sort totally depends on the nature of the pivot element. A good pivot element enhances the performance of the quick sort. The way to select the pivot element is to choose the first, middle or last element as the pivot. But there is no best way to find a good pivot element. The better the randomness of elements, the better the chance to get a good pivot element.

Now, let us see the pseudo-code of the Quick Sort. The quick sort algorithm consists of two function blocks: the partition function and the quick sort function.

The pseudo-code of the Quick Sort function:

1. Quick Sort (A, L, R)
2.	If (L < R)
3.		Q = partition (A, L, R)
4.		Quick Sort (A, L, Q - 1)
5.		Quick Sort (A, Q + 1, r)


// L -> The left index of the array
// R-> The right index of the array

In the above pseudo-code, the quick function first calls the partition function and stores the index return by the partition function in Q and calls itself two times: Quick Sort (A, L, Q - 1) and Quick Sort (A, Q + 1, R).

The pseudo-code of the partition function:

1. Partition (A, L, R)
2.	Pivot = A[R]
3.	I = L -1
4.	for J = 0 to R - 1
5.		If (A[J] <= Pivot)
6.			I = I + 1
7.			Swap (A[I] and A[J])
8.	Swap (A[I + 1] and A[R])
9.	Return i + 1 // Index of the pivot element

The partition function compares the pivot element with all the values, makes necessary swapping, places the pivot element at its correct position in the array, and returns its index to the quick sort function.

Now, let us understand the idea of the quick sort function:

Consider an unsorted array A[] = {27, 11, 17, 22, 4, 5, 13} with seven elements in it. The steps involved in sorting the given array using the quick sort are listed below:

Bubble Sort vs Quick Sort
  1. Quick Sort (A, 0, 6) is called
    The quick sort function first calls the Partition function (A, 0, 6). Let us first see the steps of the partition function.

    Partition (A, 0, 6) is called – Here, the partition function selects the last element as the pivot element, Pivot = A[R] = A[6] = 13 and sets the value of I = L – 1 = 0 -1 = -1. Now, the for-loops starts from J = 0 to 6 - 1 = 5.
  • When J = 0
    Here, A[J] = 27 which is greater than the Pivot = 13. So, the if-condition fails, no changes occur in this iteration.
Bubble Sort vs Quick Sort
  • When J = 1
    Here, A[J] = 11 which is less than the pivot = 13. So, the if-condition is true. Updating the value of I = -1 + 1 = 0 and swapping A[I] = 27 and A[J] = 11.
Bubble Sort vs Quick Sort
  • When J = 2
    Here, A[J] = 17 which is greater than the Pivot = 13. So, the if-condition fails, no changes occur in this iteration.
Bubble Sort vs Quick Sort
  • When J = 3
    Here, A[J] = 22 which is greater than the Pivot = 13. So, the if-condition fails, no changes occur in this iteration too.
Bubble Sort vs Quick Sort
  • When J = 4
    Here, A[J] = 4, which is less than the pivot = 13. So, the if-condition is true. Updating the value of I = 0 + 1 = 1 and swapping A[I] = 27 and A[J] = 4.
Bubble Sort vs Quick Sort
  • When J = 5
    Here, A[J] = 5
    Here, A[J] = 5 which is less than the pivot = 13. So, the if-condition is true. Updating the value of I = 1 + 1 = 2 and swapping A[I] = 17 and A[J] = 5.
Bubble Sort vs Quick Sort

Now, swapping A[I + 1] = 22 and A[R] = 13.

As we can see, the elements on the left side of the pivot are smaller, and the elements on the right side are larger. Hence, the pivot is placed at its correct position in the array.

Bubble Sort vs Quick Sort

The partition function returns the index of the pivot element which is I = 2 + 1 = 3. And the control is again transferred to the quick sort function.

2. Here, the quick sort function calls itself on the left and right subarrays. The left and right subarrays are treated as the same problem separately. The quick sort algorithm repeats the same steps on them.

After complete execution of all the function calls, we get the desired sorted array as shown below:

Bubble Sort vs Quick Sort
Bubble Sort vs Quick Sort

Let us discuss the differences between sorting an array using Bubble Sort and Quick Sort. The main differences between these two sorting algorithms are listed below in the table:

 Bubble SortQuick Sort
DefinitionThe idea of bubble sort is to compare the adjacent elements one by one and maintain the required order between them.The idea of quick sort is to select a random pivot element, place smaller elements left to the pivot and larger elements right to the pivot, and repeat the same process for the left and right parts recursively.
ApproachSubtract and conquerDivide and conquer
Time ComplexitiesBest case: T(n) = O(n), Average case: T(n) = O(n ^ 2)
Worst case: T(n) = O(n ^ 2)
Best case: T(n) = O(n logn),
Average case: T(n) = O(n logn)
Worst case: T(n) = O(n ^ 2)
Best-case and worst-case comparisonWhen we pass a sorted array, its flag version detects the sorted nature of the element in the single run and achieves the linear time complexity, O(n).When we pass a sorted array, it starts behaving like the subtract and conquer sorting techniques, and its time complexity becomes O(n^2). This is because it always selects the minimum and maximum element as the pivot, and the problem size becomes equal to n-1 after the first call of the partition function.
Recurrence RelationT(n) = T(n - 1) + nT(n) = 2T(n / 2) + n
StabilityStable – The order of similar elements remains unchanged.Unstable – The order of similar elements may change.
ComplexityThe complexity is very low in comparison to quick sort.It is the most complex sorting algorithm among all six fundamental sorting algorithms.
MemoryLess space is required.More space is required to manage the function calls.
Space TypeInternalInternal
MethodExchangingPartition
SpeedSlowerFaster



ADVERTISEMENT
ADVERTISEMENT