Data Structure: sorting (basic)

Sorting basically means to arrange the data in a certain order, so it's easier for us to use those data. In this post, I'll talk about some basic sorting algorithms; bubble sort, selection sort, and insertion sort.

Sorting Algorithms and their Complexity

Algorithm	Complexity
Bubble Sort	O(n2)
Selection Sort	O(n2)
Insertion Sort	O(n2)
Shell Sort	O(n2)
Quick Sort	O(n2)
Radix Sort	O(nk)
Heap Sort	O(nlog(n))
Merge Sort	O(nlog(n))

Before we head to the main contents, I would like to recommend a website that helps visualize how all these sorting algorithms work. (P.S. It helps with other stuffs too like visualizing hash table, binary heap, etc.). And this one is helpful, too!

Bubble Sort

In bubble sort we compare 2 items at a time, and we either swap them or move on to compare the next pair. It is infamously slow, but it's conceptually the simplest of the sorting algorithm.

A pseudocode of how it works to sort an array of size n

1. Repeat i) to ii) for n times
    i) Compare the leftmost element in array with the next element
        a. If the leftmost element is bigger, swap them
        b. Else, go to 2.
    ii) Move to next position, set that element to be the leftmost element. Is there next element?
        a. Yes, go back to i)
        b. No, go back to 1.
2. Done

And here's a java code of bubble sort

public void bubbleSort() {
    int out, in, temp;
    int[] a = new int[nElems];      // nElems is the number of elements we'll input later ^^||
    for(out=nElems-1; out>1; out--) {  
        for(in=0; in<out; in++) {
            if( a[in] > a[in+1] ) { // out of order?
                temp = a[in];       // swap them
                a[in] = a[in+1];
                a[in+1] = temp;
            }
        }
    }
}

Efficiency of Bubble sort

• comparison operations:

  for N items: (N-1) + (N-2) + (N-3) + ... + 1
  = N*(N-1)/2
  ≈ N²/2

• swap operations:

  usually less than comparison operations
  ≈ N²/4

• which means its complexity ≈ O(N²), quite slow

Selection Sort

In selection sort, we move along the data and select the smallest item, swap the selected item to the position 0, and so on.

A pseudocode for an array of size n

1. Repeat i) to ii) for (n-1) rounds
    i) Go through every unsorted element
    ii) Pick the smallest one and swap with element at the first position (but next to those already been sorted)
2. Done 

A java code for selection sort

public void selectionSort() {
    int out, in, min, temp;
    int[] a = new int[nElems];        // nElems is the number of elements we'll input later ^^||
    for(out=0; out<nElems-1; out++) {
        min = out;
        for(in = out+1; in<nElems; in++) {
            if(a[in] < a[min]) {      // if min is greater,
                min = in;             // we have a new min
                temp = a[out];        // swap 'em
                a[out] = a[min];
                a[min] = temp;
            }
        }
    }
}

Efficiency of Selection sort

• comparison operations:

  the same as bubble sort
  ≈ N²/2

• swap operations:

  usually less than N

• thus we get O(N²); slow :/

Insertion Sort

We divide the data into 2 lists (sorted and unsorted). In each iteration, the first element of the unsorted list is inserted at appropriate position into the sorted list.

pseudocode

1. Repeat i) and ii) for (n-1) rounds
    i) insert the first unsorted element, to the sorted
    ii) compare the newly inserted element to all the sorted, and put it in place
2. Done

java code!

public void insertionSort() {
    int in, out;
    int[] a = new int[nElems];         // nElems is the number of elements we'll input later ^^||
    for(out=1; out<nElems; out++) {    // out is dividing line
        long temp = a[out];            // remove marked item
        in = out;                      // start shifts at out
        while(in>0 && a[in-1]>=temp) { // until one is smaller,
            a[in] = a[in-1];           // shift item to right
            --in;                      // go left one position
        }
        a[in] = temp; // insert marked item
    }
} 

Efficiency of Selection sort

• comparison operations:

  N*(N-1)/4
  ≈ N²/4

• copy operations:

  usually similar to comparison operations

• its complexity ≈ O(N²); still slow..

• If the data is sorted, the algorithm runs in almost O(N).

• If the data is in reverse order, it runs pretty much slow like the bubble sort

Comparing the 3 simple sorts

They require only their initial data array plus a little extra memory, but all their algorithms execute in O(N²) time.

• The bubble sort is simple, but the least efficient. It is practical if the amount of data is small
• The selection sort minimizes the number of swaps, but the number of comparisons is still high
• The insertion sort is the most versatile of the three, and is the best in most situations, assuming the amount of data is small or the data is almost sorted.