Sort algorithms: QuickSort, BubbleSort y SelectionSort

Spread the love

In this post we are going to put, in Java code, the implementation of the bubble, selection and quicksort sorting algorithms. Some blog readers have requested them and they are one of the algorithms that are most studied in the faculty.

QuickSort

The quicksort algorithm has a logarithmic complexity O(n log n).

public static void quickSort(int[] arr, int left, int right) {
	    int pivotIndex = left + (right - left) / 2;
	    int pivotValue = arr[pivotIndex];
	    int i = left;
	    int j = right;
	    while (i <= j) {
	      while (arr[i] < pivotValue) {
	        i++;
	      }
	      while (arr[j] > pivotValue) {
	        j--;
	      }
	      if (i <= j) {
	        int tmp = arr[i];
	        arr[i] = arr[j];
	        arr[j] = tmp;
	        i++;
	        j--;
	      }
	      if (left < i) {
	        quickSort(arr, left, j);
	      }
	      if (right > i) {
	        quickSort(arr, i, right);
	      }
	    }
	  }

BubbleSort

This is undoubtedly one of the easiest to implement and most used by students. The complexity is O (n ^ 2).

<pre class="EnlighterJSRAW" data-enlighter-language="java" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">public static void bubbleSort(int[] arr) {
	    int lastIndex = arr.length - 1;
	    for (int j = 0; j &lt; lastIndex; j++) {
	      for (int i = 0; i &lt; lastIndex - j; i++) {
	        if (arr[i] > arr[i + 1]) {
	          int tmp = arr[i];
	          arr[i] = arr[i + 1];
	          arr[i + 1] = tmp;
	        }
	      }
	    }
	  }</pre>

Selection Sort

Like bubble, double nesting causes O (n ^ 2).

public static void selectionSort(int[] arr) {
	    int len = arr.length;
	    for (int i = 0; i < len - 1; i++) {
	      int minIndex = i;
	      for (int j = i + 1; j < len; j++) {
	        if (arr[j] < arr[minIndex]) {
	          minIndex = j;
	        }
	      }
	      int tmp = arr[minIndex];
	      arr[minIndex] = arr[i];
	      arr[i] = tmp;
	    }
	  }

I hope these algorithms serve you.

Leave a Reply

Your email address will not be published. Required fields are marked *