Data Structures - Sorts with Java code

Selection Sort

Selection sort goes through each item in the list repeatedly. In every pass, the smallest value in the remained list will be selected and placed in a sorted list. Same to bubble sort, selection sort also has O(n^2) time complexity.

Here’s the sample implementation in Java.

1.  void selectionSort(int[] arr){

2.   

3.    int length = arr.length;

4.    for (int k=0; k < length; k++){

5.   

6.      // get the current smallest 

7.      // element

8.      int min = arr[k];

9.      int minIndex = k;

10.    for (j = k+1; j < N; j++){

11.        if (A[j] < min) {

12.            min = arr[j];

13.            minIndex = j;

14.        }

15.    }

16.    // put the smallest element  to the sorted list

17.    A[minIndex] = A[k];

18.    A[k] = min;

19.  }

20.}

Here’s a step-by-step example of Selection Sort.

Bubble Sort

Bubble sort repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Although the algorithm is simple, it is too slow (O(n^2)) and impractical for most problems even compared to insertion sort. It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position.

Here’s the sample implementation in Java.

1.  void bubbleSort(int[] arr) {

2.   

3.    int n = arr.length;

4.   

5.    for(int i=0;i < n;i++){

6.      for(int j=1;j < (n-i);j++){

7.        if(arr[j-1]>arr[j]){

8.          //swap the elements

9.          int temp = arr[j-1];

10.        arr[j-1] = arr[j];

11.        arr[j] = temp;

12.      }

13.    }

14.  }      

15.}

Here’s a step-by-step example of bubble sort. Basically, each pass “bubbles” the largest value from the unsorted area to the sorted area:

Insertion Sort

Insertion sort picks elements from the unsorted list one by one. For each element, it will be inserted into the proper position of the sorted list. Same to bubble sort, insertion sort also has O(n^2) time complexity.

Here’s the sample implementation in Java.

1.  void InsertionSort(int[] arr){

2.    // the number of items 

3.    // sorted so far

4.    int j;

5.    int length = arr.length;

6.    for (j = 1; j < length; j++){

7.     

8.      // the item to be inserted

9.      int key = arr[j];

10.             

11.    int i=j-1;

12.    while(i>=0 && arr[i] > key){

13.             

14.      // move one value over 

15.      // one place to the right

16.      arr[i+1] = arr[i];

17.      i--;

18.    }

19.    // put the key in its proper 

20.    // location

21.    arr[i+1] = key;    

22.  }

23.}

Here’s a step-by-step example of insertion sort.

Merge Sort

Merge sort divides the array into two halves, sorts each of those halves and then merges them back together. For each half, it uses the same algorithm to divide and merge smaller halves back. The smallest halves will just have one element each which is already sorted.

Note that the merge step needs an auxiliary array to avoid overwriting the values in the original array. The sorted values are then copied back from the auxiliary array to the original array.

Merge sort is a very typical divide-and-conquer algorithm. The idea is to divide a bigger problem (sorting a bigger array) to a smaller problem (sorting a smaller array) and then combine the results to generate the final result (by merging sorted arrays back).

The average time complexity of merge sort is O(nlog(n)).

Here’s the sample implementation of merge sort in Java.

1.  void mergeSort(int[] arr){

2.    int[] helper = new int[arr.length];

3.    mergeSort(arr,helper, 0, 

4.      arr.length-1);

5.  }

6.  void mergeSort(int[] arr, int[] helper, 

7.    int low, int high){

8.    if(low < high){

9.   

10.     /* divide the array to two

11.     halves and sort them */

12.     int middle = (low+high)/2;

13.     mergeSort(arr, helper, 

14.       low, middle);

15.     mergeSort(arr, helper, 

16.       middle+1, high);

17.     // merge the sorted array

18.     merge(arr, helper, low, 

19.       middle, high);

20.   }

21. }

22. void merge(int[] arr, int[] helper, 

23.   int low, int middle, int high){

24.   /* copy both halves in 

25.   a helper array */

26.   for(int i=low, i <= high; i++){

27.     helper[i] = array[i];

28.   }

29.   // the start element indexes of

30.   // the two halves to be merged 

31.   int left = low;

32.   int right = middle+1;

33.   int current = low;

34.   /* Iterate through the helper array. 

35.   Compare each elements in the left 

36.   and right halves and copy the smaller

37.   element from the two halves to 

38.   the original array. */

39.   while(left < middle && right <= high){

40.  

41.     if(helper[left] <= helper[right]){

42.       arr[current] = helper[left];

43.       left++;

44.     }

45.     else{

46.       arr[current] = helper[right];

47.       right++;

48.     }

49.     current++;

50.   }

51.   /* copy the rest of the left side  to the target array */

52.   int remaining = middle - left;

53.   for(int i=0; i <= remaining; i++){

54.     arr[current++]=helper[left+i];

55.   }

56. }

Here’s a step-by-step example of merge sort.

Quick Sort

Quick Sort is also a divide-and-conquer algorithm like Merge Sort. In Quick Sort, we pick a random element (called pivot) to partition the unsorted array to two parts: all the elements less then the pivot and all the elements that are greater than the pivot. If we keep partitioning the sub arrays with the same method recursively, eventually we will get a sorted array.

The most perfect case is that everytime we pick a pivot that is the median of the list. Then the time complexity will be O(nlog(n)). The worst case happens if everytime we pick a pivot that is the largest or smallest element in the array. For example, if the list is sorted in reversed order and our pivot picking strategy is to pick the first element in the array, then after every patitioning we will get a partition with 1 element and another partition with n-1 elements. In such case, the time complexity will be reduced to O(n^2).

Here’s the sample implementation in Java.

1.  void quickSort(int[] arr,   int left, int right){

2.      int index = partition(arr, left,       right);

3.  if(left < index-1){

4.      quickSort(arr, left, index-1);

5.    }

6.    if(index < right){

7.      quickSort(arr, index, right);

8.    }

9.  }

10.int partition(int[] arr,   int left, int right) {

11.  // pick a pivot in the middle of  the array

12.  int pivot = arr[(left+right)/2];

13.  while(left <= right){

14.    // find the element on left that should be on right

15.    while(arr[left] < pivot)

16.      left++;

17.    // find the element on right that should be on left

18.    while(arr[right] > pivot)

19.      right--;

20.    if(left <= right){

21.      // swap elements

22.      swap(arr, left, right);

23.      left++;

24.      right--;

25.    }

26.    return left;

27.  }

28.}