Bubble Sort VS Selection Sort Sorting Algorithms


Sorting algorithms are crucial tools for arranging data in a systematic and orderly manner in the enormous ocean of computer science and algorithmic effectiveness. They are essential to many applications, from databases and search engines to commonplace jobs like compiling lists or organizing information tables. Bubble Sort and Selection Sort are two foundational techniques that stand as cornerstones of simplicity and efficiency among the myriad sorting algorithms.



In this essay, we compare these two sorting methods in an effort to comprehend their inner workings, advantages, and disadvantages. It will become clearer when and why one algorithm might be preferred over the other as we delve into the inner workings of Bubble Sort and Selection Sort. So buckle up as we set sail into the realm of sorting algorithms, navigating the waters of Bubble Sort and Selection Sort to assist you in making wise decisions in your coding endeavors.


Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. Large data sets should not be used with this approach due to its high average and worst-case time complexity.
 
          The algorithm works by,
  • traverse from left and compare adjacent elements and the higher one is placed at right side. 
  • In this way, the largest element is moved to the rightmost end at first. 
  • This process is then continued to find the second largest and place it and so on until the data is sorted.

How does Bubble Sort Work?

Let us understand the working of bubble sort with the help of the following illustration:

    Input: arr[] = {6, 3, 0, 5}


        First Pass : 

        The largest element is placed in its correct position, i.e., the end of the array.


        Second Pass : 

        Place the second largest element at correct position


        Third Pass :

        Place the remaining two elements at their correct positions.



    Sorted Array Output :

    11 12 22 25 34 64 90



Selection Sort


Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. 

The algorithm repeatedly chooses the smallest (or largest) member from the list's unsorted part and switches it with the part's initial element. Until the full list is sorted, this procedure is repeated for the remaining unsorted section. 

How does selection sort works ?

    Input Array : {64, 25, 12, 22, 11}

        First pass:
  • For the first position in the sorted array, the whole array is traversed from index 0 to 4 sequentially. The first position where 64 is stored presently, after traversing whole array it is clear that 11 is the         lowest value.
  • Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array, tends to appear in the first position of the sorted list.

        Second Pass:
  • For the second position, where 25 is present, again traverse the rest of the array in a sequential manner.
  • After traversing, we found that 12 is the second lowest value in the array and it should appear at the second place in the array, thus swap these values.

        Third Pass :
  • Now, for third place, where 25 is present again traverse the rest of the array and find the third least value present in the array.
  • While traversing, 22 came out to be the third least value and it should appear at the third place in the array, thus swap 22 with element present at third position.

        Fourth Pass :

  • Similarly, for fourth position traverse the rest of the array and find the fourth least element in the array 
  • As 25 is the 4th lowest value hence, it will place at the fourth position.

        Fifth Pass :

  • At last the largest value present in the array automatically get placed at the last position in the array
  • The resulted array is the sorted array.



Differences between Bubble Sort and Selection Sort :

  1. In bubble sort, two adjacent elements are compared. If the adjacent elements are not at the correct position, swapping would be performed, while in Selection Sort the minimum element is selected from the array and swap with an element which is at the beginning of the unsorted sub array.
  2. The Bubble Sort, The time complexities in best case and worst case are O(n) and O(n2) respectively, while in Selection Sort both best and worst cases is O(n 2).
  3. Bubble Sort is not an efficient sorting technique, while Selection Sort is an efficient sorting technique as compared to Bubble sort.
  4. Bubble Sort uses an exchanging method, while Selection Sort uses a selection method
  5. Bubble Sort is slower than the selection sort as a greater number of comparisons is required

As a result of our investigation of Bubble Sort and Selection Sort, we now have a better understanding of their distinctive qualities and appropriate applications. Keep in mind that picking the ideal sorting algorithm is simply one piece of the puzzle as you go with your coding endeavors. May your coding adventures always point you in the direction of effectiveness and success. Continue experimenting with diverse tools.


~Rizki


Created By : Rizki Aswangga Adiluhur
As an ORE assignment to fulfill CCIT-FTUI's requirement


Source :
https://www.geeksforgeeks.org/bubble-sort/
https://www.geeksforgeeks.org/selection-sort/
https://www.javatpoint.com/bubble-sort-vs-selection-sort

Comments

Post a Comment